A new constraint test-case generator and the importance of hybrid optimizers

In the past decade, significant progress has been made in understanding problem complexity of discrete constraint problems. In contrast, little similar work has been done for constraint problems in the continuous domain. In this paper, we study the complexity of typical methods for non-linear constraint problems and present hybrid solvers with improved performance. To facilitate the empirical study, we propose a new test-case generator for generating non-linear constraint satisfaction problems (CSPs) and constrained optimization problems (COPs). The optimization methods tested include a sequential quadratic programming (SQP) method, a penalty method with a fixed penalty function, a penalty method with a sequence of penalty functions, and an augmented Lagrangian method. For hybrid solvers, we focus on the form that combines two or more optimization methods in sequence. In the experiments, we apply these methods to solve a series of continuous constraint problems with increasing constraint-to-variable ratios. The test problems include artificial benchmark problems from the test-case generator and problems derived from controlling a hyper-redundant modular manipulator. We obtain novel results on complexity phase transition phenomena of the various methods. Specifically, for constraint satisfaction problems, the SQP method is the best on weakly constrained problems, whereas the augmented Lagrangian method is the best on highly constrained ones. Although the static penalty method performs poorly by itself, by combining it with the SQP method, we show a hybrid solver that is significantly better than any of the individual methods on problems with moderate to large constraint-to-variable ratios. For constrained optimization problems, the hybrid solver obtains much better solutions than SQP, while spending comparable amount of time. In addition, the hybrid solver is flexible and can achieve good results on time-bounded applications by setting parameters according to the time limits.     

LocalSolver 1.x: a black-box local-search solver for 0-1 programming

This paper introduces LocalSolver 1.x, a black-box local-search solver for general 0-1 programming. This software allows OR practitioners to focus on the modeling of the problem using a simple formalism, and then to defer its actual resolution to a solver based on efficient and reliable local-search techniques. Started in 2007, the goal of the LocalSolver project is to offer a model-and-run approach to combinatorial optimization problems which are out of reach of existing black-box tree-search solvers (integer or constraint programming). Having outlined the modeling formalism and the main technical features behind LocalSolver, its effectiveness is demonstrated through an extensive computational study. The version 1.1 of LocalSolver can be freely downloaded at and used for educational, research, or commercial purposes.     

Constraint programming-based column generation

This paper surveys recent applications and advances of the constraint programming-based column generation framework, where the master subproblem is solved by traditional OR techniques, while the pricing subproblem is solved by constraint programming (CP). This framework has been introduced to solve crew assignment problems, where complex regulations make the pricing subproblem demanding for traditional techniques, and then it has been applied to other contexts. The main benefits of using CP are the expressiveness of its modeling language and the flexibility of its solvers. Recently, the CP-based column generation framework has been applied to many other problems, ranging from classical combinatorial problems such as graph coloring and two dimensional bin packing, to application oriented problems, such as airline planning and resource allocation in wireless ad hoc networks.      

Generating hard instances for robust combinatorial optimization

While research in robust optimization has attracted considerable interest over the last decades, its algorithmic development has been hindered by several factors. One of them is a missing set of benchmark instances that make algorithm performance better comparable, and makes reproducing instances unnecessary. Such a benchmark set should contain hard instances in particular, but so far, the standard approach to produce instances has been to sample values randomly from a uniform distribution.In this paper we introduce a new method to produce hard instances for min-max combinatorial optimization problems, which is based on an optimization model itself. Our approach does not make any assumptions on the problem structure and can thus be applied to any combinatorial problem. Using the Selection and Traveling Salesman problems as examples, we show that it is possible to produce instances which are up to 500 times harder to solve for a mixed-integer programming solver than the current state-of-the-art instances.     

A fix-and-optimize matheuristic for university timetabling

