Infeasibility with MIP problem

77 views
Skip to first unread message

Vusal Babashov

unread,
May 25, 2017, 2:36:45 PM5/25/17
to Gurobi Optimization
Hello,

I am running into infeasible solution for a model with binary and integer decision variables. Model formulation looks feasible mathematically, so there should be no errors. 

However, when I ran the  model.computeIIS(), I get the following (see below), I cannot figure the source of the infeasibility. Is this a numerical error related to integer or binary variables? Your timely feedback/assistance is highly appreciated. 

Regards,

Vusal

----------------------------------------------------------------------------


Parameter UpdateMode unchanged
   Value: 1  Min: 0  Max: 1  Default: 1
Changed value of parameter DualReductions to 0
   Prev: 1  Min: 0  Max: 1  Default: 1
Optimize a model with 338 rows, 198 columns and 1548 nonzeros
Variable types: 6 continuous, 192 integer (66 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+03]
  Objective range  [5e+00, 2e+02]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 1e+03]
Presolve removed 325 rows and 181 columns
Presolve time: 0.00s

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

Solution count 0
Pool objective bound 1e+100

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

Computing Irreducible Inconsistent Subsystem (IIS)...

      Constraints           Bounds       Runtime
     Min       Max       Min      Max
------------------------------------------------
        0      338         0      132         0s
       16       16        10       10         0s

IIS computed: 16 constraints, 10 bounds
IIS runtime: 0.27 seconds

--------------------------------------------------------------

gurobi.log
model1.ilp
model1.lp
model1.mps

Daniel Espinoza

unread,
May 25, 2017, 3:57:31 PM5/25/17
to Gurobi Optimization
Hi Vusal,

Do you know a feasible solution for the IIS? can you share it with us?
Note that even relaxing the integrality requirements on the `general` integer variables (but keeping the binary requirement) still produces and infeasible MIP.
This would be easier to test by solving all 16 LPs with the fixed values for the four remaining binaries.

Best
Daniel



Vusal Babashov

unread,
May 26, 2017, 10:23:02 AM5/26/17
to Gurobi Optimization
Hi Daniel,

I am not sure if this is what you want, but I ran model.feasRelaxS() and re-optimize() I obtain the following the outcome. As you can see, there are some non-integer values.

Regards,

Vusal

----------------------------------------------

