Forum Discussion

FICO's avatar
FICO
Community Manager
3 years ago

Infeasible model after consecutive invocation

We have the following workflow implemented in Java with Xpress 9.2.2 8.14.5:

1. Build BCL MIP model

2. Fix subset of variables (xprbVar.fix(.)). This simplified model is referred to as model A

3. Load model into optimizer (xprb.loadMat())

4. Solve model A (xprsProb.mipOptimize();) 

5. Unfix variables from step 2 (xprbVar.setLb(.), xprbVar.setUb(.)), thereby obtaining the original model. We refer to this model as model B

6. Load model into optimizer (xprb.loadMat())

7. Solve model B. If model A produced a feasible solution, we use this as a warmstart for B (xprb.loadMIPSol(mipSolution.x, true)). 

When executing this workflow, we ran into the following issue.

For a particular instance, model A is infeasible due to the variable fixing, but a solution exists to model B. When we execute the above workflow, this is what happens:

1. Model A returns infeasible (as expected)

2. Model B returns infeasible (not expected!):

Minimizing MILP LTLN using up to 8 threads and up to 15GB memory, with these control settings:
MAXTIME = -3600
MIPLOG = 3
THREADS = -1
MIPRELSTOP = .05
Original problem has:
      8258 rows         5407 cols        32026 elements      5403 globals
       850 delrows
Presolved problem has:
      3111 rows         3446 cols        14066 elements      3446 globals
      2642 delrows
LP relaxation tightened
Presolve finished in 0 seconds
Heap usage: 4527KB (peak 8518KB, 8219KB system)
 
Coefficient range                    original                 solved        
  Coefficients   [min,max] : [ 2.38e-04,  3.38e+05] / [ 5.95e-05,  2.00e+00]
  RHS and bounds [min,max] : [ 1.00e+00,  3.36e+04] / [ 4.05e-02,  6.20e+01]
  Objective      [min,max] : [ 1.00e+00,  1.00e+00] / [ 2.50e-01,  5.06e+03]
Autoscaling applied standard scaling
 
Will try to keep branch and bound tree memory usage below 4.4GB
Primal starts after 0 seconds
Crash basis containing 558 structural columns created
 
   Its         Obj Value      S   Ninf  Nneg        Sum Inf  Time
     0       66090.81967      p      9    30       7.882812     0
    19       66123.04311      p      5     0       5.000000     0
Problem is infeasible
 *** Search completed ***

Since this code is part of a large application, it's quite a challenge to create a small reproducible example. I however tried the following:

- when exporting model B after it is deemed infeasible, and running the exported lp or mps file through the interactive optimizer, the model solves correctly as expected.

- when searching for an IIS after model B was deemed infeasible, it doesn't seem to find an IIS:

General IIS
 
Problem is MIP feasible
 *** Search unfinished ***    Time:     0 Nodes:          1

- disabling the presolve (xprs.setIntControl(XPRS.PRESOLVE,0) seems to resolve the issue, i.e. model A is still infeasible as expected, but model B now correctly produces a solution.

 My suspicion is that the presolve eliminates some variables when solving model A. Then, after unfixing some variables and invoking solve again (model B), those variables that were eliminated by the presolve during the first invocation are still absent. This would be strange though, since xprb.loadMat() is invoked before every call to mipOptimize to ensure that the new updated variable domains are taken into account.

 Any suggestions on how to further troubleshoot this issue? Ideally I would prefer not to disable the presolve.

2 Replies

  • FICO's avatar
    FICO
    Community Manager

    First of all, I suggest to export the models to LP files and compare them, just to be sure that the changes are indeed what you suspect them to do. I.e., do XPRBprob.getXPRSprob().writeProb("stage.lp", "l").

    I suggest to do that in three different points:

    1. For the original model (model1.lp)
    2. After fixing the variables and calling loadmat (model2.lp)
    3. After unfixing the variables and calling loadmat (model3.lp)

    model1.lp and model3.lp should be the same.

    Then, when analyzing model B (model3.lp) instead of setting PRESOLVE=0 you could play with the PRESOLVEOPS control to figure out whether this can be blamed easily on a particular reduction.

    I am not sure I understood correctly: are you saying that model B is found infeasible only if it is solved right after model A in your application but when solved standalone then it is found feasible? In particular, if you solve the original model before even creating model B, is that found feasible?

    Could you share the offending model? If not here, then maybe by email? Preferably as a file created by XPRBprob.getXPRSprob().saveAs(...) right before solving model B. That might tell whether there is something bad "left" from solving A in the model state.

  • FICO's avatar
    FICO
    Community Manager

    As per your instructions, I created the 3 exports (model1.lp, model2.lp, model3.lp). Model1.lp and model3.lp are indeed identical. Model2.lp indeed has a subset of variables fixed. I can solve each of these LPs through the interactive optimizer, and the results are as expected: Model1.lp and Model3.lp produce a feasible solution, Model2.lp is infeasible.

    I am not sure I understood correctly: are you saying that model B is found infeasible only if it is solved right after model A in your application but when solved standalone then it is found feasible? In particular, if you solve the original model before even creating model B, is that found feasible?

    That is correct. In fact, if I disable steps 2, 3, 4 and 5 in the above workflow, and hence solve the original model with no variables fixed then I obtain a correct, feasible solution.

    I played around with the PRESOLVEOPS parameters but was unable to find a combination of parameters that allowed me to solve model B correctly. Only setting PRESOLVE=0 allows me to solve model B (I did not attempt an exhaustive search over all 2^19 PRESOLVE parameter combinations..).

    I also tried inserting the following lines right before invoking xprs.mipOptimize("p"):

    xprsProb.writeProb(config.OUTPUT_DIRECTORY+"/"+solveInstanceName, "l");
     
    xprsProb.readProb(config.OUTPUT_DIRECTORY+"/"+solveInstanceName, "v");

    This simply writes the problem to a file, and immediately reads the same file again. This solves the issue, i.e. model A is again infeasible, and model B produces a feasible solution. Also adding the following 2 lines right before invoking mipOptimize solves the problem:

    xprsProb.saveAs(config.OUTPUT_DIRECTORY+"/"+instanceName);
    xprsProb.restore(config.OUTPUT_DIRECTORY+"/"+instanceName);

    I've email the requested svf to you ([email protected])