SCIP Doxygen Documentation
Loading...
Searching...
No Matches
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-2025 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file xternal_lop.c
26 * @brief main document page
27 * @author Marc Pfetsch
28 */
29
30/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
31
32/**@page LOP_MAIN Linear Ordering
33 * @version 1.0
34 * @author Marc Pfetsch
35 *
36 * The linear ordering gives another example for setting up a
37 * constraint handler.
38 *
39 * The linear ordering problem is the following:
40 *
41 * Given a positive integer \f$ n \f$ and an \f$ n \times n \f$ matrix \f$ W \f$ the goal is to
42 * find a linear order of \f$ \{1, \dots, n\} \f$ such that the sum of weights \f$
43 * w_{ij}\f$ for all pairs in which \f$ x \f$ comes before \f$ j \f$ in the order is
44 * maximized.
45 *
46 * We use the integer programming following model: We have binary
47 * variables \f$ x_{ij}\f$ for all pairs \f$ (i,j)\f$ with \f$ i \neq
48 * j\f$, where \f$ x_{ij} = 1\f$ if and only if \f$ i \f$ comes before \f$ j \f$ in the
49 * encoded order. The basic model is then:
50 * \f[
51 * \max \{ \sum_{i,j} w_{ij} x_{ij}\;:\; x_{ij} + x_{ji} = 1 \mbox{ for all } j \neq i\}.
52 * \f]
53 * To ensure that x encodes a linear order one has to add the
54 * following @em triangle @em inequalities:
55 * \f[
56 * x_{ij} + x_{jk} + x_{ki} \leq 2 \quad\mbox{for all }i,j,k.
57 * \f]
58 * Using the equations above, one can of course eliminate half of the
59 * variables (and change the triangle inequalies accordingly), but we
60 * do not do this explicitly in order to keep a simpler
61 * formulation. In fact, SCIP will do some of the eliminations
62 * automatically.
63 *
64 * The following files provide the example code:
65 * - cmain.c: Here the main function is located. It sets up SCIP, the
66 * linear order project, and solves the problem.
67 * - reader_lop.c: this file provides code for reading the corresponding weight matrix
68 * and setting up the above model.
69 * - cons_lop.c: contains the constraint handler that takes care of the
70 * equations and the triangle inequalities.
71 * - genRandomLOPInstance.c: problem generator (see \ref LOP_PROBLEMGENERATORUSEIT "below")
72 *
73 *
74 * To use the problem generator you have do two things. First
75 * \ref LOP_PROBLEMGENERATORCOMPILE "compile the generator" and second \ref LOP_PROBLEMGENERATORUSEIT "use it".
76 *
77 * @section LOP_PROBLEMGENERATORCOMPILE Compile the Problem Generator
78 *
79 * Call the command
80 *
81 * <code>make genRandomLOPInstance</code>
82 *
83 * in main directory of the example. This will create a binary in the <code>bin/</code> directory
84 * with the name <code>genRandomLOPInstance</code>.
85 *
86 * @section LOP_PROBLEMGENERATORUSEIT Use the Problem Generator
87 *
88 * The problem generator needs three parameter:
89 * -# the name of the file to create
90 * -# matrix dimension
91 * -# the range of the integer values
92 *
93 * For example the call (in the main directory of the example)
94 *
95 * <code>bin/genRandomLOPInstance instance 10 6</code>
96 *
97 * produces a file named "instance" containing a matrix of dimension 10x10 with entries between 0 and 6.
98 *
99 * Installation
100 * ============
101 *
102 * See the @ref INSTALL_APPLICATIONS_EXAMPLES "Install file"
103 *
104 */