Skip to main content

turning off presolve after "max constraint violation (1.0000e+00) exceeds tolerance" still produces an incorrect solution

Shunji Tanaka
  • Gurobi-versary
  • First Comment
  • First Question

Hi,

I am trying to solve a binary IP using Gurobi Optimizer v8.1.1 through C++ API on a Linux box, when I find difficulty in checking the infeasibility of the model.

I turned on presolve, as it improves the performance, but it sometimes fails to detect the infeasibility of the problem and returns an infeasible solution as an optimal one with the following message:

Warning: max constraint violation (1.0000e+00) exceeds tolerance
(model may be infeasible or unbounded - try turning presolve off)

To avoid this erroneous behavior, I tried the following procedure:

  1. Check the feasibility of the solution by retrieving GRB_DoubleAttr_Slack of every constraint.

  2. If the solution is infeasible, presolve is turned off and the model is optimized again.

However, even if presolve is turned off, the optimizer seems to recycle the results of the previous presolve and it again produces an infeasible solution.

Is there any good idea to check the infeasibility correctly with presolve turned on by default? Should I turn off Presolve from the start?

Best regards,

Shunji Tanaka

 

Sample C++ code, data file and their log output are as follows:

[test.cpp]

#include <iostream>
#include "gurobi_c++.h"
using namespace std;
#define Tolerance (1.0e-6)
int main(const int argc, const char **argv)
{
  try {
    GRBEnv env = GRBEnv();
    GRBModel *m = new GRBModel(env, "test.lp");
    cout << endl << "**Without presolve******" << endl << endl;
    m->set(GRB_IntParam_Presolve, 0);
    m->optimize();
    if(m->get(GRB_IntAttr_Status) == GRB_OPTIMAL) {
      cout << endl << "**The model is feasible**" << endl << endl;
    } else if(m->get(GRB_IntAttr_Status) == GRB_INFEASIBLE) {
      cout << endl << "**The model is infeasible**" << endl << endl;
    } else {
      throw;
    }
    delete m;
    m = new GRBModel(env, "test.lp");
    cout << endl << "**With presolve******" << endl << endl;
    m->set(GRB_IntParam_Presolve, -1);
    m->optimize();
    if(m->get(GRB_IntAttr_Status) == GRB_OPTIMAL) {
      bool again = false;
      GRBConstr *c = m->getConstrs();
      for(int n = 0; n < m->get(GRB_IntAttr_NumConstrs); ++n) {
	char sense = c[n].get(GRB_CharAttr_Sense);
	double slack = c[n].get(GRB_DoubleAttr_Slack);
	if(sense == '>' and slack >= Tolerance) {
	  again = true;
	  break;
	} else if(sense == '<' and slack <= -Tolerance) {
	  again = true;
	  break;
	} else if(sense == '=' and (slack <= -Tolerance || slack >= Tolerance)) {
	  again = true;
	  break;
	}
      }
      if(again) {
	cout << endl << "**Presolve returned an infeasible solution**" << endl;
	cout << "**Presolve is turned off and the model is optimized again**" << endl << endl;
	m->set(GRB_IntParam_Presolve, 0);
	m->optimize();
      }
    }
    if(m->get(GRB_IntAttr_Status) == GRB_OPTIMAL) {
      cout << endl << "**The model is feasible**" << endl << endl;
    } else if(m->get(GRB_IntAttr_Status) == GRB_INFEASIBLE) {
      cout << endl << "**The model is infeasible**" << endl << endl;
    } else {
      throw;
    }
  } catch(GRBException e) {
    cout << "Error code = " << e.getErrorCode() << endl;
    cout << e.getMessage() << endl;
  } catch(...) {
    cout << "Exception during optimization" << endl;
  }
  return 0;
}

 

[test.lp]

