1
$\begingroup$

I want to solve a family of MILP problems (indexed by $k \geq 0$) of the following type:

$$ \begin{align} \max \; c^Tx \;\; s.t. \\ Ax \leq b \\ d^Tx \leq k \end{align} $$

In other words, the problems are the same with the exception of the additional constraint $d^Tx \leq k$. In particular, I want to solve this problem for many values of $k$.

Are there any tricks I could use in order to make this fast?

One possible way would be to add an additional bound for the objective function (based on the previous maximum) as we move from lower $k$ to higher $k$, as these problems are nested. Is there anything else I could do?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ A good search term might be "parametric integer programming." My short answer would be that it depends on what the rest of your problem looks like and how your $d^T x \leq k$ constraint interacts with it. $\endgroup$
    – tmyklebu
    Jan 23, 2015 at 0:32
  • 1
    $\begingroup$ I don't see the integer programming part, are your variables integers? If they are reals, then dual simplex method is the way to go. Dual simplex method is easy to add new constraints, so you start with higher k and add additional ones with lower k each step. If they are integers, you combine the dual simplex method with cutting plane method. $\endgroup$
    – jf328
    Jan 23, 2015 at 9:36
  • $\begingroup$ Ah thanks! Sorry for not being explicit about it, around half of the variables in the $x$ vector are binary variables. So it would probably have to be a hand-crafted solution e.g. using COIN-OR, rather than just using Gurobi or another commercial solver (or possibly by using the low-level interface of the above solvers)? $\endgroup$
    – air
    Jan 23, 2015 at 10:18

1 Answer 1

Reset to default
2
$\begingroup$

If the problems $P_k$ are not too difficult each, I would suggest to solve the problem for the lowest value of $k$ first and use the optimal solution as initial value for the second lowest value of $k$ and so on.

Often, a reasonable starting solution speeds up the solution process of a Branch-And-X a lot. Setting initial values is easy for solvers like CPLEX or Gurobi.

Improve this answer
$\endgroup$

Your Answer

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

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