Project B25

Scheduling Techniques in Constraint Integer Programming

DFG Research Center Matheon Technische Universität Berlin
Duration: July 2010 - December 2010
Project heads: Rolf H. Möhring
Researcher: Jens Schulz
Support: DFG Research Center "Mathematics for Key Technologies" (Matheon)

Project description.


Scheduling problems belong to the most widely studied optimization problems due to their practical relevance. Only few special cases are solvable in polynomial time. A very hard and general problem is the resource-constrained project scheduling problem (RCPSP), where even practical instances with 60 jobs cannot be solved to optimality. Besides heuristics, several exact approaches have been developed usually using branch-and-bound algorithms combined with constraint programming, integer programming or techniques from satisfiability testing. Also hybrid approaches are known like the Australian G12-project (using a hybrid of constraint programming and a SAT solver) who currently report best results. In accordance to these results it is a logical next step to additionally integrate techniques from integer programming into such a framework, i.e., Lagrangean relaxation and cutting plane algorithms. The aims are on the one hand, to improve the solving process and to obtain better lower and upper bounds on general instance sets PSPLib , and on the other hand, to evaluate the impact of these techniques on the solving process.

In Matheon Project B20 the branch-cut-and-price framework SCIP is developed further. SCIP combines constraint programming, integer programming and techniques from statisfiability testing in one solver. Recently, in a research collaboration between our group and B20, we started integrating first scheduling specific techniques into SCIP, among them a primal heuristic, a propagator and two constraint handlers. Our work [2] shows good results for a general class of scheduling problems. It turned out that

(a) conflict analysis drastically reduces the search space with low computational efforts,

(b) lower bounds from LP are very helpful in pruning the search tree, but lead to high computation times, and

(c) some propagation algorithms are not suited for an efficient conflict analysis in the framework since they perform a set of reductions at once and do not use the bound changes found therein.

Research program

To focus our activities during the six months, we will concentrate on the followig topics:

1. Implementational issue:
The use of Lagrangean relaxation and combinatorial algorithms to obtain lower bounds more efficiently.
In case of the RCPSP, the Lagrangean relaxation yields a minimum cut problem which can be solved efficiently and is thus more likely to generate lower bounds faster than by solving the LP relaxation. Since this approach is embedded in a branch-and-bound process, different techniques might be applied in the subgradient method and after propagations or branching decisions have been applied. Furthermore, it should be evaluated whether updating cost-coefficients rather than solving from scratch reduces the computation times and by how much. Right now, SCIP does not support relaxators to be plugins, as needed in this approach. Efforts are made at ZIB to enhance the framework with such plugins and we will closely cooperate. The constraint handlers developed within this project will serve as a problem specific case study.
2. Experimental issue:
An evaluation of the tradeoff between fast but incomplete propagations with easy conflict analysis and slow but powerful propagations neglecting conflict analysis -- to this end technique specific propagation and repropagation algorithms need to be developed and analyzed.
3. Theoretical issue:
A study of the complexity of computing conflict sets of minimum or small size.
Conflict analysis bases on the idea of finding minimum explanations why a domain of a variable has been reduced by a propagation algorithm. Typically, such an explanation is a set of variables and their bounds that led to the domain reduction. A brute force approach is to rerun the propagation algorithm and to filter some explanation if possible. Since explanations have to be performed for each infeasible node in the search tree on a path from the infeasible node back to the root, these repropagation algorithms are performed very often at higher nodes during search. Thus, they have to be highly efficient, i.e., they have to be fast and they have to report sets of minimum size. Suited algorithms need to be developed. In case of edge-finding algorithms or the concept of core-times the complexity of computing an explanation of minimum size needs to be clarified.


[1] N. Megow, R.H. Möhring and J. Schulz.
Decision Support and Optimization in Shutdown and Turnaround Scheduling.
To appear in Informs Journal on Computing 2010
[2] T. Berthold, S. Heinz, M.E. Lübbecke, R.H. Möhring and J. Schulz.
A Constraint Integer Programming Approach for Resource-Constrained Project Scheduling.
Proceedings of CPAIOR 2010.
[3] T. Berthold, S. Heinz and J. Schulz.
An Approximative Criterion for the Potential of Energetic Reasoning.
Technical Report 2010.


Within Matheon: B24, B20 (ZIB).