Weird behavior indicator function

回答済み

spineda

2025年06月24日 15:30

• 
• 
• 

Hi, I'm solving a mip with indicator constraints. I include below the log. First I solve the model with binary variables, then I fix the binaries and solve the continuous LP. In the last row of the mip, you can see the model suddenly changes the best solution and best bound to 1242.619. However, when I fix the obtained binary variables, the solution is 1516.122, which is actually worse than the second-best solution which is 1510.04. I do not have much experience with indicator functions, but I find this behaviour a bit weird. Just in case someone has an explanation. Thanks in advance!

 

Gurobi Optimizer version 10.0.3 build v10.0.3rc0 (linux64)

CPU model: AMD EPYC 7H12 64-Core Processor, instruction set [SSE2|AVX|AVX2]
Thread count: 128 physical cores, 128 logical processors, using up to 1 threads

Optimize a model with 491 rows, 1067 columns and 1508 nonzeros
Model fingerprint: 0xc35f981f
Model has 744 general constraints
Variable types: 881 continuous, 186 integer (186 binary)
Coefficient statistics:
 Matrix range     [1e+00, 2e+02]
 Objective range  [2e+01, 1e+03]
 Bounds range     [1e+00, 1e+03]
 RHS range        [2e-02, 4e+00]
 GenCon coe range [1e+00, 1e+00]
Presolve added 1088 rows and 0 columns
Presolve removed 0 rows and 287 columns
Presolve time: 0.03s
Presolved: 1579 rows, 780 columns, 4610 nonzeros
Variable types: 602 continuous, 178 integer (178 binary)

Root relaxation: objective 0.000000e+00, 704 iterations, 0.01 seconds (0.00 work units)

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

    0     0    0.00000    0   24          -    0.00000      -     -    0s
    0     0    0.00000    0   41          -    0.00000      -     -    0s
    0     0    0.00000    0   24          -    0.00000      -     -    0s
    0     0    0.00000    0   24          -    0.00000      -     -    0s
    0     0    0.00000    0   23          -    0.00000      -     -    0s
    0     0    0.00000    0   25          -    0.00000      -     -    0s
    0     0    0.00000    0   20          -    0.00000      -     -    0s
    0     0    0.00000    0   24          -    0.00000      -     -    0s
    0     0    0.00000    0   18          -    0.00000      -     -    0s
    0     0    0.00000    0   18          -    0.00000      -     -    0s
    0     0    0.00000    0   18          -    0.00000      -     -    0s
    0     2    0.00000    0   18          -    0.00000      -     -    0s
H  560   446                    2794.2017783 1304.67426  53.3%  32.8    2s
H  576   434                    2400.8779710 1304.67426  45.7%  44.9    2s
H  636   450                    2400.8779690 1304.67426  45.7%  52.7    3s
H  662   445                    2400.8779683 1304.67426  45.7%  50.9    3s
H  714   457                    2400.8779548 1304.67426  45.7%  48.4    3s
H  719   428                    1693.1359790 1304.67426  22.9%  48.1    3s
H  746   428                    1683.4004443 1304.67426  22.5%  46.9    3s
H  766   423                    1683.4004410 1304.67426  22.5%  46.2    3s
H  870   471                    1683.4004360 1304.67426  22.5%  41.6    3s
*  883   461             186    1674.2177725 1304.67426  22.1%  41.1    3s
 1711   902 1510.24972   68   22 1674.21777 1304.67426  22.1%  27.9    5s
H 1775   956                    1667.0485446 1304.67426  21.7%  27.3    5s
H 1802   982                    1666.7397402 1304.67426  21.7%  26.9    5s
H 1829   834                    1636.9903511 1304.67426  20.3%  26.6    5s
H 2415  1231                    1636.9903409 1304.67426  20.3%  23.2    6s
H 2416  1167                    1632.1627434 1304.67426  20.1%  23.1    6s
H 3417  1759                    1625.2272134 1304.67426  19.7%  19.4    7s
H 3418  1729                    1623.1649692 1304.67426  19.6%  19.4    7s
H 3703  1912                    1623.1573315 1304.67426  19.6%  18.7    8s
H 4064  2121                    1623.1573310 1304.67426  19.6%  17.9    8s
 4943  2555 1615.32892   72   44 1623.15733 1304.67426  19.6%  17.5   10s