Priority1-Day1-Day4(r) -0.0
Priority1-Day1-Day5(r) -0.0
Priority1-Day1-Day6(r) -0.0
Priority1-Day1-Day7(r) -0.0
Priority1-Day1-Day8(r) -0.0
Priority1-Day1-Day9(r) -0.0
Priority1-Day1-Day10(r) -0.0
Priority1-Day2-Day1(r) 7.0
Priority1-Day2-Day2(r) 7.0
Priority1-Day2-Day3(r) 7.0
Priority1-Day2-Day4(r) 4.999999999999998
Priority1-Day2-Day5(r) 4.999999999999998
Priority1-Day2-Day6(r) 4.999999999999998
Priority1-Day2-Day7(r) -0.0
Priority1-Day2-Day8(r) -0.0
Priority1-Day2-Day9(r) -0.0
Priority1-Day2-Day10(r) -0.0
Priority2-Day1-Day1(r) -0.0
Priority2-Day1-Day2(r) -0.0
Priority2-Day1-Day3(r) 1.9999999999999982
Priority2-Day1-Day4(r) 3.0
Priority2-Day1-Day5(r) 9.0
Priority2-Day1-Day6(r) 9.0
Priority2-Day1-Day7(r) 9.0
Priority2-Day1-Day8(r) 9.0
Priority2-Day1-Day9(r) 9.0
Priority2-Day1-Day10(r) 9.0
Priority2-Day2-Day1(r) -0.0
Priority2-Day2-Day2(r) -0.0
Priority2-Day2-Day3(r) 0.0
Priority2-Day2-Day4(r) -0.0
Priority2-Day2-Day5(r) 0.0
Priority2-Day2-Day6(r) 1.0
Priority2-Day2-Day7(r) 1.0
Priority2-Day2-Day8(r) 1.0
Priority2-Day2-Day9(r) 1.0
Priority2-Day2-Day10(r) 1.0
Priority3-Day1-Day1(r) -0.0
Priority3-Day1-Day2(r) -0.0
Priority3-Day1-Day3(r) -0.0
Priority3-Day1-Day4(r) -0.0
Priority3-Day1-Day5(r) -0.0
Priority3-Day1-Day6(r) 0.0
Priority3-Day1-Day7(r) 1.0
Priority3-Day1-Day8(r) 1.0
Priority3-Day1-Day9(r) 1.0
Priority3-Day1-Day10(r) 1.0
Priority3-Day2-Day1(r) -0.0
Priority3-Day2-Day2(r) -0.0
Priority3-Day2-Day3(r) -0.0
Priority3-Day2-Day4(r) 0.0
Priority3-Day2-Day5(r) 0.0
Priority3-Day2-Day6(r) 0.0
Priority3-Day2-Day7(r) -0.0
Priority3-Day2-Day8(r) 6.0
Priority3-Day2-Day9(r) 6.0
Priority3-Day2-Day10(r) 6.0
Priority1-Day1-Day1(w) 1.0
Priority1-Day1-Day2(w) 1.0
Priority1-Day1-Day3(w) 1.0
Priority1-Day1-Day4(w) -0.0
Priority1-Day1-Day5(w) -0.0
Priority1-Day1-Day6(w) -0.0
Priority1-Day1-Day7(w) -0.0
Priority1-Day1-Day8(w) -0.0
Priority1-Day1-Day9(w) -0.0
Priority1-Day1-Day10(w) -0.0
Priority1-Day2-Day1(w) 1.0
Priority1-Day2-Day2(w) 1.0
Priority1-Day2-Day3(w) 1.0
Priority1-Day2-Day4(w) 1.0
Priority1-Day2-Day5(w) 1.0
Priority1-Day2-Day6(w) 1.0
Priority1-Day2-Day7(w) 0.0
Priority1-Day2-Day8(w) -0.0
Priority1-Day2-Day9(w) -0.0
Priority1-Day2-Day10(w) -0.0
Priority2-Day1-Day1(w) -0.0
Priority2-Day1-Day2(w) -0.0
Priority2-Day1-Day3(w) 1.0
Priority2-Day1-Day4(w) 1.0
Priority2-Day1-Day5(w) 1.0
Priority2-Day1-Day6(w) 1.0
Priority2-Day1-Day7(w) 1.0
Priority2-Day1-Day8(w) 1.0
Priority2-Day1-Day9(w) 1.0
Priority2-Day1-Day10(w) 1.0
Priority2-Day2-Day1(w) -0.0
Priority2-Day2-Day2(w) -0.0
Priority2-Day2-Day3(w) 0.0
Priority2-Day2-Day4(w) -0.0
Priority2-Day2-Day5(w) 0.0
Priority2-Day2-Day6(w) 1.0
Priority2-Day2-Day7(w) 1.0
Priority2-Day2-Day8(w) 1.0
Priority2-Day2-Day9(w) 1.0
Priority2-Day2-Day10(w) 1.0
Priority3-Day1-Day1(w) -0.0
Priority3-Day1-Day2(w) -0.0
Priority3-Day1-Day3(w) -0.0
Priority3-Day1-Day4(w) -0.0
Priority3-Day1-Day5(w) -0.0
Priority3-Day1-Day6(w) 0.0
Priority3-Day1-Day7(w) 1.0
Priority3-Day1-Day8(w) 1.0
Priority3-Day1-Day9(w) 1.0
Priority3-Day1-Day10(w) 1.0
Priority3-Day2-Day1(w) -0.0
Priority3-Day2-Day2(w) -0.0
Priority3-Day2-Day3(w) -0.0
Priority3-Day2-Day4(w) 0.0
Priority3-Day2-Day5(w) 0.0
Priority3-Day2-Day6(w) 0.0
Priority3-Day2-Day7(w) -0.0
Priority3-Day2-Day8(w) 1.0
Priority3-Day2-Day9(w) 1.0
Priority3-Day2-Day10(w) 1.0
Priority1-Day1(s) 0.0
Priority1-Day2(s) 0.0
Priority2-Day1(s) 0.0
Priority2-Day2(s) 0.0
Priority3-Day1(s) 0.0
Priority3-Day2(s) 0.0
ArtN_R0 0.0
ArtN_R1 0.0
ArtN_R2 0.0
ArtN_R3 0.0
ArtN_R4 0.0
ArtN_R5 0.0
ArtP_R6 0.0
ArtP_R7 0.0
ArtP_R8 0.0
ArtP_R9 0.0
ArtP_R10 0.0
ArtP_R11 0.0
ArtN_R12 0.0
ArtN_R13 0.0
ArtN_R14 0.0
ArtN_R15 0.0
ArtN_R16 0.0
ArtN_R17 0.0
ArtN_R18 0.0
ArtN_R19 0.0
ArtN_R20 0.0
ArtN_R21 0.0
ArtP_R22 0.0
ArtN_R22 0.0
ArtN_R23 0.0
ArtN_R24 0.0
ArtN_R25 0.0
ArtN_R26 0.0
ArtN_R27 0.0
ArtN_R28 0.0
ArtN_R29 0.0
ArtN_R30 0.0
ArtN_R31 0.0
ArtP_R32 0.0
ArtN_R32 0.0
ArtP_R33 0.0
ArtN_R33 0.0
ArtP_R34 0.0
ArtN_R34 0.0
ArtP_R35 0.0
ArtN_R35 0.0
ArtP_R36 0.0
ArtN_R36 0.0
ArtP_R37 0.0
ArtN_R37 0.0
ArtN_R38 0.0
ArtN_R39 0.0
ArtN_R40 0.0
ArtP_R41 0.0
ArtN_R41 0.0
ArtP_R42 0.0
ArtN_R42 0.0
ArtP_R43 0.0
ArtN_R43 0.0
ArtP_R44 0.0
ArtN_R44 0.0
ArtP_R45 0.0
ArtN_R45 0.0
ArtP_R46 0.0
ArtN_R46 0.0
ArtP_R47 0.0
ArtN_R47 0.0
ArtP_R48 0.0
ArtN_R48 0.0
ArtN_R49 0.0
ArtN_R50 0.0
ArtN_R51 0.0
ArtP_R52 0.0
ArtN_R52 0.0
ArtP_R53 0.0
ArtN_R53 0.0
ArtP_R54 0.0
ArtN_R54 0.0
ArtP_R55 0.0
ArtN_R55 0.0
ArtP_R56 0.0
ArtN_R56 0.0
ArtP_R57 0.0
ArtN_R57 0.0
ArtN_R58 0.0
ArtN_R59 0.0
ArtN_R60 0.0
ArtN_R61 0.0
ArtN_R62 0.0
ArtP_R63 0.0
ArtN_R63 0.0
ArtP_R64 0.0
ArtN_R64 0.0
ArtP_R65 0.0
ArtN_R65 0.0
ArtP_R66 0.0
ArtN_R66 0.0
ArtP_R67 0.0
ArtN_R67 0.0
ArtP_R68 0.0
ArtN_R68 0.0
ArtN_R69 0.0
ArtN_R70 0.0
ArtN_R71 0.0
ArtN_R72 0.0
ArtN_R73 0.0
ArtP_R74 0.0
ArtN_R74 0.0
ArtP_R75 0.0
ArtN_R75 0.0
ArtP_R76 0.0
ArtN_R76 0.0
ArtP_R77 0.0
ArtN_R77 0.0
ArtN_R78 0.0
ArtN_R79 0.0
ArtN_R80 0.0
ArtN_R81 0.0
ArtN_R82 0.0
ArtN_R83 0.0
ArtN_R84 0.0
ArtP_R85 0.0
ArtN_R85 0.0
ArtP_R86 0.0
ArtN_R86 0.0
ArtP_R87 0.0
ArtN_R87 0.0
ArtP_R88 0.0
ArtN_R88 0.0
ArtN_R89 0.0
ArtN_R90 0.0
ArtN_R91 0.0
ArtN_R92 0.0
ArtN_R93 0.0
ArtN_R94 0.0
ArtN_R95 0.0
ArtP_R96 0.0
ArtN_R96 0.0
ArtP_R97 0.0
ArtN_R97 0.0
ArtP_R98 0.0
ArtP_R99 0.0
ArtN_R100 0.0
ArtN_R101 0.0
ArtP_R102 0.0
ArtP_R103 0.0
ArtN_R104 0.0
ArtN_R105 0.0
ArtP_R106 0.0
ArtP_R107 0.0
ArtN_R108 0.0
ArtN_R109 0.0
ArtP_R110 0.0
ArtP_R111 0.0
ArtN_R112 0.0
ArtN_R113 0.0
ArtP_R114 0.0
ArtP_R115 0.0
ArtN_R116 0.0
ArtN_R117 0.0
ArtP_R118 0.0
ArtP_R119 0.0
ArtN_R120 0.0
ArtN_R121 0.0
ArtP_R122 0.0
ArtP_R123 0.0
ArtN_R124 0.0
ArtN_R125 0.0
ArtP_R126 0.0
ArtP_R127 0.0
ArtN_R128 0.0
ArtN_R129 0.0
ArtP_R130 0.0
ArtP_R131 0.0
ArtN_R132 0.0
ArtN_R133 0.0
ArtP_R134 0.0
ArtP_R135 0.0
ArtN_R136 0.0
ArtN_R137 0.0
ArtP_R138 0.0
ArtP_R139 0.0
ArtN_R140 0.0
ArtN_R141 0.0
ArtP_R142 0.0
ArtP_R143 0.0
ArtN_R144 0.0
ArtN_R145 0.0
ArtP_R146 0.0
ArtP_R147 0.0
ArtN_R148 0.0
ArtN_R149 0.0
ArtP_R150 0.0
ArtP_R151 0.0
ArtN_R152 0.0
ArtN_R153 0.0
ArtP_R154 0.0
ArtP_R155 0.0
ArtN_R156 0.0
ArtN_R157 0.0
ArtP_R158 0.0
ArtP_R159 0.0
ArtN_R160 0.0
ArtN_R161 0.0
ArtP_R162 0.0
ArtP_R163 0.0
ArtN_R164 0.0
ArtN_R165 0.0
ArtP_R166 0.0
ArtP_R167 0.0
ArtN_R168 0.0
ArtN_R169 0.0
ArtP_R170 0.0
ArtP_R171 0.0
ArtN_R172 0.0
ArtN_R173 0.0
ArtP_R174 0.0
ArtP_R175 0.0
ArtN_R176 0.0
ArtN_R177 0.0
ArtP_R178 0.0
ArtP_R179 0.0
ArtN_R180 0.0
ArtN_R181 0.0
ArtP_R182 0.0
ArtP_R183 0.0
ArtN_R184 0.0
ArtN_R185 0.0
ArtP_R186 0.0
ArtP_R187 0.0
ArtN_R188 0.9999999999999982
ArtN_R189 0.0
ArtP_R190 0.0
ArtP_R191 0.0
ArtN_R192 0.0
ArtN_R193 0.0
ArtP_R194 0.0
ArtP_R195 0.0
ArtN_R196 0.0
ArtN_R197 0.0
ArtP_R198 0.0
ArtP_R199 0.0
ArtN_R200 0.0
ArtN_R201 0.0
ArtP_R202 0.0
ArtP_R203 0.0
ArtN_R204 0.0
ArtN_R205 0.0
ArtP_R206 0.0
ArtP_R207 0.0
ArtN_R208 0.0
ArtN_R209 0.0
ArtP_R210 0.0
ArtP_R211 0.0
ArtN_R212 0.0
ArtN_R213 0.0
ArtP_R214 0.0
ArtP_R215 0.0
ArtN_R216 0.0
ArtN_R217 0.0
ArtP_R218 0.0
ArtP_R219 0.0
ArtN_R220 0.0
ArtN_R221 0.0
ArtP_R222 0.0
ArtP_R223 0.0
ArtN_R224 0.0
ArtN_R225 0.0
ArtP_R226 0.0
ArtP_R227 0.0
ArtN_R228 0.0
ArtN_R229 0.0
ArtP_R230 0.0
ArtP_R231 0.0
ArtN_R232 0.0
ArtN_R233 0.0
ArtP_R234 0.0
ArtP_R235 0.0
ArtN_R236 0.0
ArtN_R237 0.0
ArtP_R238 0.0
ArtP_R239 0.0
ArtN_R240 0.0
ArtN_R241 0.0
ArtP_R242 0.0
ArtP_R243 0.0
ArtN_R244 0.0
ArtN_R245 0.0
ArtP_R246 0.0
ArtP_R247 0.0
ArtN_R248 0.0
ArtN_R249 0.0
ArtP_R250 0.0
ArtP_R251 0.0
ArtN_R252 0.0
ArtN_R253 0.0
ArtP_R254 0.0
ArtP_R255 0.0
ArtN_R256 0.0
ArtN_R257 0.0
ArtP_R258 0.0
ArtP_R259 0.0
ArtN_R260 0.0
ArtN_R261 0.0
ArtP_R262 0.0
ArtP_R263 0.0
ArtN_R264 0.0
ArtN_R265 0.0
ArtP_R266 0.0
ArtP_R267 0.0
ArtN_R268 0.0
ArtN_R269 0.0
ArtP_R270 0.0
ArtP_R271 0.0
ArtN_R272 0.0
ArtN_R273 0.0
ArtP_R274 0.0
ArtP_R275 0.0
ArtN_R276 0.0
ArtN_R277 0.0
ArtP_R278 0.0
ArtP_R279 0.0
ArtN_R280 0.0
ArtN_R281 0.0
ArtP_R282 0.0
ArtP_R283 0.0
ArtN_R284 0.0
ArtN_R285 0.0
ArtP_R286 0.0
ArtP_R287 0.0
ArtN_R288 0.0
ArtN_R289 0.0
ArtP_R290 0.0
ArtP_R291 0.0
ArtN_R292 0.0
ArtN_R293 0.0
ArtP_R294 0.0
ArtP_R295 0.0
ArtN_R296 0.0
ArtN_R297 0.0
ArtP_R298 0.0
ArtP_R299 0.0
ArtN_R300 0.0
ArtN_R301 0.0
ArtP_R302 0.0
ArtP_R303 0.0
ArtN_R304 0.0
ArtN_R305 0.0
ArtP_R306 0.0
ArtP_R307 0.0
ArtN_R308 0.0
ArtN_R309 0.0
ArtP_R310 0.0
ArtP_R311 0.0
ArtN_R312 0.0
ArtN_R313 0.0
ArtP_R314 0.0
ArtP_R315 0.0
ArtN_R316 0.0
ArtN_R317 0.0
ArtP_R318 0.0
ArtP_R319 0.0
ArtN_R320 0.0
ArtN_R321 0.0
ArtP_R322 0.0
ArtP_R323 0.0
ArtN_R324 0.0
ArtN_R325 0.0
ArtP_R326 0.0
ArtP_R327 0.0
ArtN_R328 0.0
ArtN_R329 0.0
ArtP_R330 0.0
ArtP_R331 0.0
ArtN_R332 0.0
ArtN_R333 0.0
ArtP_R334 0.0
ArtP_R335 0.0
ArtN_R336 0.0
ArtN_R337 0.0

