|
Constraint Logic Programming and Integer Programming (CLP)
Organiser:
Paul Williams
Southampton University
The CLP session at OR41 will focus on the relation between IP and CLP. It will be followed on Friday by the inaugural meeting of th UK Constraints Network (see ConsNeT-99)
|
Logical Reduction of Integer Programmes in General Integer Variables
John Wilson
Loughborough University
ID: CLP1(CLP5t)
, last change v10
,
Thur
(Session 1)
09:00-09:25
, place:E2
Abstract: Most developments at the logic/integer programming interface involve {0,1} variables. This paper will consider some generalisations of results from the {0,1} perspective to more general integer variables. It will be shown that certain {0,1} results are particular cases of more general results. Problem reduction and cut generation will be considered from both a logic and linear programming point of view and linked with other work on detection of valid inequalities. From the computational work presented some evidence of the effectiveness of the procedures will be provided.
Integer Programming and Constraint Logic Programming - The Scope for hybrid solvers
ID: CLP2(CLP3t)
, last change v21
,
Thur
(Session 1)
09:30-09:55
, place:E2
Extra Equipment: Data Projector
Abstract: Integer Programming and Constraint Logic Programming are two alternative approaches for solving combinatorial optimisation problems. Both techniques can claim individual successes but practical experience indicates that neither approach dominates the other in terms of computational performance. The development of a hybrid solver that captures the best features of both would appear to offer scope for improved overall performance. The issue of communication between different modelling paradigms is discussed and a number of applications with different characteristics are examined. Computational experience of both individual techniques as well as various hybrid configurations is reported.
Keynote: Integrating Solution Methods in a Modeling Language
John Hooker
Carnegie Mellon University
ID: CLP3(CLP1t)
, last change v10
,
Thur
(Session 2)
11:15-12:10
, place:E2
Abstract: Constraint satisfaction and optimization methods can be viewed as emphasizing complementary aspects of a single underlying methodology. Several efforts to combine them are underway. This talk reports on the progress of one such effort that retains the declarative nature of mathematical programming. The structure of the modeling language itself indicates how optimization and constraint satisfaction methods should interact to solve the problem. It represents joint work with Hak-Jin Kim, Greger Ottosson and Erlendur Thorsteinsson.
The Modelling of Constraint Logic Programming Predicates by Integer Programming
Paul Williams
Southampton University
ID: CLP4(CLP2t)
, last change v10
,
Thur
(Session 2)
12:15-12:40
, place:E2
Abstract: Constraint Logic Programming (CLP) offers a flexible and compact way of modelling many combinatorial problems. Integer Programming (IP) is a powerful tool for solving them if they are formulated in the best way. A number of the most commonly used predicates in CLP such as all_different, if_then, at_least etc will be considered from this point of view. If possible the convex hull representation of them will be given. It will be shown that the use of an integer presolve routine in conjunction with good IP formulations can be as effective as CLP methods.
Designing an Open Interface for Hooking Constraint Logic Programming Solvers to an Algebraic Modeling Language
ID: CLP5(RFDG1)
, last change v10
,
Thur
(Session 3)
13:45-14:10
, place:E2
Abstract: Combinatorial modeling language extensions motivated by constraint logic programming methods are valuable to modelers, but introduce new difficulties in maintaining an open interface that can accommodate a variety of current and future solvers. We describe several representation and recognition issues that arise in extending the interface of the AMPL language.
The Optimization Programming Language OPL
Pascal Van Hentenryck
Brown University
ID: CLP6(CLP7t)
, last change v10
,
Thur
(Session 3)
14:15-14:40
, place:E2
Abstract: OPL is a modeling language that attempts to enhance traditional modeling languages from mathematical programming with constraint programming notations and algorithms and the ability to define search procedures and strategies at a high level. The novel modeling tools include higher-order constraints, logical combinations of constraints, arrays indexed by expressions containing variables, global constraints, as well as specific support for scheduling and resource allocation applications. The talk reviews these features in detail and illustrates them on combinatorial optimization problems.
Modeling and Solving Problems in Constraint-Based Scheduling
Wim Nuijten
ILOG France
ID: CLP7(CLP4t)
, last change v23
,
Thur
(Session 3)
14:45-15:10
, place:E2
Extra Equipment: data projector
Abstract: Since the early 90's, constraint-based scheduling has had a growing success both in theory and in practice. In this presentation a short introduction to constraint-based scheduling is given in which the principles of the area are explained. After that we will give a general description of the kind of problems that are studied. These problems will be used to discuss one of the main reasons for the success of constraint-based scheduling, being its flexible modeling and solving capabilities. We will also pay attention to another important component: the integration of efficient propagation algorithms. Computational results on well-known theoretical problems like the Job Shop Scheduling Problem are presented as well as examples of successful industrial applications.
Hybridisation of CP and LP: To Duplicate or to Delegate?
ID: CLP8(CLP8t)
, last change v17
,
Thur
(Session 3)
16:30-16:55
, place:E2
Keywords: constraints, hybrid algorithms, rescheduling, benchmarks
Abstract: In this talk we shall assume that constraints involving discrete variables can be handled by constraint propagation (CP), or by linear relaxation (LP), or both. We will focus on optimisation problems, where search is performed by depth-first branch and bound. This type of hybridisation is easy to express and brings significant benefits in efficiency, scalability and robustness on many problem classes. A straightforward hybrid algorithm handles all such constraints by BOTH methods. Each constraint is automatically duplicated across the two constraint handlers. This algorithm proves its robustness on several different variations of the "hoist scheduling" problem.
Another hybridisation delegates some of the constraints to LP and some to CP. However constraints handled by the different methods may share variables, which allows the LP and CP handlers to communicate with each other. Moreover the set of constraints handled by the different methods may change during search. We present an algorithm of this kind which efficiently solves rescheduling problems.
Both these problem classes have been published as benchmark sets, and to our knowledge the presented algorithms are the best for each class.
© 1999 McKinnon/Archibald/Grothey Edinburgh University. (v26t, html_genr v27, cgi v6) email: Organisers