University course timetabling covers the task of assigning rooms and time periods to courses while ensuring a minimum violation of soft constraints that define the quality of the timetable. These soft constraints can have attributes that make it difficult for mixed-integer programming solvers to find good solutions fast enough to be used in a practical setting. Therefore, metaheuristics have dominated this area despite the fact that mixed-integer programming solvers have improved tremendously over the last decade. This paper presents a matheuristic where the MIP-solver is guided to find good feasible solutions faster. This makes the matheuristic applicable in practical settings, where mixed-integer programming solvers do not perform well. To the best of our knowledge this is the first matheuristic presented for the University Course Timetabling problem. The matheuristic works as a large neighborhood search where the MIP solver is used to explore a part of the solution space in each iteration. The matheuristic uses problem specific knowledge to fix a number of variables and create smaller problems for the solver to work on, and thereby iteratively improves the solution. Thus we are able to solve very large instances and retrieve good solutions within reasonable time limits. The presented framework is easily extendable due to the flexibility of modeling with MIPs; new constraints and objectives can be added without the need to alter the algorithm itself. At the same time, the matheuristic will benefit from future improvements of MIP solvers. The matheuristic is benchmarked on instances from the literature and the 2nd International Timetabling Competition (ITC2007). Our algorithm gives better solutions than running a state-of-the-art MIP solver directly on the model, especially on larger and more constrained instances. Compared to the winner of ITC2007, the matheuristic performs better. However, the most recent state-of-the-art metaheuristics outperform the matheuristic.     

A Declarative Modeling Framework that Integrates Solution Methods

Constraint programming offers modeling features and solution methods that are unavailable in mathematical programming but are often flexible and efficient for scheduling and other combinatorial problems. Yet mathematical programming is well suited to declarative modeling languages and is more efficient for some important problem classes. This raises this issue as to whether the two approaches can be combined in a declarative modeling framework. This paper proposes a general declarative modeling system in which the conditional structure of the constraints shows how to integrate any “checker” and any special-purpose “solver”. In particular this integrates constraint programming and optimization methods, because the checker can consist of constraint propagation methods, and the solver can be a linear or nonlinear programming routine.     

Towards a practical engineering tool for rostering

The profitability and morale of many organizations (such as factories, hospitals and airlines) are affected by their ability to schedule their personnel properly. Sophisticated and powerful constraint solvers such as ILOG, CHIP, ECLiPSe, etc. have been demonstrated to be extremely effective on scheduling. Unfortunately, they require non-trivial expertise to use. This paper describes ZDC-rostering, a constraint-based tool for personnel scheduling that addresses the software crisis and fills a void in the space of solvers. ZDC-rostering is easier to use than the above constraint-based solvers and more effective than Microsoft’s Excel Solver. ZDC-rostering is based on an open-source computer-aided constraint programming package called ZDC, which decouples problem formulation (or modelling) from solution generation in constraint satisfaction. ZDC is equipped with a set of constraint algorithms, including Extended Guided Local Search, whose efficiency and effectiveness have been demonstrated in a wide range of applications. Our experiments show that ZDC-rostering is capable of solving realistic-sized and very tightly-constrained problems efficiently. ZDC-rostering demonstrates the feasibility of applying constraint satisfaction techniques to solving rostering problems, without having to acquire deep knowledge in constraint technology.     

Combining the Scalability of Local Search with the Pruning Techniques of Systematic Search

Systematic backtracking is used in many constraint solvers and combinatorial optimisation algorithms. It is complete and can be combined with powerful search pruning techniques such as branch-and-bound, constraint propagation and dynamic variable ordering. However, it often scales poorly to large problems. Local search is incomplete, and has the additional drawback that it cannot exploit pruning techniques, making it uncompetitive on some problems. Nevertheless its scalability makes it superior for many large applications. This paper describes a hybrid approach called Incomplete Dynamic Backtracking, a very flexible form of backtracking that sacrifices completeness to achieve the scalability of local search. It is combined with forward checking and dynamic variable ordering, and evaluated on three combinatorial problems: on the n-queens problem it out-performs the best local search algorithms; it finds large optimal Golomb rulers much more quickly than a constraint-based backtracker, and better rulers than a genetic algorithm; and on benchmark graphs it finds larger cliques than almost all other tested algorithms. We argue that this form of backtracking is actually local search in a space of consistent partial assignments, offering a generic way of combining standard pruning techniques with local search.     

Constraint satisfaction problems: Algorithms and applications

A constraint satisfaction problem (CSP) requires a value, selected from a given finite domain, to be assigned to each variable in the problem, so that all constraints relating the variables are satisfied. Many combinatorial problems in operational research, such as scheduling and timetabling, can be formulated as CSPs. Researchers in artificial intelligence (AI) usually adopt a constraint satisfaction approach as their preferred method when tackling such problems. However, constraint satisfaction approaches are not widely known amongst operational researchers. The aim of this paper is to introduce constraint satisfaction to the operational researcher. We start by defining CSPs, and describing the basic techniques for solving them. We then show how various combinatorial optimization problems are solved using a constraint satisfaction approach. Based on computational experience in the literature, constraint satisfaction approaches are compared with well-known operational research (OR) techniques such as integer programming, branch and bound, and simulated annealing.     