H 5064  2435                    1618.5132657 1304.67426  19.4%  17.3   10s
H 5155  2504                    1618.5132576 1304.67426  19.4%  17.3   10s
H 6155  2928                    1618.5132477 1368.29421  15.5%  16.9   12s
 8344  3820 1370.91380   70   42 1618.51325 1368.29421  15.5%  15.6   15s
10203  4323 1607.89547   65   18 1618.51325 1368.29421  15.5%  14.4   20s
H10424  4204                    1618.5132318 1368.29421  15.5%  15.0   22s
H10450  4007                    1618.5132315 1368.29421  15.5%  15.0   22s
H11129  4126                    1616.6601152 1368.29421  15.4%  15.0   23s
H12129  4401                    1613.6020365 1368.29421  15.2%  15.1   24s
H12246  4281                    1613.4278067 1368.29421  15.2%  15.2   24s
12762  4458 1368.29421   96   62 1613.42781 1368.29421  15.2%  15.2   25s
H13249  4505                    1613.3891011 1368.29421  15.2%  15.1   25s
17910  6233 1526.84244  132   37 1613.38910 1368.29421  15.2%  15.5   30s
H19780  6984                    1609.8959735 1368.29421  15.0%  15.8   32s
H20780  7658                    1602.8165854 1368.29421  14.6%  15.9   33s
22083  8531 1368.29421   75   56 1602.81659 1368.29421  14.6%  15.9   35s
26919 11891 1368.29421  116   49 1602.81659 1368.29421  14.6%  16.3   40s
31713 15092 1368.29421  100   57 1602.81659 1368.29421  14.6%  16.5   45s
36003 17994 1368.29421  111   52 1602.81659 1368.29421  14.6%  16.7   50s
40933 21360 1368.29421  111   54 1602.81659 1368.29421  14.6%  16.8   55s
45898 24830 1586.60025  134   38 1602.81659 1368.29421  14.6%  16.6   60s
50626 28157 1368.29421   82   66 1602.81659 1368.29421  14.6%  16.4   65s
55353 31330 1368.29421   94   56 1602.81659 1368.29421  14.6%  16.4   70s
60517 35039 1368.29421  118   54 1602.81659 1368.29421  14.6%  16.3   75s
65224 38188 infeasible  128      1602.81659 1368.29421  14.6%  16.3   80s
69683 41352 infeasible  136      1602.81659 1368.29421  14.6%  16.5   85s
73697 44278 1368.29421  122   50 1602.81659 1368.29421  14.6%  16.5   90s
78289 47549 1368.29421   99   66 1602.81659 1368.29421  14.6%  16.6   95s
82793 50766 1368.29421  134   39 1602.81659 1368.29421  14.6%  16.7  100s
87333 53934 1368.29421   99   50 1602.81659 1368.29421  14.6%  16.8  105s
91910 57264 1368.29421   89   57 1602.81659 1368.29421  14.6%  16.9  110s
96249 60292 1368.29421  126   48 1602.81659 1368.29421  14.6%  17.0  115s
100787 63425 1368.29421  111   52 1602.81659 1368.29421  14.6%  17.0  120s
105284 66656 1368.29421  128   39 1602.81659 1368.29421  14.6%  17.1  125s
109988 69761 1451.80693  130   44 1602.81659 1368.29421  14.6%  17.1  130s
114958 73112 infeasible  116      1602.81659 1368.29421  14.6%  17.1  135s
119250 75930 1368.29421   92   54 1602.81659 1368.29421  14.6%  17.1  140s
123963 79159 1368.29421   83   59 1602.81659 1368.29421  14.6%  17.1  145s
128673 82480 1472.93938  141   34 1602.81659 1368.29421  14.6%  17.1  150s
133589 85863 1368.29421  107   47 1602.81659 1368.29421  14.6%  17.1  155s
138272 89026 1368.29421   82   63 1602.81659 1368.29421  14.6%  17.1  160s
142282 91594 1368.29421  115   52 1602.81659 1368.29421  14.6%  17.2  165s
147339 95269 1368.29421  114   54 1602.81659 1368.29421  14.6%  17.1  170s
151481 98110 1368.29421   88   69 1602.81659 1368.29421  14.6%  17.1  175s
156171 101371 1368.29421  113   50 1602.81659 1368.29421  14.6%  17.1  180s
160932 104604 1368.29421  137   39 1602.81659 1368.29421  14.6%  17.0  185s
166304 108101 1368.29421  139   37 1602.81659 1368.29421  14.6%  16.9  190s
H168686 108337                    1540.8488439 1368.29421  11.2%  16.8  192s
H168712 107837                    1516.9380701 1368.29421  9.80%  16.8  193s
169807 108561 1368.29421  140   33 1516.93807 1368.29421  9.80%  16.8  195s
174880 111708 1368.29421  110   60 1516.93807 1368.29421  9.80%  16.7  200s
179546 114700 1368.29421  122   52 1516.93807 1368.29421  9.80%  16.7  205s
H181072 115669                    1514.3944675 1368.29421  9.65%  16.6  206s
184006 117546 1368.29421  127   49 1514.39447 1368.29421  9.65%  16.6  210s
188701 120357 infeasible  125      1514.39447 1368.29421  9.65%  16.5  215s
193201 123383 1368.29421  141   38 1514.39447 1368.29421  9.65%  16.4  220s
197933 126302 1368.29421  114   57 1514.39447 1368.29421  9.65%  16.4  225s
H202195 128995                    1510.4840658 1368.29421  9.41%  16.4  229s
H202196 128990                    1510.0437285 1368.29421  9.39%  16.4  229s
202441 129105 1368.29421  115   58 1510.04373 1368.29421  9.39%  16.4  230s
207405 132353 1368.29421  120   45 1510.04373 1368.29421  9.39%  16.3  235s
212326 135267 1368.29421  102   60 1510.04373 1368.29421  9.39%  16.3  240s
217115 138510 1368.29421  127   48 1510.04373 1368.29421  9.39%  16.2  245s
H219326 140023                    1510.0400810 1368.29421  9.39%  16.2  247s
220962 141100     cutoff  137      1510.04008 1368.29421  9.39%  16.3  250s
225425 143919 1368.29421  117   58 1510.04008 1368.29421  9.39%  16.3  255s
230129 146998 1368.29421   89   58 1510.04008 1368.29421  9.39%  16.3  260s
234252 149709 1368.29421  125   28 1510.04008 1368.29421  9.39%  16.3  265s
238316 152179     cutoff  143      1510.04008 1368.29421  9.39%  16.3  270s
242267 154677 1368.29421  120   43 1510.04008 1368.29421  9.39%  16.4  275s
246592 157296 1368.29421  110   63 1510.04008 1368.29421  9.39%  16.3  280s
250763 159664 1368.29421  128   45 1510.04008 1368.29421  9.39%  16.3  285s
254795 161835 1436.13633  144   33 1510.04008 1368.29421  9.39%  16.3  290s
H259339 62579                    1242.6193661 1242.61937  0.00%  16.3  294s

