Meaning of the domain propagation in the context of mixed-integer programming

Question

In the literature, domain propagation defines the process of inferring sequences of local domain reductions at the current node of the branch-and-bound tree. The goal is to shrink the size of the current sub-problem as much as possible at an affordable computational cost. (references mentioned at the end). Also, it is often more known in constraint programming than MILPs.

However, this approach has often been used in the context of integer programming (IP) where the domain of the variables is limited and also can be estimated in prior. Now suppose we have a mixed-integer program, specifically a scheduling problem, with a mix of the binary (assigning) and positive (intervals) variables.

My questions are:

• Is it possible to apply domain propagation to the positive variables of the MIP? (If so):

• If one can make a good domain for the interval variables (also known as the start and end time of each task) by using some heuristic approaches, then fixing these time intervals in the domain window of the interval variables, can this be a domain reduction/propagation? Or just is a domain prediction?

References:

1. Shift-And-Propagate by T BERTHOLD
2. Rounding and Propagation Heuristics for Mixed Integer Programming

Answer 1

Overview

I think the canonical resource to this topic is:

Achterberg, Tobias. Constraint integer programming. Diss. 2007.

Example Code

As this basiclly describes the theory behind the open-source MILP solver:

• SCIP (nowadays more than MILP)

it's not surprising, that there are some rather complex applications of constraint-propagation, even related to scheduling, where things get complex very fast because CP community introduced lots of very powerful propagation-mechanisms.

See for example:

• /src/scip/cons_cumulative.h

and

Heinz, Stefan, Wen-Yang Ku, and J. Christopher Beck. "Recent improvements using constraint integer programming for resource allocation and scheduling." Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems: 10th International Conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18-22, 2013. Proceedings 10. Springer Berlin Heidelberg, 2013.

(it's more than "just" propagation however: e.g. conflict-analysis)

Further applications

So yes... You can add domain-propagation to MILP (if the solver is extensible enough).

One direction, related to scheduling and probably to your example domain, which i never saw in code, but which seems like a good idea to me (depending on the problem to solve of course) would be introducing the domain-propagation of Simple Temporal Networks, for which bounded incremental algorithms are available (as propagation from scratch is equivalent to the all-pairs shortest-paths problem: rather expensive).

I'm pretty sure, "IBM ILOG CP optimizer for scheduling" does exactly this and more, which is indicated in:

Laborie, Philippe, et al. "IBM ILOG CP optimizer for scheduling: 20+ years of scheduling with constraints at IBM/ILOG." Constraints 23 (2018): 210-250.

Keep in mind, that this software seems to be a hybrid of CP and MILP (although the how / tightness of this integration is hard to estimate as it's commercial software).

Remarks about heuristics

If heuristics are compatible with domain-propagation surely depends on details.

In CP and CIP (Constraint Integer-Programming) community, i'm pretty sure the following (in absense of a better-suited resource) holds:

Lagerkvist, Mikael Zayenz, and Magnus Rattfeldt. "Half-checking propagators." arXiv preprint arXiv:2007.05423 (2020).

"Propagators are required to be correct; they must never remove a value from a variable that may still be a solution to the constraint. This means that propagation is not actually concerned with finding a solution but about proving that no solution exists for a certain variable-value pair, which is a subjectively harder problem."

So everything happening during domain-propagation basically assume a closed-world model (current domain state, current constraint-state) and one has to be careful about the implications.

Heuristic shrinking

If you shrink domains by heuristics and continue, the solver surely can exploit follow-up domain-propagation much more heavily and speed up reasoning / local optimization. But you lost global-optimality of course (as you assumed something without knowing if you are right). This sounds like something focused on the generation of "fast good solutions". In some sense, one might see this as primal-heuristic (which afaik in SCIP can be interleaved with constraint-propagation).

There is probably a lot possible in this direction although semantics might deviate a lot!

If you are able to do state-restoration / backtracking, you can embed this in some outer tree such that you don't lose global-optimality.

Something similar and yet very different

There might be a connection to the concepts of: probing (in MP / CIP community) or singleton arc-consistency / shaving (CP community) although i fail to "build a bridge".

Shaving is actually something very popular in scheduling applications, but shaving (as i understood it) is solely used to refute parts of the search-space which is pretty much the oppositve of our above "fast good solution" approach.