Skip to main content
main-content

Inhaltsverzeichnis

Frontmatter

Invited Talks

Opt Art

Abstract
Optimization deals with finding the best way to complete a task—creating a schedule for a tournament, matching professors with courses, constructing an itinerary for a traveling salesman. It has been applied successfully to such a great number of diverse disciplines that one could argue that it can be put to good use in every imaginable field. In this talk, we will showcase its amazing utility by describing some applications in the area of art: portraits constructed out of complete sets of dominoes (via integer programming) mosaics comprised of abstract geometric tiles (via integer programming and various heuristics), and continuous line drawings (via the “solution” of large-scale instances of the traveling salesman problem).
Robert Bosch

Planning for Mixed Discrete Continuous Domains

Abstract
Mixed discrete-continuous systems are hybrid systems that exhibit both discrete changes of state, describable in terms of their logical and metric properties, and continuous numeric change describable in terms of differential equations. Continuous change occurs within a state as a consequence of one or more continuous processes being active in that state, whilst discrete change results in state transitions. Such hybrid systems are well-understood in the formal verification and real-time control communities.
Many real planning problems involve interaction with continuously changing values that directly affect both the validity and efficiency of plans. The problem of planning with continuous effects is harder than planning under the assumption of discrete change. The planner must be capable of reasoning about the evolution of continuous processes and their interactions with discrete state changes. For this reason, the standard approach to handling complex continuous effects in planning is to abstract them out of the domain model by lifting the representation to a level where all change can be seen as discrete.
In this talk we discuss progress we have made towards planning in mixed discrete-continuous domains. We begin by arguing that there are problems of critical interest to potential users of planning technology that cannot be adequately modelled under the assumption of discreteness. We then discuss an approach to planning in these domains that relies on the integration of a discrete planner with a continuous non-linear constraint solver. We present some results taken from a range of planning domains featuring continuous change. We discuss the future of this branch of planning and relate our work to the AI and OR literature.
Maria Fox

Duality in Optimization and Constraint Satisfaction

Abstract
We show that various duals that occur in optimization and constraint satisfaction can be classified as inference duals, relaxation duals, or both. We discuss linear programming, surrogate, Lagrangean, superadditive, and constraint duals, as well as duals defined by resolution and filtering algorithms. Inference duals give rise to nogood-based search methods and sensitivity analysis, while relaxation duals provide bounds. This analysis shows that duals may be more closely related than they appear, as are surrogate and Lagrangean duals. It also reveals common structure between solution methods, such as Benders decomposition and Davis-Putnam-Loveland methods with clause learning. It provides a framework for devising new duals and solution methods, such as generalizations of mini-bucket elimination.
J. N. Hooker

Technical Papers

A Totally Unimodular Description of the Consistent Value Polytope for Binary Constraint Programming

Abstract
We present a theoretical study on the idea of using mathematical programming relaxations for filtering binary constraint satisfaction problems. We introduce the consistent value polytope and give a linear programming description that is provably tighter than a recently studied formulation. We then provide an experimental study that shows that, despite the theoretical progress, in practice filtering based on mathematical programming relaxations continues to perform worse than standard arc-consistency algorithms for binary constraint satisfaction problems.
Ionuţ D. Aron, Daniel H. Leventhal, Meinolf Sellmann

Undirected Forest Constraints

Abstract
We present two constraints that partition the vertices of an undirected n-vertex, m-edge graph \({\mathcal{G}}=({\mathcal{V}},{\mathcal{E}})\) into a set of vertex-disjoint trees. The first is the resource-forest constraint, where we assume that a subset \({\mathtt{R}}\subseteq {\mathcal{V}}\) of the vertices are resource vertices. The constraint specifies that each tree in the forest must contain at least one resource vertex. This is the natural undirected counterpart of the tree constraint [1], which partitions a directed graph into a forest of directed trees where only certain vertices can be tree roots. We describe a hybrid-Consistency algorithm that runs in \({\mathop{\cal O}}(m+n)\) time for the resource forest constraint, a sharp improvement over the \({\mathop{\cal O}}(mn)\) bound that is known for the directed case. The second constraint is proper-forest. In this variant, we do not have the requirement that each tree contains a resource, but the forest must contain only proper trees, i.e., trees that have at least two vertices each. We develop a hybrid-Consistency algorithm for this case whose running time is \({\mathop{\cal O}}(mn)\) in the worst case, and \({\mathop{\cal O}}(m\sqrt{n})\) in many (typical) cases.
Nicolas Beldiceanu, Irit Katriel, Xavier Lorca

Allocation, Scheduling and Voltage Scaling on Energy Aware MPSoCs

