- 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:

- the name of the file to create
- matrix dimension
- 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