Invited Session Tue.2.H 3003A

Tuesday, 13:15 - 14:45 h, Room: H 3003A

Cluster 5: Constraint programming [...]

CP hybrids for scheduling


Chair: Chris Beck



Tuesday, 13:15 - 13:40 h, Room: H 3003A, Talk 1

Michele Lombardi
Hybrid off-line/on-line workload scheduling via machine learning and constraint programming

Coauthors: Andrea Bartolini, Luca Benini, Michela Milano


Advances in combinatorial optimization in the last decades have enabled their successful application to an extensive number of industrial problems. Nevertheless, many real-world domains are still impervious to approaches such as constraint programming (CP), mathematical programming or metaheuristics. In many cases, the difficulties stem from troubles in formulating an accurate declarative model of the system to be optimized. This is typically the case for systems under the control of an on-line policy: even when the basic rules governing the controller are well known, capturing its behavior in a declarative model is often impossible by conventional means. Such a difficulty is at the root of the classical, sharp separation between off-line and on-line approaches.
In this work, we investigate a general method to combine off-line and on-line optimization, based on the integration of machine learning and combinatorial optimization technology. Specifically, we use an artificial neural network (ANN) to learn the behavior of a controlled system and plug it into a CP model by means of so-called neuron constraints.



Tuesday, 13:45 - 14:10 h, Room: H 3003A, Talk 2

Chris Beck
Loosely coupled hybrids: Tabu search, constraint programming and mixed integer programming for job shop scheduling

Coauthors: Ti K. Feng, Wen-Yang Ku, Jean-Paul Watson


Since their introduction, metaheuristic algorithms have consistently represented the state of the art in solution techniques for the classical job-shop scheduling problem. This dominance is despite the availability of powerful search and inference techniques for scheduling problems developed by the constraint programming (CP) community and substantial increase in the power of commercial mixed integer programming (MIP) solvers. Building on observations of the performance characteristics of metaheuristic, CP, and MIP solvers, we investigate simple, loosely coupled hybrid algorithms for job-shop scheduling. Our hypothesis is that the fast, broad search capabilities of modern tabu search algorithms are able to very quickly converge on a set of very good, but likely sub-optimal, solutions. CP or MIP can then be seeded with these solutions to improve them and search for optimality proofs.



Tuesday, 14:15 - 14:40 h, Room: H 3003A, Talk 3

Thibaut Feydy
Lazy clause generation for RCPSP

Coauthors: Andreas Schutt, Peter Stuckey


Lazy clause generation (LCG) is a recent generic method for solving constraint problems. LCG solvers integrate tightly finite domain propagation (FD) with the conflict analysis features of Boolean satisfaction (SAT) solvers. This technology is often order of magnitudes faster than traditional finite domain propagation on some hard combinatorial problems. In particular, we have used methods based on lazy clause generation to solve the resource constrained project scheduling problem (RCPSP) as well as the more general resource constrained project scheduling problem with generalized precedence relations (RCPSP-Max). These scheduling models have applications areas such as project management and production planning. Our experiments show the benefit of lazy clause generation for finding an optimal solution and proving its optimality in comparison to other state-of-the-art exact and non-exact methods. Our methods is able to find better solution faster on hard RCPSP and RCPSP-Max benchmarks. We were able to close many open problem instances and generates better solutions in most of the remaining instances.


  There are three major facts that should be watched out for in all payday loans in the United States. If you have already decided to take Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.