SCIL - Symbolic Constraints in Integer Linear programming

0.8

Introduction

This is the manual of the branch-and-cut software SCIL that features symbolic constraints in integer linear programming. A paper describing SCIL is available at http://www.mpi-sb.mpg.de/SCIL/scil.ps

Beside the description of all classes and member function, we give a short tutorial on SCIL.

For our motivation and goals starting this project see this page. A comparison to extant work can be found on this page.

The Structure of SCIL Programs

Typical SCIL programs consist of several parts, some of which are optional

• Includes from other systems and from the SCIL library
• Definition of new basic and symbolic constraints. This section is empty if the build-in constraints of SCIL suffice. We hope that non-experienced users do not need to implement new constraints.
• Definition of an ILP-model P.
• Definition of branching and searching strategies. Again, we suppose that only experienced users implement own branching and searching strategies.
• Solving the ILP-model. Typically this part consists of the single line P.optimize().
• Exploit the the solution.

Implementing Models without new constraints.

We describe the basic usage of SCIL in three examples:

A very short example that uses only one symbolic constraint is the Traveling Salesman Tours example.

The Precedence Constrained Traveling Salesman Tours example uses two different symbolic constraint. One of it is used several times

In the Production planning example we add symbolic and basic constraints to our initial model. Here you learn how one can create entries in the LP-matrix. A detailed description of this issue can be found here.

A user only need to know the class ILP_Problem

Defining new constraints.

To learn how to develop own symbolic constraints we refer to the implementations of the following symbolic constraints:

Hamiltonian Cycles

Something with pricing

An example where the complete model can be stated with predefined constraints, but the efficiency of the algorithm can be improved by separation further basic constraints is given in the symmetric connectivity example.

Advanced usage of SCIL

TODO make examples for primal heuristics, directing the search, configurations.

Projects using SCIL

In this section, we list some projects that are based on SCIL.

• Traveling Salesman-Based Curve Reconstruction in Polynomial Time (AM01)
• A combinatorial approach to protein docking with flexible side chains (ALKM)
• Power Efficient Range Assignment in Ad-hoc Wireless Networks (ACM+03)
• A Polyhedral Approach to Surface Reconstruction from Planar Contours (AF02)
• Multiple sequence alignment with arbitrary gap costs: Computing an optimal solution using polyhedral combinatorics (ACLR)

TODO-List

The system is still under development. The following items are planned in the near future.

• Improve the documentation
• Add a implementation that is directly based on the MIP-Solver of CPLEX
• Add further symbolic constraints

If you have comments and/or suggestions please feel free to contact us.

---