Cutting planes:
 Implied bound: 2
 Projected implied bound: 101
 Flow cover: 53

Explored 259340 nodes (4224094 simplex iterations) in 294.99 seconds (210.27 work units)
Thread count was 1 (of 128 available processors)

Solution count 10: 1242.62 1510.04 1510.04 ... 1613.39

Optimal solution found (tolerance 1.00e-04)
Warning: max constraint violation (6.8001e-01) exceeds tolerance
Warning: max general constraint violation (6.8001e-01) exceeds tolerance
        (model may be infeasible or unbounded - try turning presolve off)
Best objective 1.242619366082e+03, best bound 1.242619366082e+03, gap 0.0000%
Set parameter OutputFlag to value 1
Set parameter Threads to value 1
Set parameter TimeLimit to value 3600
Gurobi Optimizer version 10.0.3 build v10.0.3rc0 (linux64)

CPU model: AMD EPYC 7H12 64-Core Processor, instruction set [SSE2|AVX|AVX2]
Thread count: 128 physical cores, 128 logical processors, using up to 1 threads

Optimize a model with 1049 rows, 1067 columns and 2350 nonzeros
Model fingerprint: 0x4d56858f
Variable types: 881 continuous, 186 integer (186 binary)
Coefficient statistics:
 Matrix range     [1e+00, 2e+02]
 Objective range  [2e+01, 1e+03]
 Bounds range     [1e+00, 1e+03]
 RHS range        [2e-02, 4e+00]