A structure-conveying modelling language for mathematical and stochastic programming

We present a structure-conveying algebraic modelling language for mathematical programming. The proposed language extends AMPL with object-oriented features that allows the user to construct models from sub-models, and is implemented as a combination of pre- and post-processing phases for AMPL. Unlike traditional modelling languages, the new approach does not scramble the block structure of the problem, and thus it enables the passing of this structure on to the solver. Interior point solvers that exploit block linear algebra and decomposition-based solvers can therefore directly take advantage of the problem’s structure. The language contains features to conveniently model stochastic programming problems, although it is designed with a much broader application spectrum.     

Analyzing infeasible nonlinear programs

Nonlinear optimizers often report infeasibility during the process of initial construction of a model, or alterations to an existing model. Because solvers are unable to decide feasibility of a nonlinear constraint set with perfect accuracy, there are numerous possible explanations: the physical model really is infeasible, there is an error in the nonlinear constraint set causing infeasibility, or the model is feasible but the initial point or solver parameters are poorly chosen. It is difficult to proceed to a diagnosis of the problem in a large NLP.This paper presents an algorithm providing automated assistance in analyzing infeasible NLPs. The deletion filtering algorithm isolates a Minimal Intractable Subsystem (MIS) of constraints, a minimal set of constraints which appears infeasible to the solver given a specified initial point and parameter settings. The MIS may be as small as a few constraints from among the very much larger set defining the original model, and helps to focus the examination, thereby speeding the diagnosis. A computer tool embodying the algorithm, LSGRG (MIS), is developed and applied to demonstration examples.     

A variable neighborhood search based matheuristic for nurse rostering problems

A practical nurse rostering problem, which arises at a ward of an Italian private hospital, is considered. In this problem, it is required each month to assign shifts to the nursing staff subject to various requirements. A matheuristic approach is introduced, based on a set of neighborhoods iteratively searched by a commercial integer programming solver within a defined global time limit, relying on a starting solution generated by the solver running on the general integer programming formulation of the problem. Generally speaking, a matheuristic algorithm is a heuristic algorithm that uses non trivial optimization and mathematical programming tools to explore the solutions space with the aim of analyzing large scale neighborhoods. Randomly generated instances, based on the considered nurse rostering problem, were solved and solutions computed by the proposed procedure are compared to the solutions achieved by pure solvers within the same time limit. The results show that the proposed solution approach outperforms the solvers in terms of solution quality. The proposed approach has also been tested on the well known Nurse Rostering Competition instances where several new best results were reached.     

Enhancing CP-based column generation for integer programs

This is a summary of the author’s Ph.D. thesis supervised by Federico Malucelli and defended on 15 May 2008 at the Politecnico di Milano. The thesis is written in English and is available from the author upon request. This work presents new methods for enhancing the Column Generation approach based on Constraint Programming when it is used for solving combinatorial optimization problems. The methods proposed focus on the interactions between the linear programming solver and the constraint programming solver, and on how they impact on both a single iteration and the overall execution of the Column Generation procedure. The result of this work is the design and implementation of general-purpose optimization algorithms, whose efficiency is proven by solving two very different problems: the Minimum Graph Coloring Problem and a resource allocation problem arising in Wireless Ad Hoc Networks.     

SCIP: solving constraint integer programs

Constraint integer programming (CIP) is a novel paradigm which integrates constraint programming (CP), mixed integer programming (MIP), and satisfiability (SAT) modeling and solving techniques. In this paper we discuss the software framework and solver SCIP (Solving Constraint Integer Programs), which is free for academic and non-commercial use and can be downloaded in source code. This paper gives an overview of the main design concepts of SCIP and how it can be used to solve constraint integer programs. To illustrate the performance and flexibility of SCIP, we apply it to two different problem classes. First, we consider mixed integer programming and show by computational experiments that SCIP is almost competitive to specialized commercial MIP solvers, even though SCIP supports the more general constraint integer programming paradigm. We develop new ingredients that improve current MIP solving technology. As a second application, we employ SCIP to solve chip design verification problems as they arise in the logic design of integrated circuits. This application goes far beyond traditional MIP solving, as it includes several highly non-linear constraints, which can be handled nicely within the constraint integer programming framework. We show anecdotally how the different solving techniques from MIP, CP, and SAT work together inside SCIP to deal with such constraint classes. Finally, experimental results show that our approach outperforms current state-of-the-art techniques for proving the validity of properties on circuits containing arithmetic.      

