Topic
  • 9 replies
  • Latest Post - ‏2013-02-26T09:49:44Z by SystemAdmin
SystemAdmin
SystemAdmin
7929 Posts

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
    475 Posts

    Re: Infeasible status?

    ‏2013-02-22T16:34:59Z  
    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

    Re: Infeasible status?

    ‏2013-02-22T17:18:16Z  
    • T_O
    • ‏2013-02-22T16:34:59Z
    Could you give some more details about what you are doing?

    Did you try to calculate an IIS?

    Best regards,
    Thomas
    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
    475 Posts

    Re: Infeasible status?

    ‏2013-02-22T21:55:15Z  
    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.
    Which API are you using? Did you try to calculate an IIS?

    Best regards,
    Thomas
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Infeasible status?

    ‏2013-02-23T09:46:43Z  
    • T_O
    • ‏2013-02-22T21:55:15Z
    Which API are you using? Did you try to calculate an IIS?

    Best regards,
    Thomas
    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

    Re: Infeasible status?

    ‏2013-02-23T16:42:58Z  
    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?
    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

    Re: Infeasible status?

    ‏2013-02-25T10:01:49Z  
    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:
    <pre class="java dw" data-editor-lang="java" data-pbcklang="java" dir="ltr">read model.sav opt conflict display conflict all </pre>

    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
    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
    475 Posts

    Re: Infeasible status?

    ‏2013-02-25T10:49:53Z  
    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?
    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

    Re: Infeasible status?

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

    Re: Infeasible status?

    ‏2013-02-26T09:49:44Z  
    Thanks for confirmation that that's the way to go.
    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