SCIL - Symbolic Constraints in Integer Linear programming

0.9

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 IP.
• 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 IP.optimize().
• Exploit the the solution.

Implementing Models without new constraints.

We describe the basic usage of SCIL in four examples:

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

In the Tool Switching example we add symbolic and basic constraints to our initial model. Here you will also learn how to create and use your own symbolic constraints.

The use of polynomials in objective function and constraints is described in the Polynomials example.

In the Boolean_Functions example you get an introduction to boolean functions and boolean constraints in SCIL.

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

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.

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)

Contact

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