9
$\begingroup$

In Constraint Programming it is possible to use interval variables to represent intervals of time during which something happens (see here), usable in scheduling problems, for example.

Is there something similar in MIP? I am aware of some modeling approaches in MIP using binary variables to represent the order of jobs on a machine (i.e. $y_{ij}$ equal to 1 if job $i$ is worked before job $j$), but I was wondering whether other modeling approaches referring to intervals exist in MIP.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
7
$\begingroup$

There is no single entity in MIP modeling that is a direct analog of an interval variable. The general MIP approach is as follows:

  1. discretize the time domain (which is inherent in CP models using interval variables);
  2. in lieu of a single interval variable, create a binary variable for each possible starting time and add a constraint setting the sum of those variables equal to 1 (so that you start at exactly one time epoch) or less than equal to 1 (so that you start once or not at all -- the analog to an optional interval variable);
  3. use a constraint to define the ending time (a continuous variable) in terms of the processing time/interval width plus the starting time (an expression using those binary variables);
  4. handle non-overlap requirements using constraints (involving all those binary variables) that say one interval either starts after the other ends or ends before the other starts.

In modeling terms, it's a bigger PITA than expressing the same concepts in a CP model ... but it is doable.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Regarding point 3, is there a particular reason to define the ending time rather than the starting time? I have seen a couple of papers doing this, but I don't understand whether is conventional or there is a benefit out of it. $\endgroup$
    – Libra
    Dec 9, 2019 at 6:52
  • $\begingroup$ It's not either-or; I assumed you already had variables for start times and was suggesting adding variables for end times. They are not necessary, but they make the non-overlap constraints easier to read (and possibly less susceptible to input error). $\endgroup$
    – prubin ♦
    Dec 10, 2019 at 16:41
6
$\begingroup$

To complete @Marco Lübbecke said, There are many scheduling problems which use binary and continuous variables to represent the interval of time. For instance, machine scheduling problems use such a method to calculate the intervals. (start time or compilation time.)

If you are interested to develop a MIP formulation, I recommended some references like:

A) Scheduling (Theory, Algorithms, and Systems)

B) Scheduling in Supply Chains Using Mixed Integer Programming

It should be noted that MIPs are usually NP-hard (They are difficult to solve), specifically in the real world situation even by using some commercial solvers like CPLEX or GUROBI, for large-scale models.

However, some useful approaches such as constraint programming (CP) can be applied to solve large-scale problems in a reasonable and efficient way.

Improve this answer
$\endgroup$
6
$\begingroup$

The vehicle routing problem with time windows is the first problem that comes to my mind, well researched, highly applicable. There are usually continuous variables that represent the visit (or start of service) time of a vehicle at a customer; that time must fall into a time window, which is an interval.

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.