Variable fixing based on a good feasible solution

Question

Suppose you have a combinatorial optimization problem that is formulated as a mixed integer linear program (minimization). The problem size is denoted $n$ and the expected $n$ is around $100$. The integer program has $O(n^5)$ variables and $O(n^2)$ constraints and its LP relaxation bound is very good. We also have a very good feasible solution that is at most $1$-$5\%$ far from optimal.

The issue is that there are so many variables and it takes so much run-time even for the LP-relaxation. I was wondering how we could fix some of the decision variables given the feasible solution. We do not have the lower bound at the beginning so it cannot be used. I know that MIP solvers have their own preprocessing, but this can happen only after the LP is loaded to the memory which is an issue by itself.

What do you suggest? Are you aware of any reference or paper in which the knowledge of having a good upper bound is used to fix the decision variables of an optimization problem?

I think my question is essentially reduced to the following:

For a combinatorial optimization problem, how can we obtain a non-trivial lower bound on the optimal objective value given a good feasible solution!?

Answer 1

As far as I know, it is not possible to fix any variables solely based on a feasible solution without compromising the exactness of your solution method. However, variable fixing is possible when you have both an upper bound and a lower bound on the optimal objective value, using a method called reduced cost fixing (see e.g. Atamtürk, Nemhauser & Savelsbergh (1996)).

For example, consider the problem $\min \left\{cx: Ax\leq b, x\in \{0,1\}^n\right\}$ and let $LB$ and $UB$ denote a known lower and upper bound, respectively. Let $\bar{c_j}$ denote the reduced cost of variable $x_j$ in the optimal solution of the linear relaxation. Then, if $LB+c_j\geq UB$, there exists an optimal solution where $x_j=0$, so this variable can be fixed to 0. It is possible to generalize this method to integer variables.

In your problem, perhaps it would be worthwhile to investigate whether you can solve the linear relaxation using column generation, where negative reduced costs variables (columns) are added on the fly. This avoids having to add all $O(n^5)$ variables to the model. Once you have solved the linear relaxation, you could fix all variables using your good feasible solution using the method I explained above, and solve the remaining problem as a mixed-integer programming problem.

Answer 2

A similar idea as suggested by @ RolfvanLieshout uses Lagrangian duals instead of LP duals, in a Lagrangian-based branch-and-bound scheme. For example, in the uncapacitated fixed-charge location problem (UFLP), the most common Lagrangian approach relaxes the assignment constraints ($\sum_j y_{ij} = 1 \ \forall i$), uses the Lagrangian subproblem to calculate a "benefit" $\beta_j$ for each facility $j$, and then opens facility $j$ if $\beta_j + f_j < 0$ (where $f_j$ is the fixed cost).

Now, if we have a lower bound $z_{LR}(\lambda)$ for a particular vector $\lambda$ of Lagrange multipliers, and we have an upper bound $\text{UB}$ from a feasible solution, then we can say:

• If $x_j=0$ in the optimal solution to the subproblem under $\lambda$ and $$ z_{LR}(\lambda) + \beta_j + f_j > \text{UB},$$ then $x_j=0$ in every optimal solution to the UFLP.
• If $x_j=1$ in the optimal solution to the subproblem under $\lambda$ and $$ z_{LR}(\lambda) - (\beta_j+f_j) > \text{UB},$$ then $x_j=1$ in every optimal solution to the UFLP.

The basic idea is that we are "peeking" down the branch-and-bound tree from the root node. If $x_j=0$ and we branch on $x_j$, then when we set $x_j=1$ in the child node, the new lower bound will be $z_{LR}(\lambda) + \beta_j + f_j$. If this is $>\text{UB}$, then we'd fathom that node, so we can just fix $x_j=0$. A similar argument applies for the second case.

This idea is used by Daskin, et al. (2002) for a location–inventory model. We also discuss the idea (in the context of UFLP) in our textbook, 2nd edition, Section 8.2.3.7.

Answer 3

You could try loading the problem through AMPL. AMPL is blazing fast so size won't be an issue, and it has its own presolve, which is very good. I've seen it reduce problems from 100Kx100K to 5Kx5K. The way you would use this would be to use AMPL to produce an .nl file which is a dense format to describe the presolved model. You can then load that .nl file very quickly to any solver that supports ASL.

If you don't have/don't want to use AMPL, you could try (i) coding some size reduction algorithms yourself to reduce the size of your model, or (ii) getting a cheap lower bound by running a constraint propagation algorithm on your MILP. The latter is the most promising, just be aware that constraint propagation algorithms are notoriously hard to code correctly (numerics-wise).