  # SCIP

Solving Constraint Integer Programs

Linear Ordering
Version
1.0

The linear ordering gives another example for setting up a constraint handler.

The linear ordering problem is the following:

Given a positive integer $$n$$ and an $$n \times n$$ matrix $$W$$ the goal is to find a linear order of $$\{1, \dots, n\}$$ such that the sum of weights $$w_{ij}$$ for all pairs in which $$x$$ comes before $$j$$ in the order is maximized.

We use the integer programming following model: We have binary variables $$x_{ij}$$ for all pairs $$(i,j)$$ with $$i \neq j$$, where $$x_{ij} = 1$$ if and only if $$i$$ comes before $$j$$ in the encoded order. The basic model is then:

$\max \{ \sum_{i,j} w_{ij} x_{ij}\;:\; x_{ij} + x_{ji} = 1 \mbox{ for all } j \neq i\}.$

To ensure that x encodes a linear order one has to add the following triangle inequalities:

$x_{ij} + x_{jk} + x_{ki} \leq 2 \quad\mbox{for all }i,j,k.$

Using the equations above, one can of course eliminate half of the variables (and change the triangle inequalies accordingly), but we do not do this explicitly in order to keep a simpler formulation. In fact, SCIP will do some of the eliminations automatically.

The following files provide the example code:

• cmain.c: Here the main function is located. It sets up SCIP, the linear order project, and solves the problem.
• reader_lop.c: this file provides code for reading the corresponding weight matrix and setting up the above model.
• cons_lop.c: contains the constraint handler that takes care of the equations and the triangle inequalities.
• genRandomLOPInstance.c: problem generator (see below)

To use the problem generator you have do two things. First compile the generator and second use it.

# Compile the Problem Generator

Call the command

make genRandomLOPInstance

in main directory of the example. This will create a binary in the bin/ directory with the name genRandomLOPInstance.

# Use the Problem Generator

The problem generator needs three parameter:

1. the name of the file to create
2. matrix dimension
3. the range of the integer values

For example the call (in the main directory of the example)

bin/genRandomLOPInstance instance 10 6

produces a file named "instance" containing a matrix of dimension 10x10 with entries between 0 and 6.

# Installation

See the Install file