4

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.

SecretAgentMan
  • 1,895
  • 2
  • 13
  • 39
Clement
  • 2,252
  • 7
  • 13

2 Answers2

4

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.

Sune
  • 6,457
  • 2
  • 17
  • 31
3

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.

prubin
  • 39,078
  • 3
  • 37
  • 104
  • 1
    I was expecting to see "Benders" in your answer. :) Any reason not to recommend it here? – RobPratt May 03 '22 at 18:36
  • Oh, that is great. Let's try Benders decomposition. – Clement May 03 '22 at 19:46
  • 1
    @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 May 03 '22 at 20:47
  • Yes, $X$ in master because fixing it makes the problem easy. (Also, did you really give him time off, or did he cut?) – RobPratt May 03 '22 at 20:56
  • The reason I didn't recommend (generalized) Benders with a MIP subproblem is that the cuts you generate from a MIP subproblem tend not to be particularly tight (although, as with anything MIP-ish, I'm sure there are exceptions). So I'm not sure generalized Benders would lead to faster convergence of $X$ than just giving $X$ top branching priority would. (And puns like that are likely to earn you cutting remarks.) – prubin May 03 '22 at 22:02
  • 1
    :) 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. – RobPratt May 03 '22 at 22:16
  • 1
    Did he cut? Benders decomposed. https://happyhappybirthday.net/en/age/jacques-f-benders-person_yxfqyyy – Mark L. Stone May 03 '22 at 22:57
  • Hi Rob! I was away for a few weeks not working on anything, thus the late reply. The variables X(i,j) model tasks i on machines j [X(i,j)=1 if i on j is performed, 0 otherwise], variables Z(i,j,i1,j1) model precedence relations among these tasks (if task i1 on machine j1 precedes task i2 on machine j2 then Z(i1,j1,i2,j2) = 1 else 0. There is no way that integrality of X implies integrality of Z. It is advantageous to first branch on variables X. Cplex supports only continuous subproblems. So, the attempt to use Benders has failed. – Clement May 30 '22 at 20:25