SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
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:
To use the problem generator you have do two things. First compile the generator and second use it.
Call the command
make genRandomLOPInstance
in main directory of the example. This will create a binary in the bin/ directory with the name genRandomLOPInstance.
The problem generator needs three parameter:
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.