SCIP Doxygen Documentation
Loading...
Searching...
No Matches
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-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_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 */