Abstract
In this paper we introduce a complex allocation and scheduling problem for variable voltage Multi-Processor System-on-Chip (MPSoC) platforms. We propose a methodology to formulate and solve to optimality the allocation, scheduling and discrete voltage selection problem, minimizing the system energy dissipation and the overhead for frequency switching. Our approach is based on the Logic Benders decomposition technique where the allocation is solved through an Integer Programming solver, and the scheduling through a Constraint Programming solver. The two solvers are interleaved and their interaction regulated by cutting plane generation. The objective function depends on both master and sub-problem variables. We demonstrate the efficiency of our approach on a set of realistic instances.
Luca Benini, Davide Bertozzi, Alessio Guerri, Michela Milano

The Range Constraint: Algorithms and Implementation

Abstract
We recently proposed a simple declarative language for specifying a wide range of counting and occurrence constraints. The language uses just two global primitives: the Range constraint, which computes the range of values used by a set of variables, and the Roots constraint, which computes the variables mapping onto particular values. In order for this specification language to be executable, propagation algorithms for the Range and Roots constraints should be developed. In this paper, we focus on the study of the Range constraint. We propose an efficient algorithm for propagating the Range constraint. We also show that decomposing global counting and occurrence constraints using Range is effective and efficient in practice.
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh

On the Separability of Subproblems in Benders Decompositions

Abstract
Benders decomposition is a well-known procedure for solving a combinatorial optimization problem by defining it in terms of a master problem and a subproblem. Its effectiveness relies on the possibility of synthethising Benders cuts (or nogoods) that rule out not only one, but a large class of trial values for the master problem. In turns, this depends on the possibility of separating the subproblem into several subproblems, i.e., problems exhibiting strong intra-relationships and weak inter-relationships. The notion of separation is typically given informally, or relying on syntactical aspects. This paper formally addresses the notion of separability of the subproblem by giving a semantical definition and exploring it from the computational point of view. Several examples of separable problems are provided, including some proving that a semantical notion of separability is much more helpful than a syntactic one. We show that separability can be formally characterized as equivalence of logical formulae, and prove the undecidability of the problem of checking separability.
Marco Cadoli, Fabio Patrizi

A Hybrid Column Generation and Constraint Programming Optimizer for the Tail Assignment Problem

Abstract
Tail Assignment is the problem of assigning flight legs to aircraft while satisfying all operational constraints, and optimizing some objective function. In this article, we present a hybrid column generation and constraint programming solution approach. This approach can be used to quickly produce solutions for operations management, and also to produce close-to-optimal solutions for long and mid term planning scenarios. We present computational results which illustrate the practical usefulness of the approach.
Sami Gabteni, Mattias Grönkvist

The Power of Semidefinite Programming Relaxations for MAX-SAT

Abstract
Recently, Linear Programming (LP)-based relaxations have been shown promising in boosting the performance of exact MAX-SAT solvers. We compare Semidefinite Programming (SDP) based relaxations with LP relaxations for MAX-2-SAT. We will show how SDP relaxations are surprisingly powerful, providing much tighter bounds than LP relaxations, across different constrainedness regions. SDP relaxations can also be computed very efficiently, thus quickly providing tight lower and upper bounds on the optimal solution. We also show the effectiveness of SDP relaxations in providing heuristic guidance for iterative variable setting, significantly more accurate than the guidance based on LP relaxations. SDP allows us to set up to around 80% of the variables without degrading the optimal solution, while setting a single variable based on the LP relaxation generally degrades the global optimal solution in the overconstrained area. Our results therefore show that SDP relaxations may further boost exact MAX-SAT solvers.
Carla P. Gomes, Willem-Jan van Hoeve, Lucian Leahu

Expected-Case Analysis for Delayed Filtering

Abstract
One way to address the tradeoff between the efficiency and the effectiveness of filtering algorithms for global constraints is as follows: Instead of compromising on the level of consistency, compromise on the frequency at which arc consistency is enforced during the search. In this paper, a method is suggested to determine a reasonable filtering frequency for a given constraint.
For dense instances of AllDifferent and its generalization, the Global Cardinality Constraint, let n and m be, respectively, the number of nodes and edges in the variable-value graph. Under the assumption that propagation is random (i.e., each edge removed from the variable-value graph is selected at random), it is shown that recomputing arc consistency only after Θ(m/n) edges were removed results in a speedup while, in the expected sense, filtering effectiveness is comparable to that of enforcing arc consistency at each search step.
Irit Katriel

Plan B: Uncertainty/Time Trade-Offs for Linear and Integer Programming

