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-2026 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 */