Presolve removed 1012 rows and 1015 columns
Presolve time: 0.00s
Presolved: 37 rows, 52 columns, 155 nonzeros
Variable types: 52 continuous, 0 integer (0 binary)

Root relaxation: objective 1.516122e+03, 41 iterations, 0.00 seconds (0.00 work units)

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

*    0     0               0    1516.1221026 1516.12210  0.00%     -    0s

Explored 1 nodes (41 simplex iterations) in 0.00 seconds (0.00 work units)
Thread count was 1 (of 128 available processors)

Solution count 1: 1516.12

Optimal solution found (tolerance 1.00e-04)
Best objective 1.516122102623e+03, best bound 1.516122102623e+03, gap 0.0000%

関連

• Indicator Constraints

0

• 

  Riley Clement

  • Gurobi Staff

  2025年06月25日 00:22

  Hi Salvador,

  I find this behaviour a bit weird

  It is weird, but maybe less weird in context of the warnings

  Warning: max constraint violation (6.8001e-01) exceeds tolerance
  Warning: max general constraint violation (6.8001e-01) exceeds tolerance
          (model may be infeasible or unbounded - try turning presolve off)

  The solution being found has at least one significantly large constraint violation.  It was likely a valid solution in the presolved space with respect to tolerances, but when it is “uncrushed” it is not a clean solution.

  I notice that you are using v10.0.3, I would use our latest v12.0.2 in case this is related to something that has been fixed or improved.

  If you want to share a model file (MPS) with us, via a service like dropbox, google drive, github etc, then please do and I'll look at it further. 

  - Riley

  0