Abstract
We address the following dilemma: When making decisions in real life, we often face the problem that, while we have time to contemplate about a problem, we are not entirely sure what the exact parameters of our problem will be. And, on the other hand, as soon as the real world is revealed to us, we need to act quickly and have no more time to rethink our actions extensively.
We suggest an approach that allows to trade uncertainty for time and marginal quality loss and discuss its applicability to combinatorial optimization problems that can be formulated as linear and integer linear programs. The core idea consists in solving a polynomial number of problems in the extensive time period before the day of operation, so that, as soon as complete information is available, a feasible near-optimal solution to the problem can be found in sublinear time.
Claire Kenyon, Meinolf Sellmann

Progressive Solutions: A Simple but Efficient Dominance Rule for Practical RCPSP

Abstract
This paper addresses the solution of practical resource-constrained project scheduling problems (RCPSP). We point out that such problems often contain many, in a sense similar projects, and this characteristic can be exploited well to improve the performance of current constraint-based solvers on these problems. For that purpose, we define the straightforward but generic notion of progressive solution, in which the order of corresponding tasks of similar projects is deduced a priori. We prove that the search space can be reduced to progressive solutions. Computational experiments on two different sets of industrial problem instances are also presented.
András Kovács, József Váncza

AND/OR Branch-and-Bound Search for Pure 0/1 Integer Linear Programming Problems

Abstract
AND/OR search spaces have recently been introduced as a unifying paradigm for advanced algorithmic schemes for graphical models. The main virtue of this representation is its sensitivity to the structure of the model, which can translate into exponential time savings for search algorithms. In this paper we extend the recently introduced AND/OR Branch-and-Bound algorithm (AOBB) [1] for solving pure 0/1 Integer Linear Programs [2]. Since the variable selection can have a dramatic impact on search performance, we introduce a new dynamic AND/OR Branch-and-Bound algorithm able to accommodate variable ordering heuristics. The effectiveness of the dynamic AND/OR approach is demonstrated on a variety of benchmarks for pure 0/1 integer programming, including instances from the MIPLIB library, real-world combinatorial auctions and random uncapacitated warehouse location problems.
Radu Marinescu, Rina Dechter

The Timetable Constrained Distance Minimization Problem

Abstract
The Timetable Constrained Distance Minimization Problem is a sports scheduling problem applicable for tournaments where the total travel distance must be minimized. In this paper we define the problem and present an integer programming and a constraint programming formulation for the problem. Furthermore, we describe a hybrid integer programming/constraint programming approach and a branch and bound algorithm for solving the Timetable Constrained Distance Minimization Problem. Finally, the computational performances of the four solution methods are tested and compared.
Rasmus V. Rasmussen, Michael A. Trick

Conflict-Directed A* Search for Soft Constraints

Abstract
As many real-world problems involve user preferences, costs, or probabilities, constraint satisfaction has been extended to optimization by generalizing hard constraints to soft constraints. However, as techniques such as local consistency or conflict learning do not easily generalize to optimization, solving soft constraints appears more difficult than solving hard constraints. In this paper, we present an approach to solving soft constraints that exploits this disparity by re-formulating soft constraints into an optimization part (with unary objective functions), and a satisfiability part. This re-formulation is exploited by a search algorithm that enumerates subspaces with equal valuation, that is, plateaus in the search space, rather than individual elements of the space. Within the plateaus, familiar techniques for satisfiability can be exploited. Experimental results indicate that this hybrid approach is in some cases more efficient than other known methods for solving soft constraints.
Martin Sachenbacher, Brian C. Williams

Event-Driven Probabilistic Constraint Programming

Abstract
Real-life management decisions are usually made in uncertain environments, and decision support systems that ignore this uncertainty are unlikely to provide realistic guidance. We show that previous approaches fail to provide appropriate support for reasoning about reliability under uncertainty. We propose a new framework that addresses this issue by allowing logical dependencies between constraints. Reliability is then defined in terms of key constraints called “events”, which are related to other constraints via these dependencies. We illustrate our approach on two problems, contrast it with existing frameworks, and discuss future developments.
S. Armagan Tarim, Brahim Hnich, Steven D. Prestwich

Online Stochastic Reservation Systems

Abstract
This paper considers online stochastic reservation problems, where requests come online and must be dynamically allocated to limited resources in order to maximize profit. Multi-knapsack problems with or without overbooking are examples of such online stochastic reservations. The paper studies how to adapt the online stochastic framework and the consensus and regret algorithms proposed earlier to online stochastic reservation systems. On the theoretical side, it presents a constant sub-optimality approximation of multi-knapsack problems, leading to a regret algorithm that evaluates each scenario with a single mathematical programming optimization followed by a small number of dynamic programs for one-dimensional knapsacks. On the experimental side, the paper demonstrates the effectiveness of the regret algorithm on multi-knapsack problems (with and without overloading) based on the benchmarks proposed earlier.
Pascal Van Hentenryck, Russell Bent, Yannis Vergados