\ LP format - for model browsing. Use MPS format to capture full model detail.
Minimize
  x(8,0) + x(8,1) + x(15,0) + 2 x(17,3) + 2 x(17,4) + 2 x(17,5) + 2 x(17,6)
   + 2 x(17,7) + 2 x(17,8) + 2 x(17,9) + 2 x(17,10) + 2 x(17,11)
   + 2 x(17,12) + 2 x(17,13) + 2 x(17,14) + x(26,0) + x(26,1) + x(7,0)
   + x(7,1) + x(7,2) + x(7,3) + x(23,0) + x(23,1) + x(23,2) + x(12,0)
   + x(12,1) + x(12,2) + x(12,3) + x(20,0) + x(20,1) + x(20,2) + x(20,3)
   + x(21,0) + x(21,1) + x(21,2) + x(21,3) + x(21,4) + x(29,0) + x(29,1)
   + x(29,2) + x(29,3) + x(29,4) + x(18,0) + x(18,1) + x(18,2) + x(18,3)
   + x(18,4) + x(24,0) + x(24,1) + x(24,2) + x(24,3) + x(24,4) + x(24,5)
   + x(24,6) + x(28,0) + x(28,1) + x(28,2) + x(28,3) + x(28,4) + x(28,5)
   + x(28,6) + x(27,0) + x(27,1) + x(27,2) + x(27,3) + x(27,4) + x(27,5)
   + x(27,6) + 2 x(30,3) + 2 x(30,4) + 2 x(30,5) + 2 x(30,6) + 2 x(19,3)
   + 2 x(19,4) + 2 x(19,5) + 2 x(19,6) + 2 x(25,7) + 2 x(17,18) + 2 x(25,9)
   + 2 x(25,10) + 2 x(25,11) + x(14,0) + 2 x(14,4) + 2 x(14,5) + 2 x(14,6)
   + 2 x(14,7) + 2 x(17,20) + 2 x(17,21) + 2 x(17,22) + 2 x(15,8)
   + 2 x(15,9) + 2 x(15,10) + 2 x(14,10) + 2 x(14,11) + 2 x(17,24)
   + 2 x(17,25)
