3
$\begingroup$

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
$\endgroup$

1 Answer 1

2
$\begingroup$

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:

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.

$\endgroup$
3
  • $\begingroup$ Dear @sascha, many thanks for sharing your insight. Let me explain more about what I did. I have tried to solve a scheduling problem that is a variant of resource-constrained scheduling. The problem contains binary and also positive variables. Actually, the main duty of the binary variables is by assigning tasks to compute the interval variables. (positive variables in my case). As an idea, if I can estimate the domain of the interval variables, actually the best estimate as you mentioned too, it seems can improve significantly the solving process. $\endgroup$
    – A.Omidi
    Commented Jun 26, 2023 at 6:23
  • $\begingroup$ Now, to estimate the interval variables domain and also based on the graph algorithms, a heuristic manner can estimate these domains very efficiently. In some cases actually, the optimal/global solution. I should note, the problem is written in an algebraic modeling language and already is solved by either CPLEX or SCIP by fixing the interval variables domain. (whose LB and UB fix on the values that are provided by a heuristic manner). $\endgroup$
    – A.Omidi
    Commented Jun 26, 2023 at 6:24
  • $\begingroup$ As far as I see the domain propagation can actually be implied in integer programs. If I understand correctly, also based on your answer, it is possible to apply this method even on the positive variables. (please, correct me if I am wrong). For my second question, I think Heuristic shrinking paragraph can answer that. Would you please, more elaborate on your last sentence in the Heuristic shrinking paragraph and also the last part of your answer? Also, what does exactly Shaving mean as I never see that? $\endgroup$
    – A.Omidi
    Commented Jun 26, 2023 at 6:34

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.