Traveling Tournament Scheduling: A Systematic Evaluation of Simulated Annealling

Abstract
This paper considers all the variants of the traveling tournament problem (TTP) proposed in [17, 7] to abstract the salient features of major league baseball (MLB) in the United States. The variants include different distance metrics and both mirrored and non-mirrored schedules. The paper shows that, with appropriate enhancements, simulated annealing is robust across the distance metrics and mirroring. In particular, the algorithm matches or improves most best-known solutions and produces numerous new best solutions spread over all classes of problems. The main technical contribution underlying these results is a number of compositive neighborhood moves that aggregate sequences of existing moves; these novel moves preserve the mirroring or distance structure of the candidate schedule, while performing interesting transformations.
Pascal Van Hentenryck, Yannis Vergados

Open Constraints in a Closed World

Abstract
We study domain filtering algorithms for open constraints, i.e., constraints that are not a priori defined on specific sets of variables. We present an efficient filtering algorithm, achieving set-domain consistency, for open global cardinality constraints. We extend this result to conjunctions of them, in case they are defined on disjoint sets of variables. We also analyze the case when the sets of variables may overlap. As establishing set-domain consistency is NP-complete in that case, we propose a weaker, though efficient, filtering algorithm instead. Finally, we extend our results to conjunctions of similar open constraints.
Willem-Jan van Hoeve, Jean-Charles Régin

Conditional Lexicographic Orders in Constraint Satisfaction Problems

Abstract
The lexicographically-ordered CSP (“lexicographic CSP” for short) combines a simple representation of preferences with the feasibility constraints of ordinary CSPs. Preferences are defined by a total ordering across all assignments, such that a change in assignment to variable k is more important than any change in assignment to any variable that comes after it in the ordering. In this paper, we show how this representation can be extended to handle conditional preferences. This can be done in two ways. In the first, for each conditional preference relation, the parents have higher priority than the children in the original lexicographic ordering. In the second, the relation between parents and children need not correspond to the basic ordering of variables. For problems of the first type, any of the algorithms originally devised for ordinary lexicographic CSPs can also be used when some of the domain orderings are dependent on the assignments to “parent” variables. For problems of the second type, algorithms based on lexical orders can be used if the representation is augmented by variables and constraints that link preference orders to assignments. In addition, the branch-and-bound algorithm originally devised for ordinary lexicographic CSPs can be extended to handle CSPs with conditional domain orderings.
Richard J. Wallace, Nic Wilson

An Efficient Hybrid Strategy for Temporal Planning

Abstract
Temporal planning (TP) is notoriously difficult because it requires to solve a propositional STRIPS planning problem with temporal constraints. In this paper, we propose an efficient strategy for solving TP, which combines, in an innovative way, several well established and studied techniques in AI, OR and constraint programming. Our approach integrates graph planning (a well studied planning paradigm), max-SAT (a constraint optimization technique), and the Program Evaluation and Review Technique (PERT), a well established technique in OR. Our method first separates the logical and temporal constraints of a TP problem and solves it in two phases. In the first phase, we apply our new STRIPS planner to generate a parallel STRIPS plan with a minimum number of parallel steps. Our new STRIPS planner is based on a new max-SAT formulation, which leads to an effective incremental learning scheme and a goal-oriented variable selection heuristic. The new STRIPS planner can generate optimal parallel plans more efficiently than the well-known SATPLAN approach. In the second phase, we apply PERT to schedule the activities in a parallel plan to create a shortest temporal plan given the STRIPS plan. When applied to the first optimal parallel STRIPS plan, this simple strategy produces optimal temporal plans on most benchmarks we have tested. This strategy can also be applied to optimal STRIPS plans of different parallel steps in an anytime fashion to find an optimal temporal plan. Our experimental results show that the new strategy is effective and the resulting algorithm outperforms many existing temporal planners.
Zhao Xing, Yixin Chen, Weixiong Zhang

Improved Algorithm for the Soft Global Cardinality Constraint

Abstract
We propose two algorithms achieving generalized arc consistency for the soft global cardinality constraint with variable-based violation and with value-based violation. They are based on graph theory and their complexity is \(O(\sqrt{n}m)\) where n is the number of variables and m is the sum of the cardinalities of the domains. They improve previous algorithms that ran respectively in O(n(m+nlog n)) and O((n+k)(m+nlog n)) where k is the cardinality of the union of the domains.
Alessandro Zanarini, Michela Milano, Gilles Pesant

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise