Topic
IC4NOTICE: developerWorks Community will be offline May 29-30, 2015 while we upgrade to the latest version of IBM Connections. For more information, read our upgrade FAQ.
9 replies Latest Post - ‏2013-02-26T09:49:44Z by SystemAdmin
SystemAdmin
SystemAdmin
7929 Posts
ACCEPTED ANSWER

Pinned topic Infeasible status?

‏2013-02-22T14:25:10Z |
Hi again,
I solved two problems and both cplex status = 3 (infeasible). Below is their log outputs. Are they correct? I could not interpret its status from the output. Why don't I get the information of violated constraints? Thanks.

Problem 1:
Tried aggregator 4 times.
...
Tried aggregator 4 times.
MIP Presolve eliminated 2155 rows and 801 columns.
MIP Presolve modified 421 coefficients.
Aggregator did 181 substitutions.
Reduced MIP has 4181 rows, 1571 columns, and 11854 nonzeros.
Reduced MIP has 763 binaries, 103 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.03 sec. (31.03 ticks)

Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap

0 0 -1.00000e+037 0 74.0000 0

Root node processing (before b&c):
Real time = 0.06 sec. (6.63 ticks)
Parallel b&c, 8 threads:
Real time = 0.00 sec. (0.00 ticks)
Sync time (average) = 0.00 sec.
Wait time (average) = 0.00 sec.
Total (root+branch&cut) = 0.06 sec. (6.63 ticks)

Problem 2:
Tried aggregator 4 times.
...
Tried aggregator 2 times.
..
Clique table members: 127.
Tightened 9 constraints.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 8 threads.
Root relaxation solution time = 0.00 sec. (2.52 ticks)

Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap

0 0 48.0000 25 48.0000 258
0 0 cutoff 267
Elapsed time = 0.42 sec. (28.33 ticks, tree = 0.00 MB, solutions = 0)

Clique cuts applied: 1
Implied bound cuts applied: 9
Flow cuts applied: 1
Mixed integer rounding cuts applied: 8
Gomory fractional cuts applied: 2

