Why does PuLP send two distinct steps of commands to the CPLEX_CMD solver for solving MILPs?

[twissocq]

Hello,

When using the CPLEX_CMD solver (i.e., without relying on the CPLEX API), I noticed a peculiar behavior in how it handles MILP problems. Three commands are sent to cplex : mipopt, change problem fixed and finally optimize.

See on file cplex_apy.py starting at line 97

if lp.isMIP():
      if self.mip:
            cplex_cmds += "mipopt\n"
            cplex_cmds += "change problem fixed\n"
      else:
      cplex_cmds += "change problem lp\n"
cplex_cmds += "optimize\n"
cplex_cmds += "write " + tmpSol + "\n"
cplex_cmds += "quit\n"

If self.mip is True, then we run mipopt (line 97) then optimize (at line 103).
To my knowledge, when using the official cplex python api, (with solver= CPLEX_PY()), only a single solve is performed.

My questions are:

• What is the purpose of running a second optimization after fixing the integer variables (with change problem fixed)?
• Does this double optimization have any significant impact on performance or the final solution accuracy?
• Are there historical or technical reasons for this specific behavior in PuLP with CPLEX_CMD?

Thank you in advance for any insights!

[pchtsp]

That's a very good question. These commands have been there for a long time and the CPLEX_CMD has always solved the problem once (except very weird unexplained cases). Do you have a reference URL that clearly shows which options to send to CPLEX in each case? I see https://www.ibm.com/docs/en/cofz/12.10.0?topic=optimizer-invoking-mip-model and https://www.ibm.com/docs/en/cofz/12.10.0?topic=cplex-table-commands-interactive-optimizer but the documentation is not very explicit.

Would you care to make a PR? Unfortunately we do not have CPLEX set up in the github CI so there's no way to easily test the differences though. If you know of a way to add cplex to the github CI that would be welcome too!

[twissocq]

Thanks, Franco, for your answer.
The optimize command is only for LP, mipopt is the good command for MILP. (if you try use the optimize command, cplex optimizer will fail)

After exploring the links you provided, especially here: IBM Documentation: Working with a fixed MIP problem, there could be a benefit from this approach, when we need access to dual information.
Therefore, I think it’s best not to modify the code.

Regarding GitHub CI with CPLEX:

For cplex_py(), there’s a Python package available on PyPI: https://pypi.org/project/cplex/. Maybe you could give it a try?
For cplex_cmd(), honestly, I’m not sure.

[orxfun]

Firstly, thanks a lot for this library with an expressive syntax.

And thanks for asking the exact question I have @twissocq :) and providing the links to recommendations.

I see the benefit but I think I receive misleading results on the solution status due to the second run. Please let me know if I am missing something.

The Problem

I experienced this while working with CPLEX and a mip model. I have a timelimit, say 600 sec. And the solver cannot find the optimal solution within the timelimit. I have used CPLEX_CMD to set the timelimit.

As far as I understand from the def actualSolve(self, lp): function of "pulp/apis/cplex_api.py", this generates the following commands:

read model.lp
set timelimit 600
mipopt
change problem fixed
optimize
write solution.txt

First Part

The first three lines initiates and solves the mip, finalizing with the following log:

     29    10   1.91922e+07   716   2.83468e+07   1.90921e+07    97974   32.65%
     30     3   1.91225e+07   914   2.83468e+07   1.90921e+07    97193   32.65%

Clique cuts applied:  2
Cover cuts applied:  93
Implied bound cuts applied:  3618
Flow cuts applied:  33
Mixed integer rounding cuts applied:  1108
Zero-half cuts applied:  15
Gomory fractional cuts applied:  2

Root node processing (before b&c):
  Real time             =  509.42 sec. (416797.53 ticks)
Parallel b&c, 32 threads:
  Real time             =   95.44 sec. (36098.25 ticks)
  Sync time (average)   =   43.66 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =  604.86 sec. (452895.78 ticks)

Solution pool: 59 solutions saved.

MIP - Time limit exceeded, integer feasible:  Objective =  2.8346776142e+07
Current MIP best bound =  1.9092290418e+07 (gap = 9.25449e+06, 32.65%)
Solution time =  605.24 sec.  Iterations = 112537  Nodes = 31 (32)
Deterministic time = 452901.98 ticks  (748.31 ticks/sec)

So far so good, I get an integer feasible solution with 32.65% gap.

Second Part

But then, the execution continues with:

change problem fixed
optimize

This gives the following

MILP problem relaxed to LP with fixed integer variables using
incumbent solution.

CPXPARAM_TimeLimit                               600
Parallel mode: deterministic, using up to 32 threads for concurrent optimization:
 * Starting dual Simplex on 1 thread...
 * Starting Barrier on 30 threads...
 * Starting primal Simplex on 1 thread...
Tried aggregator 1 time.
LP Presolve eliminated 4073937 rows and 2166795 columns.
All rows and columns eliminated.
Presolve time = 1.75 sec. (1965.77 ticks)

Dual simplex solved model.


Dual simplex - Optimal:  Objective =  2.8346776142e+07
Solution time =    6.54 sec.  Iterations = 0 (0)
Deterministic time = 3745.14 ticks  (573.04 ticks/sec)

Final Status

And the final status of the execution is Optimal although this is not the integer optimal solution. Without looking into the logs (which I didn't at first:), this is misleading. Please let me know if I am missing something.

Question

• Why do we have the change problem fixed and optimize commands automatically added? Since CPLEX_CMD provides us the flexibility to add these commands whenever we need, I was not expecting this behavior. Whenever we need the dual information, we can explicitly add these commands, rather than being implicitly inserted.
• Isn't this misleading to receive the final status from the "relaxed to LP with fixed integer variables" problem?