Subject To
 a1: x(30,3) + x(30,4) + x(30,5) + x(30,6) = 1
 a2: x(19,3) + x(19,4) + x(19,5) + x(19,6) = 1
 a3: x(8,0) + x(8,1) = 1
 a4: x(15,0) + x(15,8) + x(15,9) + x(15,10) = 1
 a5: x(25,7) + x(25,9) + x(25,10) + x(25,11) = 1
 a6: x(14,0) + x(14,4) + x(14,5) + x(14,6) + x(14,7) + x(14,10) + x(14,11)
   = 1
 a7: x(17,3) + x(17,4) + x(17,5) + x(17,6) + x(17,7) + x(17,8) + x(17,9)
   + x(17,10) + x(17,11) + x(17,12) + x(17,13) + x(17,14) + x(17,18)
   + x(17,20) + x(17,21) + x(17,22) + x(17,24) + x(17,25) = 1
 a8: x(26,0) + x(26,1) = 1
 a9: x(7,0) + x(7,1) + x(7,2) + x(7,3) = 1
 a10: x(23,0) + x(23,1) + x(23,2) = 1
 a11: x(12,0) + x(12,1) + x(12,2) + x(12,3) = 1
 a12: x(20,0) + x(20,1) + x(20,2) + x(20,3) = 1
 a13: x(21,0) + x(21,1) + x(21,2) + x(21,3) + x(21,4) = 1
 a14: x(29,0) + x(29,1) + x(29,2) + x(29,3) + x(29,4) = 1
 a15: x(18,0) + x(18,1) + x(18,2) + x(18,3) + x(18,4) = 1
 a16: x(24,0) + x(24,1) + x(24,2) + x(24,3) + x(24,4) + x(24,5) + x(24,6)
   = 1
 a17: x(28,0) + x(28,1) + x(28,2) + x(28,3) + x(28,4) + x(28,5) + x(28,6)
   = 1
 a18: x(27,0) + x(27,1) + x(27,2) + x(27,3) + x(27,4) + x(27,5) + x(27,6)
   = 1
 b1: x(8,0) + x(15,0) <= 1
 b2: x(26,0) + x(29,0) <= 1
 b3: x(20,0) + x(21,0) <= 1
 b4: x(20,1) + x(21,1) <= 1
 b5: x(20,3) + x(21,4) <= 1
 b6: x(20,1) + x(29,1) <= 1
 b7: x(20,3) + x(29,4) <= 1
 b8: x(21,3) + x(29,3) <= 1
 b9: x(20,0) + x(19,3) <= 1
 b10: x(20,1) + x(19,4) <= 1
 b11: x(20,3) + x(19,6) <= 1
 b12: x(21,0) + x(19,3) <= 1
 b13: x(21,1) + x(19,4) <= 1
 b14: x(21,4) + x(19,6) <= 1
 b15: x(29,1) + x(19,4) <= 1
 b16: x(29,2) + x(19,5) <= 1
 b17: x(29,4) + x(19,6) <= 1
 b18: x(26,1) + x(25,7) <= 1
 b19: x(26,1) + x(17,18) + x(17,25) <= 1
 b20: x(25,10) + x(14,0) + x(14,4) + x(14,5) + x(14,6) + x(14,7) + x(14,10)
   + x(14,11) <= 1
 b21: x(17,3) + x(17,4) + x(17,5) + x(17,6) + x(17,7) + x(17,8) + x(17,9)
   + x(17,10) + x(17,11) + x(17,12) + x(17,13) + x(17,14) + x(25,11)
   + x(17,22) <= 1
 b22: x(29,0) + x(25,9) <= 1
 b23: x(19,5) + x(14,6) + x(14,11) <= 1
 b24: x(14,4) + x(14,5) + x(14,6) + x(14,7) + x(17,21) + x(14,10)
   + x(14,11) <= 1
 b25: x(20,2) + x(14,6) + x(14,11) <= 1
 b26: x(21,2) + x(14,6) + x(14,11) <= 1
 b27: x(29,2) + x(14,6) + x(14,11) <= 1
 b28: x(29,0) + x(17,20) + x(17,24) <= 1
 b29: x(19,3) + x(15,8) <= 1
 b30: x(19,6) + x(15,10) <= 1
 b31: x(14,0) + x(14,4) + x(14,5) + x(14,6) + x(14,7) + x(15,8) + x(14,10)
   <= 1
 b32: x(14,0) + x(14,4) + x(14,5) + x(14,6) + x(14,7) + x(15,9) + x(14,10)
   + x(14,11) <= 1
 b33: x(14,0) + x(14,4) + x(14,5) + x(14,6) + x(14,7) + x(15,10) + x(14,10)
   <= 1
 b34: x(20,0) + x(15,8) <= 1
 b35: x(20,3) + x(15,10) <= 1
 b36: x(21,0) + x(15,8) <= 1
 b37: x(21,4) + x(15,10) <= 1
 b38: x(29,4) + x(15,10) <= 1
 c: x(8,1) + x(30,3) + x(30,4) + x(30,5) + x(30,6) + x(19,3) + x(19,4)
   + x(19,5) + x(19,6) <= 2
Bounds
Binaries
 x(8,0) x(8,1) x(15,0) x(17,3) x(17,4) x(17,5) x(17,6) x(17,7) x(17,8)
 x(17,9) x(17,10) x(17,11) x(17,12) x(17,13) x(17,14) x(26,0) x(26,1)
 x(7,0) x(7,1) x(7,2) x(7,3) x(23,0) x(23,1) x(23,2) x(12,0) x(12,1)
 x(12,2) x(12,3) x(20,0) x(20,1) x(20,2) x(20,3) x(21,0) x(21,1) x(21,2)
 x(21,3) x(21,4) x(29,0) x(29,1) x(29,2) x(29,3) x(29,4) x(18,0) x(18,1)
 x(18,2) x(18,3) x(18,4) x(24,0) x(24,1) x(24,2) x(24,3) x(24,4) x(24,5)
 x(24,6) x(28,0) x(28,1) x(28,2) x(28,3) x(28,4) x(28,5) x(28,6) x(27,0)
 x(27,1) x(27,2) x(27,3) x(27,4) x(27,5) x(27,6) x(30,3) x(30,4) x(30,5)
 x(30,6) x(19,3) x(19,4) x(19,5) x(19,6) x(25,7) x(17,18) x(25,9) x(25,10)
 x(25,11) x(14,0) x(14,4) x(14,5) x(14,6) x(14,7) x(17,20) x(17,21)
 x(17,22) x(15,8) x(15,9) x(15,10) x(14,10) x(14,11) x(17,24) x(17,25)
