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
*/
examples
LOP
doc
xternal_lop.c
© 2002-2025 by Zuse Institute Berlin (ZIB),
Imprint
Generated by
1.14.0