Avoid infeasibility in “fixed MIP problem” in CPLEX

Question

I would like to find dual values and reduced costs after solving a MIP problem using CPLEX. IBM's solution in this case is to fix the integer variables to create a “fixed MIP problem”, then solve this continuous problem and obtain the duals and reduced costs from that.

I do this by using the following commands in the CPLEX Interactive Optimizer:

set timelimit 1200
set threads 1
read /tmp/tmpu8f4obrb.pyomo.lp
optimize
change problem fix
optimize
write /tmp/tmp55qy8xe5.cplex.sol

This works well for my problems most of the time, but sometimes the first optimization stage will reach the time limit and return an integer feasible solution, but then the second stage will report infeasibility, e.g., Infeasibility row 'c_u_x495386_': 0 <= -0.00011798.

I'm assuming this occurs because the initial solution isn’t quite integral, and then in the second stage CPLEX finds a constraint where one now-fixed variable is supposed to match up with another now-fixed variable or expression, and it doesn't quite work. (This is my assumption, but I could be wrong...)

So my question is, are there settings I can adjust for the first optimization to get a “more integral” solution or for the second optimization to tolerate the non-integrality of the first solution?

UPDATE:

Looking a little deeper, I find that the infeasible constraint has the form commit_amount <= 1505.86 * is_committed. In this problem, commit_amount is a continuous variable that is separately constrained to equal 150.586 * unit_size, where unit_size is a general integer variable. is_committed is a binary variable. In the incumbent solution (before changing to a fixed mip), commit_amount = 0 and is_committed = -7.8347247411958421e-08. So when the integer variables are fixed, this constraint becomes 0 <= 1505.86 * -7.8347247411958421e-08 or 0 <= -0.00011798.

So my original intuition seems to be right: in the initial optimization, CPLEX has set the binary variable is_committed to a small negative value. Then, when the integer variables are fixed at the incumbent values, the problem becomes infeasible. But I don't know how to get the second stage to solve under these conditions.

Answer 1

The second-stage infeasibility arises because the original MIP solution from CPLEX is technically infeasible.

My best guess is that there are 3 things at play here: CPLEX' primal tolerance, integrality tolerance, and internal presolve/rescaling. The last one matters because, as I explain below, tolerances are typically applied on the presolved, rescaled problem (not necessarily the one you gave to CPLEX).

1. The integrality tolerance $\epsilon_{i}$ (default value $10^{-5}$) means that a binary variable that takes value, e.g., $0 \pm \epsilon$, is treated as binary-feasible by CPLEX. You can change the value of $\epsilon_{i}$ via the "Integrality tolerance" parameter in CPLEX.

2. CPLEX also has some tolerance $\epsilon_{p}$ (default value $10^{-6}$) on primal constraint violation. This means that a constraint $a^{T}x = b +\pm \epsilon_{p}$ will be treated as non-violated. You can also tighten that, via CPLEX' "feasibility tolerance" parameter

3. Before solving the problem, CPLEX applies presolve, and will re-scale the problem to make more numerically stable. This is an internal procedure. Typically, the above tolerances apply to the scaled model, not the original one.

In the example you gave, and for the MIP solution you report, the constraint commit_amount <= 1505.86 * is_committed is violated by roughly $10^{-4}$, which is above the default feasibility tolerance of $10^{-6}$. What likely happened is that, in the initial MIP solve, this constraint was rescaled to, e.g., 0.001 * commit_amount <= 1.50586 * is_committed, in which case the violation becomes $\simeq 10^{-7}$, which CPLEX would consider feasible.

To get rid of the infeasibility issue in your second stage, you could try:

• tighten CPLEX' tolerances in the initial MIP solve, e.g., $10^{-8}$ feasibility and $10^{-8}$ integrality tolerances. This will reduce the likelyhodd of CPLEX returning a solution that's technically infeasible, but it will likely increase solution time (impossible to know by much unless you try it out).
• slightly relax the constraints in the second stage solve, to further reduce the risk of infeasibility. For instance, relax each inequality constraint by something like $10^{-6}$ before solving for the second time.
• play with CPLEX's scale parameter as well, though it's usually better to keep this to default.

Answer 2

Based on your update, you might try the following in lieu of "change problem fix": change the bounds of the integer variables to equal the feasible solution, then solve the resulting LP problem. For instance, you would set the lower and upper bounds of is_committed to 0, and do the same for commit_amount. It's more tedious than tightening the tolerance parameters but perhaps a bit more reliable.