Root node processing (before b&c):
Real time = 0.34 sec. (9.56 ticks)
Parallel b&c, 8 threads:
Real time = 0.00 sec. (0.00 ticks)
Sync time (average) = 0.00 sec.
Wait time (average) = 0.00 sec.
Total (root+branch&cut) = 0.34 sec. (9.56 ticks)
Updated on 2013-02-26T09:49:44Z at 2013-02-26T09:49:44Z by SystemAdmin
  • T_O
    T_O
    444 Posts
    ACCEPTED ANSWER

    Re: Infeasible status?

    ‏2013-02-22T16:34:59Z  in response to SystemAdmin
    Could you give some more details about what you are doing?

    Did you try to calculate an IIS?

    Best regards,
    Thomas
    • SystemAdmin
      SystemAdmin
      7929 Posts
      ACCEPTED ANSWER

      Re: Infeasible status?

      ‏2013-02-22T17:18:16Z  in response to T_O
      I just tried to solve it and stop it with nodelimit of 1, so I can collect the LP obj value. Then, continue to branch. Apparently, these problems have very small sum of infeasibilities (in the order of 1e-4). The strange thing is its log file does not really give me any information that it is infeasible. So, when I relaxed some constraints, their infeasibilities are gone and optimal solutions are found already at the root nodes.
      • T_O
        T_O
        444 Posts
        ACCEPTED ANSWER

        Re: Infeasible status?

        ‏2013-02-22T21:55:15Z  in response to SystemAdmin
        Which API are you using? Did you try to calculate an IIS?

        Best regards,
        Thomas
        • SystemAdmin
          SystemAdmin
          7929 Posts
          ACCEPTED ANSWER

          Re: Infeasible status?

          ‏2013-02-23T09:46:43Z  in response to T_O
          c++. I did not try to get IIS directly, but used OPL IDE to help me identify constraints that cause infeasibilities, which I presume that IIS is probably handled internally. As I mentioned, when constraints are relaxed accordingly, the problem is solved to optimality. Is there a way to set tolerances to cplex to avoid such minor infeasibility, in this case in the order of 1e-4 and lower?
          • SystemAdmin
            SystemAdmin
            7929 Posts
            ACCEPTED ANSWER

            Re: Infeasible status?

            ‏2013-02-23T16:42:58Z  in response to SystemAdmin
            Sure. This is the "feasibility tolerance" parameter. In the C API this is called CPX_PARAM_EPRHS. For other APIs you need to check the parameter reference manual. Just set this parameter to 1e-4.

            But first I recommend that you call the conflict refiner to identify a small infeasible subsystem (using the default feasibility tolerance). I don't know how this can be done in OPL Studio, but if you are willing to use the interactive, then export the model to a .sav file, call the interactive CPLEX and then do:
            read model.sav
            opt
            conflict
            display conflict all
            


            I am sure this is also supported from the OPL Studio IDE, but I just don't know right now where you would find it...
            Tobias
            Updated on 2014-03-24T22:37:50Z at 2014-03-24T22:37:50Z by iron-man
            • SystemAdmin
              SystemAdmin
              7929 Posts
              ACCEPTED ANSWER

              Re: Infeasible status?

              ‏2013-02-25T10:01:49Z  in response to SystemAdmin
              Thank you. I did try EpRHS before, but it did not work then, so I opted opl which could do conflict refiner as you mentioned and it helped me identify violated constraints. Here is another question. I suppose EpRHS is applied to all constraints. However, can I pick and choose which constraints EpRHS can be applied, for I'm afraid it would screw up integrality, etc.? or is there any other feasibility tolerance that could be applied to selected constraints?
              • T_O
                T_O
                444 Posts
                ACCEPTED ANSWER

                Re: Infeasible status?

                ‏2013-02-25T10:49:53Z  in response to SystemAdmin
                You could change the right hand sides manually. Remember that in this case, you have to convert equality constraints into ranged constraints.

                Best regards,
                Thomas
  • SystemAdmin
    SystemAdmin
    7929 Posts
    ACCEPTED ANSWER

    Re: Infeasible status?

    ‏2013-02-25T12:22:59Z  in response to SystemAdmin
    Thanks for confirmation that that's the way to go.
    • SystemAdmin
      SystemAdmin
      7929 Posts
      ACCEPTED ANSWER

      Re: Infeasible status?

      ‏2013-02-26T09:49:44Z  in response to SystemAdmin
      Please also note that setting the feasibility tolerance is not the same as relaxing the right hand sides of the constraints. This has already been discussed in several other threads, but since it is so important I keep reiterating.

      The feasibility tolerances are a work-around to deal with numerical inaccuracy that comes from using inexact floating point arithmetics (i.e., regular double precision calculations). If a feasibility tolerance "eps" is given, we have a constraint
      
      a*x <= b
      

      in the model, and x' is a potential solution vector, then x' is
      
      - feasible, 
      
      if a*x
      ' <= b, - infeasible, 
      
      if a*x
      ' > b + eps, and - undecided, 
      
      if b < a*x
      ' <= b + eps.
      

      If x' is undecided, then CPLEX is free to choose any status it wants to, and depending on the case it will choose one or the other. Typically, it would declare such a solution to be feasible, but it can also declare it infeasible. And this also depends of course on the outcome of the inexact floating point calculations.

      The surprising effect of this is that the optimal objective value for a given problem instance is no longer well-defined. A problem instance can have different "optimal" objective values that are all correct answers to the problem. In the extreme case, it can even both be correct to say that a model is feasible (i.e., there exists a feasible solution within the tolerance) and to say that it is infeasible (i.e., there exists no feasible solution, but maybe there is one that is feasible within the tolerance).
      Tobias