Scippy

    SCIP

    Solving Constraint Integer Programs

    xternal_miniisc.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_miniisc.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 MINIISC_MAIN MinIISC
    33 * @version 0.1
    34 * @author Marc Pfetsch
    35 *
    36 * This code uses Benders decomposition to solve the Minimum IIS-Cover Problem (MinIISC). Here, one is given an
    37 * infeasible linear system and wants to compute a subsystem of smallest size whose removal leaves a feasible
    38 * subsystem. This corresponds to removing at least one constraint from each irreducible infeasible subsystem (IIS).
    39 *
    40 * The approach is described in:
    41 *
    42 * "Finding the Minimum Weight IIS Cover of an Infeasible System of Linear Inequalities"@n
    43 * by Mark Parker and Jennifer Ryan,@n
    44 * Ann. Math. Artif. Intell. 17, no. 1-2, 1996, pp. 107-126.
    45 *
    46 * @section Appr Solution Approach
    47 *
    48 * This approach works as follows. MinIISC can be formulated as:
    49 * \f{eqnarray*}{
    50 * \min && \sum_{i=1}^m y_i \\
    51 * s.t. && \sum_{i \in I} y_i \geq 1 \quad \forall \mbox{ IISs }I \\
    52 * && y_i \in \{0,1\} \quad \forall i.
    53 * \f}
    54 *
    55 * We begin with a subset of IISs and solve the above set covering problem (using SCIP as a MIP solver). We then check
    56 * whether the resulting vector \f$y^*\f$ corresponds to an IIS-cover. If this is the case, we are done. Otherwise, we
    57 * check for an uncovered IIS and add its inequality to the set covering problem. We then repeat the process.
    58 *
    59 * Checking for an uncovered IIS can be done using a so-called alternative polyhedron. We explain the approach for the case
    60 * in which the linear system is \f$Dx \leq d\f$ where \f$D\f$ is an \f$m \times n\f$ matrix. The alternative polyhedron
    61 * is then
    62 * \f[
    63 * \{z : D^T z = 0,\; d^T z \leq -1,\; z \geq 0\}.
    64 * \f]
    65 * Gleeson and Ryan [1990] proved that the vertices of this polyhedron are in 1-to-1 correspondence with the IISs of the
    66 * original system. If we are then given the solution \f$y^* \in \{0,1\}^m\f$ from the set covering problem, we can
    67 * consider
    68 * \f[
    69 * \{z : D^T z = 0,\; d^T z \leq -1,\; z_i = 0 \mbox{ for all i with }y^*_i = 1,\; z \geq 0\}.
    70 * \f]
    71 * A vertex of this polyhedron corresponds to an IIS is the system remaining from \f$D x \leq d\f$ when the inequalities
    72 * given by \f$y^* = 1\f$ are deleted.
    73 *
    74 * @section Impl Implementation
    75 *
    76 * The implementation uses several tricks to speed up the solution process:
    77 * - Several IISs are generated in one round using the technique described in
    78 * Branch-And-Cut for the Maximum Feasible Subsystem Problem,@n
    79 * Marc Pfetsch, SIAM Journal on Optimization 19, No.1, 21-38 (2008)
    80 * - The master problem can be solved approximately (using a gap limit) or using a stall limit (the final MIP has to be
    81 * solved exactly).
    82 * - Moreover, the master problem can be tackled using reoptimization.
    83 *
    84 * The input to the code should be an infeasible linear program (the objective is ignored) in any format that SCIP can
    85 * handle. The basic benders algorithm is implemented in the file benders.c using a call back for the cut generation.
    86 *
    87 * Installation
    88 * ============
    89 *
    90 * See the @ref INSTALL_APPLICATIONS_EXAMPLES "Install file"
    91 */