End

 

[output]

Read LP format model from file test.lp
Reading time = 0.00 seconds
: 57 rows, 96 columns, 226 nonzeros

**Without presolve******

Optimize a model with 57 rows, 96 columns and 226 nonzeros
Variable types: 0 continuous, 96 integer (96 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 2e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 2e+00]
Variable types: 0 continuous, 96 integer (96 binary)

Root relaxation: objective 2.350000e+01, 27 iterations, 0.00 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0   23.50000    0   10          -   23.50000      -     -    0s
     0     0   24.00000    0   15          -   24.00000      -     -    0s
     0     2   24.00000    0   15          -   24.00000      -     -    0s

Explored 23 nodes (139 simplex iterations) in 0.01 seconds
Thread count was 8 (of 8 available processors)

Solution count 0

Model is infeasible
Best objective -, best bound -, gap -

**The model is infeasible**

Read LP format model from file test.lp
Reading time = 0.00 seconds
: 57 rows, 96 columns, 226 nonzeros

**With presolve******

Optimize a model with 57 rows, 96 columns and 226 nonzeros
Variable types: 0 continuous, 96 integer (96 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 2e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 2e+00]
Presolve removed 50 rows and 89 columns
Presolve time: 0.00s
Presolved: 7 rows, 7 columns, 16 nonzeros
Variable types: 0 continuous, 7 integer (7 binary)
Found heuristic solution: objective 24.0000000

Root relaxation: cutoff, 1 iterations, 0.00 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0     cutoff    0        24.00000   24.00000  0.00%     -    0s

Explored 0 nodes (1 simplex iterations) in 0.00 seconds
Thread count was 8 (of 8 available processors)

Solution count 1: 24 

Optimal solution found (tolerance 1.00e-04)
Warning: max constraint violation (1.0000e+00) exceeds tolerance
         (model may be infeasible or unbounded - try turning presolve off)
Best objective 2.400000000000e+01, best bound 2.400000000000e+01, gap 0.0000%

**Presolve returned an infeasible solution**
**Presolve is turned off and the model is optimized again**

Optimize a model with 57 rows, 96 columns and 226 nonzeros
Variable types: 0 continuous, 96 integer (96 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [1e+00, 2e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 2e+00]

Continuing optimization...


Explored 0 nodes (1 simplex iterations) in 0.00 seconds
Thread count was 8 (of 8 available processors)

Solution count 1: 24 

Optimal solution found (tolerance 1.00e-04)
Warning: max constraint violation (1.0000e+00) exceeds tolerance
Best objective 2.400000000000e+01, best bound 2.400000000000e+01, gap 0.0000%

**The model is feasible**

 

 

 

 

0

Comments

3 comments

Date Votes
  • Official comment
    Simranjit Kaur
    • Gurobi Staff Gurobi Staff
    This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
  • Eli Towle
    • Gurobi Staff Gurobi Staff
    Edited

    Hi Shunji,

    Presolve assumes that a model is feasible and bounded. Because this model is infeasible, some presolve reductions can have unexpected behavior that results in constraint violations. For this reason, Gurobi prints the following warning:

    Warning: max constraint violation (1.0000e+00) exceeds tolerance
             (model may be infeasible or unbounded - try turning presolve off)

    Note that after setting Presolve=0, you should reset the model before re-solving it to discard the existing solution information.

    In general, such a warning can be avoided by completely disabling presolve. For this model, it appears that it is sufficient to set Aggregate=0.

    I hope this helps. Thanks!

    Eli

    0
  • Shunji Tanaka
    • Gurobi-versary
    • First Comment
    • First Question

    Dear Eli,

    Thank you very much for your helpful advice.  The function "reset()" is exactly what I was searching for.  "Aggregate=0" seems to work fine as well.  I should have noticed Section 24.5 in the reference manual!

    Since my model has a lot of rows and columns, and hence I can expect presolve to considerably eliminate them, I will stick to the two-level infeasibility check instead of completely disabling presolve.

    Best regards,

    Shunji

     

     

     

    0

Post is closed for comments.

Didn't find what you were looking for?

New post