Scippy

SCIP

Solving Constraint Integer Programs

xternal_lop.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2018 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file xternal_lop.c
17  * @brief main document page
18  * @author Marc Pfetsch
19  */
20 
21 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 /**@page LOP_MAIN Overview
24  * @version 1.0
25  * @author Marc Pfetsch
26  *
27  * The linear ordering gives another example for setting up a
28  * constraint handler.
29  *
30  * The linear ordering problem is the following:
31  *
32  * Given a positive integer \f$ n \f$ and an \f$ n \times n \f$ matrix \f$ W \f$ the goal is to
33  * find a linear order of \f$ \{1, \dots, n\} \f$ such that the sum of weights \f$
34  * w_{ij}\f$ for all pairs in which \f$ x \f$ comes before \f$ j \f$ in the order is
35  * maximized.
36  *
37  * We use the integer programming following model: We have binary
38  * variables \f$ x_{ij}\f$ for all pairs \f$ (i,j)\f$ with \f$ i \neq
39  * j\f$, where \f$ x_{ij} = 1\f$ if and only if \f$ i \f$ comes before \f$ j \f$ in the
40  * encoded order. The basic model is then:
41  * \f[
42  * \max \{ \sum_{i,j} w_{ij} x_{ij}\;:\; x_{ij} + x_{ji} = 1 \mbox{ for all } j \neq i\}.
43  * \f]
44  * To ensure that x encodes a linear order one has to add the
45  * following @em triangle @em inequalities:
46  * \f[
47  * x_{ij} + x_{jk} + x_{ki} \leq 2 \quad\mbox{for all }i,j,k.
48  * \f]
49  * Using the equations above, one can of course eliminate half of the
50  * variables (and change the triangle inequalies accordingly), but we
51  * do not do this explicitly in order to keep a simpler
52  * formulation. In fact, SCIP will do some of the eliminations
53  * automatically.
54  *
55  * The following files provide the example code:
56  * - cmain.c: Here the main function is located. It sets up SCIP, the
57  * linear order project, and solves the problem.
58  * - probdata_lop.c: this file provides code for reading the corresponding weight matrix
59  * and setting up the above model.
60  * - cons_linearordering.c: contains the constraint handler that takes care of the
61  * equations and the triangle inequalities.
62  * - genRandomLOPInstance.c: problem generator (see \ref LOP_PROBLEMGENERATOR "below")
63  *
64  *
65  * @section LOP_PROBLEMGENERATOR Problem Generator
66  *
67  * To use the problem generator you have do two things. First
68  * \ref LOP_PROBLEMGENERATORCOMPILE "compile the generator" and second \ref LOP_PROBLEMGENERATORUSEIT "use it".
69  *
70  * @subsection LOP_PROBLEMGENERATORCOMPILE Compile the Problem Generator
71  *
72  * Call the command
73  *
74  * <code>make genRandomLOPInstance</code>
75  *
76  * in main directory of the example. This will create a binary in the <code>bin/</code> directory
77  * with the name <code>genRandomLOPInstance</code>.
78  *
79  * @subsection LOP_PROBLEMGENERATORUSEIT Use the Problem Generator
80  *
81  * The problem generator needs three parameter:
82  * -# the name of the file to create
83  * -# matrix dimension
84  * -# the range of the integer values
85  *
86  * For example the call (in the main directory of the example)
87  *
88  * <code>bin/genRandomLOPInstance instance 10 6</code>
89  *
90  * produces a file named "instance" containing a matrix of dimension 10x10 with entries between 0 and 6.
91  *
92  *
93  */