Daniel Espinoza

unread,
May 26, 2017, 11:17:20 AM5/26/17
to Gurobi Optimization
Vusal,

What I'm saying is that the IIS is correct, the problem is indeed infeasible by the combination of the four binary variables.

Best
Daniel

Vusal Babashov

unread,
May 26, 2017, 12:13:33 PM5/26/17
to Gurobi Optimization
Daniel,

I am new to Gurobi and not quite familiar with dealing IIS or feasRelaxS(). Could you please be a little more specific as to what you expect me to share to solve the issue? 

On the other hand, model is feasible with some input parameter values. When the same input parameter value is changed (randomly to other value) model runs into infeasibility. The instance I presented here is infeasible. I can share a feasible instances too.

Vusal

Daniel Espinoza

unread,
May 26, 2017, 12:36:39 PM5/26/17
to Gurobi Optimization
Dear Vusal,

Maybe we are not understanding each other.
Your first message was that a model was declared infeasible when it should not, and I just pointed out that the IIS is actually correct.
Note that MIP infeasibility is different from LP infeasibility.
The IIS you reported is LP-feasible, but there is no combination of values for the binary variables for which the problem is feasible.
what I suggested to `see` this was to try all 16 combinations of values for your four binary variables and see that each resulting LP is indeed infeasible.

I hope this helps
Best
Daniel

Vusal Babashov

unread,
May 31, 2017, 2:19:01 PM5/31/17
to Gurobi Optimization
Hi Daniel,

I would like to follow your suggestion below, but how do you fix value for specific index values of the binary variable (e.g., x[a,b,c]). I know model.addVar() allows you to bound variables for all possible indices, but in this particular case I need to fix value for specific indices. I believe simply hard coding such as x[1,1,3]=1 in Python will not work, as solver will override this during the optimization.

I could not see anything in the reference manual.

Vusal

Daniel Espinoza

unread,
May 31, 2017, 4:07:24 PM5/31/17
to Gurobi Optimization
Dear Vusal,

If you have something like

x = m.addVars(n1,n2,n3,vtype=GRB.BINARY)

then you can fix a given variable a,b,c by 

x[a,b,c].lb = 1
x[a,b,c].ub = 1

Best,
Daniel
Reply all
Reply to author
Forward
0 new messages