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-2024 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
*/
applications
MinIISC
doc
xternal_miniisc.c
© 2002-2024 by Zuse Institute Berlin (ZIB),
Imprint
Generated by
1.10.0