A logic language for combinatorial optimization

CHIP (Constraint Handling In Prolog) is a new logic programming language combining the declarative aspect of logic programming for stating search problems with the efficiency of constraint handling techniques for solving them. CHIP has been applied to many real-life problems in Operations Research and hardware design with an efficiency comparable to specific programs written in procedural languages. The main advantage of CHIP is the short development time of the programs and their great modifiability and extensibility. In this paper, we discuss the application of the finite domain part of CHIP to the solving of discrete combinatorial problems occurring in Operations Research. The basic mechanisms underlying CHIP are explained through simple examples. Solutions in CHIP of several real-life problems (e.g., cutting stock, warehouses location problems) are presented and compared with usual approaches, showing the versatility and the interest of the approach.     

An interval component for continuous constraints

Local consistency techniques for numerical constraints over interval domains combine interval arithmetic, constraint inversion and bisection to reduce variable domains. In this paper, we study the problem of integrating any specific interval arithmetic library in constraint solvers. For this purpose, we design an interface between consistency algorithms and arithmetic. The interface has a two-level architecture: functional interval arithmetic at low-level, which is only a specification to be implemented by specific libraries, and a set of operations required by solvers, such as relational interval arithmetic or bisection primitives. This work leads to the implementation of an interval component by means of C++ generic programming methods. The overhead resulting from generic programming is discussed.     

A Constraint Programming model for fast optimal stowage of container vessel bays

Container vessel stowage planning is a hard combinatorial optimization problem with both high economic and environmental impact. We have developed an approach that often is able to generate near-optimal plans for large container vessels within a few minutes. It decomposes the problem into a master planning phase that distributes the containers to bay sections and a slot planning phase that assigns containers of each bay section to slots. In this paper, we focus on the slot planning phase of this approach and present a Constraint Programming and Integer Programming model for stowing a set of containers in a single bay section. This so-called slot planning problem is NP-hard and often involves stowing several hundred containers. Using state-of-the-art constraint solvers and modeling techniques, however, we were able to solve 90% of 236 real instances from our industrial collaborator to optimality within 1 second. Thus, somewhat to our surprise, it is possible to solve most of these problems optimally within the time required for practical application.     

Multiscale Domain Decomposition Methods for Elliptic Problems with High Aspect Ratios

Abstract In this paper we study some nonoverlapping domain decomposition methods for solving a classof elliptic problems arising from composite materials and flows in porous media which contain many spatialscales. Our preconditioner differs from traditional domain decomposition preconditioners by using a coarsesolver which is adaptive to small scale heterogeneous features. While the convergence rate of traditional domaindecomposition algorithms using coarse solvers based on linear or polynomial interpolations may deteriorate inthe presence of rapid small scale oscillations or high aspect ratios, our preconditioner is applicable to multiple-scale problems without restrictive assumptions and seems to have a convergence rate nearly independent ofthe aspect ratio within the substructures. A rigorous convergence analysis based on the Schwarz framework iscarried out, and we demonstrate the efficiency and robustness of the proposed preconditioner through numericalexperiments which include problems with multipl     

Helly-type theorems and Generalized Linear Programming

Recent combinatorial algorithms for linear programming can also be applied to certain nonlinear problems. We call these Generalized Linear-Programming, or GLP, problems. We connect this class to a collection of results from combinatorial geometry called Helly-type theorems. We show that there is a Helly-type theorem about the constraint set of every GLP problem. Given a familyH of sets with a Helly-type theorem, we give a paradigm for finding whether the intersection ofH is empty, by formulating the question as a GLP problem. This leads to many applications, including linear expected time algorithms for finding line transversals and mini-max hyperplane fitting. Our applications include GLP problems with the surprising property that the constraints are nonconvex or even disconnected.     

Variable and Clause Elimination for LTL Satisfiability Checking

We study preprocessing techniques for clause normal forms of LTL formulas. Applying the mechanism of labeled clauses enables us to reinterpret LTL satisfiability as a set of purely propositional problems and thus to transfer simplification ideas from SAT to LTL. We demonstrate this by adapting variable and clause elimination, a very effective preprocessing technique used by modern SAT solvers. Our experiments confirm that even in the temporal setting substantial reductions in formula size and subsequent decrease of solver runtime can be achieved.