Linear Ordering

Version

1.0

Author

Marc Pfetsch

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