17
$\begingroup$

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!?

$\endgroup$
  • $\begingroup$ Would you see node heuristics? Another way to reduce the duality gap at a node (in Branch and Cut method) is to use node heuristics to increase the lower bound. Each time some tree node is processed, we can try to somehow ”round off” a solution to its relaxation LP. $\endgroup$ – A.Omidi Oct 4 '19 at 21:29
14
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I agree with your last point. And then you can in also use the feasible solution in order to temporarily fix most of the variables: initialize the master problem with variables in the feasible solution. $\endgroup$ – Sune Oct 4 '19 at 13:08
  • 3
    $\begingroup$ +1 for trying column generation (branch-price-and-cut). $\endgroup$ – prubin Oct 4 '19 at 20:44
  • $\begingroup$ I can see why this is correct but I was wondering if you could also mention a paper/textbook for citation, perhaps the first paper that introduced/applied this idea (but any citation will do). $\endgroup$ – Opt Oct 5 '19 at 14:11
  • $\begingroup$ I couldn't find the paper that introduces this technique, but I have now added a reference. $\endgroup$ – Rolf van Lieshout Oct 6 '19 at 10:52
13
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I tried to find this in UFLP papers but could not, perhaps I should search more (I also had a look on the book Location Science but could not see this variable fixing). There are so many papers on UFLP and it would be great to mention a paper or textbook for citation. $\endgroup$ – Opt Oct 5 '19 at 14:19
  • 1
    $\begingroup$ Now that you mention it, I know of a reference for a different facility location problem. We also discuss the idea briefly, for UFLP, in our textbook. I'll update the answer to cite both. $\endgroup$ – LarrySnyder610 Oct 5 '19 at 15:27
  • $\begingroup$ In "An aggressive reduction scheme for the simple plant location problem" by Letchford and Miller, they list many reduction rules for the UFLP. Some of them are Lagrangean-based $\endgroup$ – Sune Oct 6 '19 at 14:48
  • $\begingroup$ @Sune Nice finding. $\endgroup$ – Opt Oct 7 '19 at 2:10
3
$\begingroup$

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).

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.