4
$\begingroup$

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.

$\endgroup$

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
8
  • 1
    $\begingroup$ I was expecting to see "Benders" in your answer. :) Any reason not to recommend it here? $\endgroup$
    – RobPratt
    May 3, 2022 at 18:36
  • $\begingroup$ Oh, that is great. Let's try Benders decomposition. $\endgroup$
    – Clement
    May 3, 2022 at 19:46
  • 1
    $\begingroup$ @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. :-)] $\endgroup$
    – prubin
    May 3, 2022 at 20:47
  • 1
    $\begingroup$ :) 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. $\endgroup$
    – RobPratt
    May 3, 2022 at 22:16
  • 1
    $\begingroup$ Did he <Benders> cut? Benders decomposed. happyhappybirthday.net/en/age/jacques-f-benders-person_yxfqyyy $\endgroup$ May 3, 2022 at 22:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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