6

I have a MILP model that solves a master production schedule including capacity decisions. In the model I have a production quantity that should either be 0 or at least the amount that can be produced in one shift (or half shift), i.e., a minimium production quantity. Right now this is modeled using two variables, one binary and one continuous.

The actual implementation right now is done with Google's or-tools which doesn't support semi-continuous variables, so I can't easily test this out. I would need to rewrite the whole model using a solver specific API and that would take quite some time.

The model is solved in about 24h (with a reasonable gap remaining), it has more than 100,000 rows, 150,000 columns, and 600,000 non-zeros. Due to this "minimum quantity" I have about 28,000 binary variables in the model and without it there would be only a handful (basically choosing between different capacity levels). I tried removing the minimum quantity restriction (and thus those binary variables) and the model is solved in 2-3h to optimality.

Would the use of semi-continuous variables instead of the binary-continuous pair allow the model to be solved faster than using two variables? Are there any examples that show this difference in similar sized dimensions?

Andreas
  • 313
  • 1
  • 6
  • Would you ask just about the variable type changing or you would like to reduce the solving time? – A.Omidi Oct 23 '20 at 19:42
  • I want the model to be solved faster and thus I wanted to know whether adding semi-continuous variables in place of the binary-continuous variable pair could be expected to have an impact – Andreas Oct 24 '20 at 05:41
  • For the first part, the excellent answer of Dr 4er would be interested. About the second part to reduce the solving time, would you try using the state-of-art solvers to do that? have you tried to feed a warm-start solution to your model by heuristic methods which are frequently used in industries like calculating master schedule by using MRP to initialize a prior solution? might be some constraints interpreted as the lazy to reduce the solution space? – A.Omidi Oct 24 '20 at 06:03

1 Answers1

8

A solver may branch directly on the semi-continuous variables, or may transform each one to an equivalent formulation using a continuous variable and a binary variable (like you have now). Either way, the solver must deal with the same number of discrete variables that require branching.

One solver might do better with your continuous+binary formulation (perhaps because you know better bounds on the variables than the solver can deduce). Another solver might do better with the semi-continuous formulation, by taking advantage of its special structure.

Additionally, any results with mixed-integer programming tend to be highly problem-specific. Although a given formulation and/or solver may be superior for your problem, it may well be inferior for someone else's problem that has a different structure.

The upshot of all this is that the only way to be sure what works best is to run some tests. If you are writing directly to solver APIs, then that will mean programming more than one version of your model.

4er
  • 628
  • 3
  • 6
  • Thanks. I know that this is highly model dependent, but comparing models that have been solved with the same solver we should be able to draw conclusion on the merits of these variables, at least for that solver. – Andreas Oct 24 '20 at 05:48