Main Page   Class Hierarchy   Compound List   File List   Contact   Download   Symbolic Constraints   Examples  

Motivation

Motivation

Many combinatorial optimization problems are naturally formulated through constraints. Consider the traveling salesman problem TSP. It asks for the minimum cost Hamiltonian cycle in an undirected graph G = (V,E) with edge weights $ (w_e)_{e \in E} $. Formulated as an optimization task:

Find a subset T of the edges of G such that " \p T is a Hamiltonian cycle" and $ \sum_{e \in T} w_e $ is minimum.

Our vision is that the sentence above (written in some suitable language) suffices to obtain an efficient algorithm for the TSP. Efficiency is meant in a double sense. We want short development time (= efficient use of human resources) and runtime efficiency (= efficient use of computer resources). The software system SCIL is our first step towards realizing this vision. Section ComputeTour shows a SCIL program for the traveling salesman problem. We propose a programming system for (mixed) integer linear programming (ILP) based on a branch-and-cut-and-price framework~(BCP) that features symbolic constraints.

Integer linear programming and more specifically the branch-and-cut-and-price paradigm for solving ILPs is one of the most effective approaches to find exact or provably good solutions of hard combinatorial optimization problems(NW88) (EGJR01). It has been used for a wide range of problems including the TSP (ABCC99) (Nad02), maximum-cut-problems (DeSimone-Rinaldi), cutting-stock-problems (VBJN93), or crew-scheduling (BJN+98). For more applications we refer to the overview (CF97). The implementation of a BCP algorithm requires significant expert knowledge, a fact that has hindered the spread of the method outside the scientific world. It consists of various involved components, each with wide influence on the algorithm's overall performance. Almost all parts of a BCP algorithm considerably rely on linear programming (LP) methods or properties of the linear programming relaxation of the underlying ILP. Many components are problem independent and can be provided by existing software packages (see (JT00)). But there is still a major problem dependent part: an ILP formulation has to be found, appropriate linear programs have to be derived, the various methods for exploiting LP solutions to find feasible solutions or speedup the computation have to be designed and implemented. To our knowledge there is no BCP system for combinatorial optimization that covers the problem dependent part in an appropriate way.

SCIL closes this gap by introducing symbolic constraints , one of the key achievements constraint programming (Hentenryck-Saraswat) into integer linear programming. It simplifies the implementation of BCP-algorithms by supporting high-level specifications of combinatorial optimization problems with linear objective functions. It provides a library of symbolic constraints, which allow one to convert high-level specifications into efficient BCP-algorithms. A user may extend SCIL by defining new symbolic constraints or by changing the standard behavior of the algorithms. We have used SCIL already in several projects like curve reconstruction (AM01) and computing protein dockings (ALKM).

Goals

We collect and motivate the goals that guided the development of SCIL. We distinguish between primary goals determining the overall design and secondary goals determining specific implementation issues.

Primary Goals

Integer linear programs frequently involve a large number of constraints and/or variables. This is either intrinsic in the problem (there are an exponential number of cut constraints in the natural formulation of the traveling salesman problem) or is algorithmically motivated (in order to use column generation, one introduces variables for high level constructs such as cycles in graphs). In either case, the set of constraints and/or variables has considerable structure and is not just an indexed collection $ x_1 $, $ x_2 $, ..., $ x_N $ of variables for some large $ N $. Rather, the variables and/or constraints correspond to objects in the problem domain. We have a variable for each edge or cycle in a graph or we have a constraint for each cut in a graph. This leads to.

Being able to refer to single variables and constraints in a problem-oriented way, is a first step. We also want to refer to groups of variables and/or constraints. For example, we want to talk about degree constraints or cut constraints. We want to specify these constraints once and for all for an abstract graph; it should then be able to instantiate them for a concrete graph. Thus our groups of variables and/or constraints are abstract or symbolic groups. This leads to.

We give an example. The cut constraints with demand $ c \in \mathbbm{N} $ for a graph $ G = (V,E) $ with edge variables $ x_e $ state that $ \sum_{u \in S, v \not\in S} x_{e} \ge c $ for every non-trivial cut $ S \subset V $ with $ \emptyset \ne S \ne V $. This is a symbolic constraint which we can define once and for all and give a name, e.g., cut_constraints. We can then instantiate it for a concrete graph $ G $ whose edges have ILP-variables associated with them through a map EV and for a concrete demand, say 2, by writing cut_constraints(G,EV,2).

We have already seen in the introduction that symbolic constraints together with the ability of referring to ILP-variables through objects from the problem domain leads to concise and readable models. There is another advantage: semantic knowledge about the variables and constraints is retained and can be exploited algorithmically in the underlying branch-and-cut-and-price system.

Every node of a branch-and-cut-and-price tree has an linear program associated with it. This linear program is obtained from the complete specification by selecting some of the constraints and some of the variables. For example, only some of the cut constraints could be present and only a subset of the variables could be active. Assume that a solution to the current LP has been determined.

Our goals have an interesting architectural consequence. When a symbolic constraint is specified and implemented, the context of its use is not known. In particular, a symbolic constraint must work without knowledge of the other variables and constraints in the model.

In different contexts different searching strategies are preferable. There are different rather general approaches and problem specific strategies.

Secondary Goals

The first wish in this section is valid for any software project.

When we started the work on SCIL, we had experience in developing BCP-algorithms using ABACUS, LEDA, and the LP-solvers CPLEX and SoPlex. It was therefore natural to reuse these systems and to build upon the experience gained with them. The desire to reuse ABACUS and LEDA which are both implemented in C++ suggested to use C++ as the programming language for SCIL. This choice is coherent with the following goal.

We knew from our experience with ABACUS and LEDA that C++ supports the first two points, ILOG-solver proves that C++ is adequate for (3), and (4) follows from (3) and the ability to iterate over structures in the problem domain.

In the newest version of SCIL we have replaced LEDA with the free BOOST C++ Libraries. Thus SCIL may be used without any commercial libraries.

A general branch-&-cut algorithm has many parameters, i.e. the work on a node of a tree should could be terminated and a branching step performed, if the bound does only slightly increase during a number of iteration. Such behavior is usually controlled by parameters. The running time of such an algorithm strongly depends on the "right" selection of the parameters, but these parameters could often only be determined experimentally. Thus we want a possibility to experiment with different parameter settings without recompiling the program.

Generated on Mon Mar 28 22:03:51 2011 for SCIL by  doxygen 1.6.3