# Trying to accelerate MILP solution

I developed a mathematical model that contains several thousand of binary variables (in addition to several thousand continuous variables).

The binary variables model different things, say $$X(i)$$, $$Y(j)$$, $$Z(k)$$, ... I made the observation, that if I fix the binaries of type $$X(i)$$ to their optimal value (even a subset of those) and optimize for the rest of the variables then I obtain the optimal solution to the problem very fast. Without this fixing, the solution time is very long.

The problem is that for a new setting of the problem, I don't know the optimal values $$X(i)$$.

Does anyone have an idea of how I could exploit the knowledge that if I get the optimal values for $$X(i)$$ the problem becomes easy?

I tried setting high branching priorities for the $$X(i)$$ variables but this doesn't really help. Optimizing only for $$X(i)$$ doesn't help either.

You could try the cut-and-solve-method proposed by Climer and Zhang 2006. The idea is roughly as follows

1. Somehow guess a good cut, that will limit the freedom of the $$X$$ variables.
2. After guessing such a cut, you solve to optimality the problem defined by the feasible set removed by the cut.
3. If this reduced problem has a feasible solution, it will give you a primal bound. Update best primal if necessary.
4. Then you add the cut to your original problem, and obtain a dual bound for this modified problem.
5. Now test if $$(\text{best primal bound} - \text{dual bound})\leq 0$$ (minimization case). If so, you have solved your problem to optimality. Otherwise go back to 1.

The method is described in Figure 4 of the linked paper. I have had good luck using this method for problems where the problem after reducing the wiggle room of the $$X$$-variables is significantly easier to solve, than the original full problem.

The idea is somewhat similar to local branching.

First, knowing that fixing $$X$$ makes solution faster may not give you any leverage whatsoever. Consider a MIP model with binary variables $$X$$ and all other variables continuous. If you fix $$X$$ at optimal values, the rest is an LP that solves quickly. That fact tells you nothing about how to fix the values of $$X.$$

Second, high branching priorities for $$X$$ is a sound thing to try. The fact that it didn't help means either (a) the solver is already prioritizing branching on $$X$$, (b) branching on $$X$$ does not immediately result in much pruning of nodes or (c) both.

Hypothetically there might be a way to combine prioritization of $$X$$ with something else, but that would be model-specific, so not something easily suggested with what we have to go on.

• I was expecting to see "Benders" in your answer. :) Any reason not to recommend it here? Commented May 3, 2022 at 18:36
• Oh, that is great. Let's try Benders decomposition. Commented May 3, 2022 at 19:46
• @RobPratt Are you thinking Benders with a MIP subproblem ($X$ in the master; $Y$, $Z$ etc. in the subproblem)? [Also, I gave Benders a couple of days off, since he's been working so hard lately. :-)]
– prubin
Commented May 3, 2022 at 20:47
• :) Yes, hard to tell without seeing the full model. Maybe we are lucky and the problem structure is such that integrality of $X$ automatically implies integrality of the other variables, as I saw in a recent project. @Clement please update your question with more details of the model. Commented May 3, 2022 at 22:16
• Did he <Benders> cut? Benders decomposed. happyhappybirthday.net/en/age/jacques-f-benders-person_yxfqyyy Commented May 3, 2022 at 22:57