• 

  spineda

  2025年07月18日 15:29

  • 
  • 
  • 

  Dear Riley,

  Thanks for the reply.

  I have another example to this repository (https://github.com/salvapineda/gurobi_indicator) including a .mps file and a .py file to read it and execute with a feasible solution. I also include the log I get in Gurobi 10.0.3.

  The initial solution is feasible with an objective function of 1432.46. Then Gurobi “jumps” to a solution with an objective function of 1331.42, but then it realizes this is infeasible with a constraint violation of 1.0819e+00 and concludes that the model may be infeasible. 

  I do not understand why the solver says the problem can be infeasible if it already knows a feasible solution. Or maybe I'm missing something.

  In any case, thanks a lot for the help.

  Best, 

  Salva.

   

  0
• 

  Riley Clement

  • Gurobi Staff

  2025年07月21日 00:54

  Hi Salva,

  I took a look, it seems similar to https://support.gurobi.com/hc/en-us/community/posts/12035360261649

  I used SolFiles to write all solutions found to a directory.  On my machine, with v12.0.3, we found 62 solutions.  12 of these were “infeasible”, i.e. had very large constraint violations.

  The solutions are all ok in the presolved space but then when translated back to the original space errors are magnified, which is why the warning suggests to turn off presolve.  Turning off presolve is an extreme measure, here is what I think you should do:

  * Use v12.0.3 - with each release we generally improve performance and numeric stability

  * Use IntegralityFocus=1.  Your indicator constraints are being translated to Big M linear constraints, which are susceptible to trickle flow error.

  * Add bounds to variables in RHS of indicator constraints.  To translate indicator constraints we need to derive bounds for the expressions appearing on the RHS of indicator constraints.  A quick glance suggests does not look like your variables that appear in the RHS do not have bounds (upper or lower).  If you provide bounds for variables then they may be tighter than what Gurobi is able to derive, or perhaps enables Gurobi to tighten bounds further.

  - Riley

  0
• 

  spineda

  2025年07月21日 07:44

  • 
  • 
  • 

  Dear Riley,

  Thank you very much for your reply.

  Yes, the problem is similar to the one you pointed out.

  What I don’t understand is the following: if Gurobi is able to find 62 solutions, with 12 of them being infeasible, why doesn’t it return the best among the 50 feasible ones? I don’t know much about this internal behavior, but it seems like the most natural thing to do.

  Unfortunately, I don’t have access to Gurobi 12. I only have a license for Gurobi 10.

  The reason I’m researching this topic is that I argue that using indicator constraints out of the box in current solvers is quite risky, and that it’s often better to reformulate them using big-M constants. The thing is, whenever I present this argument at a conference, someone from Gurobi usually approaches me to say they disagree and insist that Gurobi handles these problems correctly.

  I agree that I could start tuning Gurobi’s parameters, but in my experience it’s much easier and more effective to do as you suggested: find suitable big-M values and reformulate the indicator constraints manually.

  Thanks again for your feedback!

  Best regards,
  Salva

  0
• 

  Gwyneth Butera

  • Gurobi Staff

  2025年07月21日 09:26

  Unfortunately, I don’t have access to Gurobi 12. I only have a license for Gurobi 10.

  As an Academic user, you should not have this restriction.

  0
• 

  Riley Clement

  • Gurobi Staff

  2025年07月21日 14:35

  Hi Salva,

  why doesn’t it return the best among the 50 feasible ones?

  Technically it returns up to n solutions where n is the value of the PoolSolutions parameter, it's just the last one found is the one reported in the log.  There may be other solutions found that may have violations within the allowed tolerances but what if they are not within the prescribed MIP gap?  I think logging a different solution other than the last would cause confusion.

  The thing is, whenever I present this argument at a conference, someone from Gurobi usually approaches me to say they disagree and insist that Gurobi handles these problems correctly.

  I would agree with them - and certainly with Python can lead to more readable code.  Indicator constraints were introduced to handle the numerical issues introduced by Big M constraints - in particular trickle flow, which is the culprit here.  The reason it is an issue here is because the indicator constraints are being translated into linear constraints.  The PreSOS1BigM parameter can be used to control this.

  To do the translation Gurobi has to derive bounds on the RHS of the indicator constraints expressions.  This is where they can be a downfall.  If coding Big M constraints the user is forced to think about bounds.  If using indicator constraints they can ignore bounds (at their peril).  If the user defines bounds for all variables appearing in indicator constraints then I see no disadvantage, there is only the advantage of flexibility.

  - Riley 

   

  0
• 

  spineda

  2025年07月21日 14:53

  • 
  • 
  • 

  Thanks Riley, 

  I think I get your point. So what you're saying is that I can use knowledge about the problem to compute bounds on RHS, feed them to Gurobi, and still get some benefits from the indicator constraints since it can help with numerical issues. Is that correctly understood?

  I thought that indicator constraints were use for lazy people that did not want to find appropiate bigM values, but it seems I was wrong, right?

  Best,

  Salva.

  0
• 

  Riley Clement

  • Gurobi Staff

  2025年07月22日 01:45

  Hi Salva,

  Is that correctly understood?

  Correct.

  I thought that indicator constraints were use for lazy people that did not want to find appropiate bigM values, but it seems I was wrong, right?

  Also correct.  We are always interested in making things easier for users but this is not the motivation here.

   

  As an experiment, consider this Python snippet:

  m = gp.Model()
  b = m.addVar(vtype="B", name="b")
  x = m.addVar(name="x")
  y = m.addVar(name="y")
  m.addConstr((b==0) >> (x+y == 0))
  m.update()
  m.params.DualReductions=0
  p= m.presolve()
  p.write("presolved.lp")

  Gurobi does not know bounds on x and y and so cannot linearize the indicator constraint.  If you inspect the presolved model in the LP file you will see that it has been translated to a SOS1 constraint, but not translated any further.

  Subject To
  R0: x + y - C2 = 0
  Bounds
  Binaries
  C3
  SOS
  s0:  S1 :: C3:1 C2:2
  End
  

  Now try with very large bounds on x and y, 

  x = m.addVar(ub=1e10, name="x")
  y = m.addVar(ub=1e10, name="y")

  You could manually linearize the indicator yourself, with x + y ≤ 2e10b but you will almost certainly get trickle flow due to the huge big M value of 2e10.  Gurobi avoids this by not translating the SOS1 constraint.  (ignore C2, it is left over from the indicator → SOS translation and would be removed by dual reductions if they were enabled).

  presolved.lp:

  Subject To
   R0: x + y - C2 = 0
  Bounds
   x <= 1e+10
   y <= 1e+10
  Binaries
   C3
  SOS
   s0:  S1 :: C3:1 C2:2
  End

   

  Now try with small bounds on x and y, 

  x = m.addVar(ub=10, name="x")
  y = m.addVar(ub=10, name="y")

  presolved.lp:

  Gurobi will also translate this since the big M is not too big:

  Subject To
  R0: C2 + C3 <= 1
  R1: x + y - 20 C3 <= 0
  Bounds
  x <= 10
  y <= 10
  Binaries
  C2 C3
  End

   

  Now add a constraint x + y ≤ 5 and see how the translation changes:

  m.addConstr(x+y <= 5)

  presolved.lp

  Subject To
   R0: C2 + C3 <= 1
   R1: x + y - 5 C3 <= 0
  Bounds
   x <= 5
   y <= 5
  Binaries
   C2 C3
  End

  - Riley

  0
• 

  spineda

  2025年07月28日 11:21

  • 
  • 
  • 

  Thanks a lot Riley, that example is very illustrative and I finally understand what Gurobi is doing internally. 

  0
• 

  spineda

  2025年07月30日 12:26

  • 
  • 
  • 

  Thanks again. I’ve now run all simulations with the indicator constraints, using the same bounds I had for the other methods, and the results have improved significantly. So it makes more sense to use that as a benchmark for my results.

  While implementing this approach, I came across another question related to my problem. I have the relation y = z * x, where y and x are continuous variables and z is binary. I have bounds for both y and x depending on the value of z, but I also have tighter bounds for x that are only valid when z = 0. Is there a way to include this information directly in Gurobi? Or should I just add another indicator constraint to enforce the tighter bounds when z = 0?

  0
• 

  Riley Clement

  • Gurobi Staff

  2025年07月30日 12:45

  No problem!

  You can use an indicator constraint or you can linearize it yourself with

  x ≤ (1-z) ub_1 + z ub_2

  where ub_1 is the tighter bound, and ub_2 is the looser one.

  0
• 

  spineda

  2025年07月30日 16:39

  • 
  • 
  • 

  Ok, I did that. I was expecting the indicator formulation to consistently outperform the big-M reformulation when using the same bounds, but that’s not always the case. In fact, I implemented three different formulations: the non-linear formulation y = z * x, the indicator formulation (z = 0 ⇒ y = 0, z = 1 ⇒ y = x), and the big-M formulation. Surprisingly, depending on the instance, any of the three can result in the lowest CPU time.

  Maybe my implementation could be optimized further, but I was wondering if this kind of behavior is expected in Gurobi?

  0
• 

  Riley Clement

  • Gurobi Staff

  2025年07月30日 23:09

  Are you comparing each instance with many values of Seed?

  These articles will be of use:

  • Is Gurobi random?
  • What is performance variability?
  • How can I make accurate comparisons? 

   

   

  0
• 

  spineda

  2025年08月01日 13:34

  • 
  • 
  • 

  No, instances differ because some of the parameters are different.

  0

サインインしてコメントを残してください。