
Citation 
 Permanent Link:
 http://digital.auraria.edu/AA00003405/00001
Material Information
 Title:
 A set covering approach to infeasibility analysis of linear programming problems and related issues
 Creator:
 Parker, Mark Richard
 Publication Date:
 1995
 Language:
 English
 Physical Description:
 v, 93 leaves : illustrations ; 29 cm
Subjects
 Subjects / Keywords:
 Linear programming ( lcsh )
Linear programming ( fast )
 Genre:
 bibliography ( marcgt )
theses ( marcgt ) nonfiction ( marcgt )
Notes
 Bibliography:
 Includes bibliographical references (leaves 9093).
 General Note:
 Submitted in partial fulfillment of the requirements for the degree, Doctor of Philosophy, Applied Mathematics.
 General Note:
 Department of Mathematical and Statistical Sciences
 Statement of Responsibility:
 by Mark Richard Parker.
Record Information
 Source Institution:
 University of Colorado Denver
 Holding Location:
 Auraria Library
 Rights Management:
 All applicable rights reserved by the source institution and holding location.
 Resource Identifier:
 34235729 ( OCLC )
ocm34235729
 Classification:
 LD1190.L622 1995d .P37 ( lcc )

Downloads 
This item has the following downloads:

Full Text 
A SET COVERING APPROACH TO
INFEASIBILITY ANALYSIS OF LINEAR
PROGRAMMING PROBLEMS AND RELATED
ISSUES
by
Mark Richard Parker
B. A., University of Colorado at Denver, 1984
M. S., University of Colorado at Denver, 1992
A thesis submitted to the
Faculty of the Graduate School of the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Doctor of Philosophy
Applied Mathematics
1995
This thesis for the Doctor of Philosophy
degree by
Mark Richard Parker
has been approved by
Jennifer Ryan
Harvey Greenberg
Gary Kochenberger
J. Richard Lundgren
Burt Simon
Date
Parker, Mark Richard (Ph. D., Applied Mathematics)
A Set Covering Approach to Infeasibility Analysis of Linear Programming
Problems and Related Issues
Thesis directed by Associate Professor Jennifer Ryan
ABSTRACT
With the increased sophistication of both computers and opti
mization software, linear programming problems of a size inconceivable to
solve only a few years ago are now readily accessible. As model size and
complexity increase, the issue of feasibility becomes a major issue in model
development. This thesis explores the analysis of linear programming in
feasibility through the use of Irreducible Infeasible Subsystems, or
IISs. In particular, we develop a constraint generation algorithm for iden
tifying the minimum weight IIS cover, which isolates a minimal weight set
of constraints whose removal from the system yields a feasible system. It
has been shown that this set covering problem has a very special structure.
We also explore the facial structure of the set covering polyhedra and pro
vide a generalization to a class of covering problems. The link between
this problem and the linear discriminant problem is also explored.
This abstract accurately represents the content of the candidates thesis.
I recommend its publication. Signed______________________________
Jennifer Ryan
m
CONTENTS
Chapter
1. Introduction.......................................... 1
2. Finding the Maximum Weight Feasible Subsystem of an
Infeasible System of Linear Equations................. 3
2.1 Introduction and Notation ............................ 3
2.2 Background on IISs........................... 7
2.3 Hypergraph Framework......................... 13
2.4 Techniques in Approximating the MWFS......... 17
3. Extensions and Unifications of IIS Results............ 29
3.1 Examination of Van Loons Method............. 29
3.2 Van Loons Method and the Gleeson and Ryan Method 37
4. Facial Structure of the IIS Cover Polyhedron.......... 40
4.1 Dimension of the Min Weight IIS Covering Polytope 40
4.2 Known Properties of the General Set Covering Polytope 42
4.3 Properties of the Min Weight IIS Covering Polytope 44
4.4 Generalizations.............................. 52
5. Algorithm Description and Computational Results .... 55
5.1 Introduction................................. 55
5.2 Min IIS Cover Isolation in Practice ................. 57
5.3 Formulation of P, the Alternative Polyhedron, for
General Linear Programming Problems.......... 62
5.4 Finding IISs................................. 64
5.5 Heuristic Solution of Covering Problems.............. 67
5.6 Computational Results ............................... 68
6. Extensions to Solving the Linear Discriminant Problem . 82
7. Summary and Areas for Further Research................ 88
Bibliography ..................................................... 90
1
1. Introduction
This thesis is organized as follows. Chapter 2 introduces the
problem of finding a maximum weight feasible subsystem of an infeasible
system of linear inequalities (the MWFS problem). We review past work
on this problem, including the notion of an Irreducible Inconsistent Sub
system, or IIS. We use a constraint generation algorithm combined with
branch and bound to solve the MWFS problem. Our approach is based
on finding the minimum weight cover over all IISs, which is equivalent to
finding the minimum weight set of inequalities to remove from the infeasi
ble system in order to restore feasibility. We denote this covering problem
as the MWIC problem.
Chapter 3 contains new extensions and unifications to the theory
of IISs.
Chapter 4 contains new theoretical results obtained in examining
the facial structure of the MWIC problem. In particular, we demonstrate
that all covering constraints, which correspond to the IISs of the infeasible
system, are facets of the MWIC problem. We also examine a generaliza
tion of these results to a category of problems called polyhedral covering
problems.
Chapter 5 describes an algorithm for solving the MWIC problem,
and presents computational results. Also, a comparison is made between
the algorithm and a fixed charge integer program formulation of the MWIC
problem.
Chapter 6 discusses further applications of the algorithm to the
linear discriminant problem.
Chapter 7 summarizes the results and discusses areas still open
for further research.
2
2. Finding the Maximum Weight Feasible Subsystem of an In
feasible System of Linear Equations
In this chapter, we will establish notation and present the prob
lem of finding a maximum weight feasible subsystem of an infeasible sys
tem of linear equations.
2.1 Introduction and Notation
Let A be an m X n real matrix and let b be a real mvector.
We then define S = {Ax < b} as the system of linear inequalities arising
from A and b. Let M = {1,... ,m} be the set indexing the rows of A. We
define the following subsystems of S for a subset of the rows of A, I C M.
S(I) = {A;X < bi for i G 1}
S\S(I) = {A;x < bi for i 1}
S\i = S\{A^ < bi}
S {A;X ^ bi  A;X = bi for % Â£ ilL and for all x satisfying Ax ^ b}
If there exists an x satisfying all inequalities in S, then S is
feasible, and x is feasible in S. If there is no x satisfying all inequalities of
S, we say that S is infeasible. Similarly, if S(I) is feasible for I C M, then
S(I) is called a feasible subsystem. If S(I) is infeasible for I C M, we
call S(I) an infeasible subsystem. If S(I) is a feasible subsystem and
S(I)\J{AiX < bi} is infeasible for every i ^ I, then S(I) is a maximal
feasible subsystem. Similarly, if S(I) is an infeasible subsystem and
S(I') is a feasible subsystem for every /' C J, then S(I) is a minimal
infeasible subsystem or an irreducible infeasible subsystem (IIS).
If S is feasible, then S= is the set of implicit equalities of S.
In the general setting, we will also have nonnegativity con
straints on x. We define the set of functional constraints to be the set of
constraints exclusive of all nonnegativity constraints. In some instances,
we will wish to distinguish between nonnegativity constraints and func
tional constraints when we are identifying I ISs. We introduce the following
definition due to Chinneck and Dravnieks [13]: An irreducible incon
sistent set of functional constraints (IISF) is the complete subset of
functional constraints in an IIS.
Suppose that S is infeasible. We define a maximum cardinality
feasible subsystem of S as S(Imcf) where
Imcf = argmax{ I \ \ S(I) is a maximal feasible subsystem}
This extends naturally to a maximum weight feasible subsystem of S. If
we assign weights W{ to each row i of A, we seek to find a feasible subset
of rows maximizing the sum of the weights. We denote this as S(Imwf)
where
Imwf = arg max{^) w;  S(I) is a maximal feasible subsystem}
IM iei
We also wish to review the following basic polyhedral theory. We
refer to the dual system of S as
Sd = {yTA = 0, yTb < 0, y > 0}.
4
Much of the theory in this paper is based upon theorems of the alternative.
In particular, we will make use of the following variant of Farkas Theorem
of the Alternative:
Theorem 2.1 (Farkas [35]) Exactly one of the following holds:
(1) Ax < b is consistent.
(2) There exists y Â£ Rm such that yTA = 0, yTb < 0, and y > 0.
Note that the alternative system identified in (2) above is equivalent to
Sd[J{yTb < 0}.
We will also make reference to the final tableau obtained via a
simplex algorithm. Given a system
max E?= i cixi
subject to
Ax < b
x >0
where A is an m X n real matrix, we use the following standard LP tableau
notation; Xg refers the vector of m basic variables, x^r refers to the vector
of the remaining n m nonbasic variables, B refers to the columns of A
corresponding to the basic variables, and N refers to the columns of A
corresponding to the nonbasic variables. The vector y corresponds to the
dual variables (or reduced costs) of the system. We define the rate of
substitution of a nonbasic variable Xj with respect to a basic variable
X{ as the rate at which X{ must change with respect to a change in Xj to
maintain the equations Ax + s = b with all other nonbasics held fixed at
0. This is the negative of the updated tableau entry in column j, in the
row where i is basic. Thus, if we speak of a negative rate of substitution
5
for nonbasic variable j with respect to basic variable i, we mean that the
tableau entry in column j of row i is positive.
We also refer to the support of a vector. We define the support
of a vector x as the set of nonzero elements of x.
A serious problem in developing or modifying large linear pro
gramming models is the identification of modeling errors and inconsisten
cies. Many researchers have proposed identifying an IIS and using this to
assist the modeler in debugging her formulation (see section 2.2). However
it is known that an IIS can contain as many as n + 1 inequalities, and
this information is potentially useless because a large system is difficult to
comprehend. We propose to go a step further, to identify the maximum
cardinality feasible subsystem. A more practical version allows the analyst
to weight the constraints according to importance or flexibility. Then the
maximum weight feasible subsystem is sought. Equivalently, we want to
identify the minimum weight set of inequalities that covers all IISs, which
we shall call the minimum weight IIS cover (MWIC). If we knew what
the IISs of a system S were, we could formulate the following set covering
problem, where W{ is the weight on the ith constraint.
min Yh=i wizi
subject to
Y^ieJ zi I for IISs, J.
Z{ binary
Unfortunately, it has been shown (see [9]) that the number of IISs may be
exponential in the size of the original problem, so we do not want to write
down the whole problem at once. Instead, we will generate constraints
6
dynamically for the problem and solve it iteratively.
2.2 Background on IISs
IISs, also called minimal infeasible systems and minimal unsolv
able systems, were first introduced in the context of linear inequality theory
in the early part of this century [8].
In his doctoral dissertation [27], Motzkin provides an excellent
review of the theory of linear inequalities. He extends the previous work
by deriving several results pertaining to systems of inequalities, the most
interesting in this context is a necessary condition for an inconsistent sys
tem to be an IIS.
Theorem 2.2 (Motzkin [27]) The coefficient matrix A of an
IIS {Ax < b}, where A Â£ i?mXn, x Â£ Rn, and b Â£ Rm, has rank m 1.
Motzkin proves that if an infeasible system is irreducibly infeasible, then
the rank of the coefficient matrix of the system is one less than the number
of constraints in the system.
Fan [17] again consolidated many of the known results for systems
of inequalities. Additionally, he presented the following strengthening of
Motzkins characterization of an IIS to provide necessary and sufficient
conditions for a system of inequalities to be an IIS:
Theorem 2.3 (Fan [17]) The system {Ax < b} is an IIS if,
and only if, the following conditions hold.
1. There exists exactly m 1 linearly independent rows.
2. There exists y Â£ Rm such that yA = 0, yb < 0, and y > 0.
Fan extends Motzkins results by noting that a necessary and
7
sufficient condition for a system to be infeasible is the existence of a spe
cial solution to the alternative system from Farkas Theorem (see Theo
rem 2.1). In order to guarantee the irreducibility of the infeasible system,
the solution to the alternative system must have y > 0, rather than y > 0
as in Theorem 2.1.
Van Loon [36] was the first to identify IISs with linear program
ming infeasibility analysis. He interprets the result of Fan in light of the
simplex method and proves the result given in Theorem 2.4. Again, we
consider the system Ax + s = b, with s > 0. We will solve the system
in terms of a single slack variable, say Si. Thus, we consider this row the
objective function of a linear program. In the notation below, we refer to
the matrix A1 as the remaining m lxn submatrix of A after the removal
of row 1. We additionally use the following standard LP tableau notation
(see section 2.1); Xg refers the vector of m 1 basic variables, x^r refers
to the vector of the remaining n m + 1 nonbasic variables, B refers to
the columns of A1 corresponding to the basic variables, and N refers to
the columns of A1 corresponding to the nonbasic variables. The vector y
corresponds to the dual variables of the system.
Theorem 2.4 (Van Loon [36]) The system Ax + s = b, s > 0
is an IIS if and only if there is a slack variable, say Si, and vector y, such
that the system can be solved with respect to Si and a set Xg of basic
variables as follows:
(1) 5l = yTb/yi 
(2) xB = B~\b \ W) B'Nxn B~\s \ Sl)
with yTb < 0 and yu ..., ym > 0.
8
In other words, the system of inequalities is an IIS if and only if
upon solution of a standard Phase 1 LP, we have a slack variable which
is negative, say Si, and all other slack variables have a strictly negative
rate of substitution with respect to Si and all problem variables X{ have a
0 rate of substitution with respect to Si.
We demonstrate this theorem on the following example:
1. x2 < 1
2. Xi  x2 < 0
3. xx  x2 < 4
We begin with the all slack basis, and will consider row 3 of our
tableau as the objective:
Xl x2 Si s2 S3 RHS
0 1 1 0 0 1
1 1 0 1 0 0
1 1 0 0 1 4
Upon pivoting x\ and x2 into the basis, we have the following
optimal tableau:
Xl x2 Sl S2 S3 RHS
0 1 1 0 0 1
1 0 1 1 0 1
0 0 2 1 1 2
In this tableau, we have s3 = 2 2si s2 = 2 (which satisfies
(1) from the theorem), x\ = 1 Si s2 = 1, and x2 = 1 Si = 1 (which
satisfy (2) from the theorem). Note also that y > 0 so all of the conditions
of Theorem 2.4 are satisfied, and thus the system is an IIS.
9
Van Loon strengthens this theorem by observing that at least one
IIS can be obtained from a nonminimally infeasible system Ax + s = b,
s > 0 by examining the final Phase 1 tableau. If there exists a slack
variable, say Si, which is negative and all problem variables X{ have a 0
rate of substitution with respect to Si, then an IIS can be identified within
this row as follows:
Theorem 2.5 (Van Loon [36]) The subsystem, consisting of
the constraints corresponding to Si and all slack variables having strictly
negative rate of substitution with respect to Si, is an IIS.
Van Loon also notes that by pivoting through other bases of the
Phase 1 LP other IISs can be identified.
By using IISs as a tool in LP infeasibility analysis, Van Loon
provides the foundation of much of the more recent work in the area.
Gleeson and Ryan [19] derive a geometric approach to IIS iden
tification that is based upon Farkas Theorem of the Alternative and basic
polyhedral theory. They identify an alternative system whose extreme
vertices are in one to one correspondence with the IISs of the original
infeasible LP. In the absence of degeneracy of the alternative system, this
improves upon the work of Van Loon in that every pivot in the alternative
system identifies a unique IIS in the original system.
Theorem 2.6 (GleesonRyan [19]) Let Ax < b denote an
inconsistent set of inequalities. Then the IISs are in 11 correspondence
with the extreme points of the polyhedron P = {y Â£ 9?m  yTA =
0, yTb = 1, y > 0}. In particular, the nonzero components of any ex
treme point of P index an IIS.
10
Once a basic feasible solution to the alternative system exists,
through solution of a Phase 1 LP of the alternative system for instance,
Gleeson and Ryan propose the use of an algorithm due to Dyer [16] to visit
all extreme points. This algorithm, in the absence of degeneracy, provides
an efficient means of visiting all extreme points. In this way, all IISs of
an infeasible system S can be enumerated.
Since removal of any constraint from an IIS yields a feasible
subsystem, finding the minimum cardinality cover over all IISs will iden
tify the minimum number of constraints to modify or remove from the
system to attain feasibility. This minimum set of constraints will provide
a localization of the modeling error/inconsistency. Thus, this approach
provides a framework with which not only to isolate the infeasibility, but
also to diagnose the infeasibility. To date, this approach had only been
explored in the theoretical sense.
Recently, Chinneck (e.g. [13], [10], [11]) has developed a set of
software tools to bring IIS isolation into practical use in LP infeasibility
analysis. The goal of these algorithms is to identify a small cardinality
IISs, the idea being that the smaller the constraint set the infeasibility is
isolated to the easier the actual infeasibility analysis will be. These tools
are now implemented in the commercial LP solvers MINOS(IIS), CPLEX,
and LINDO.
In [13], Chinneck and Dravnieks develop the foundations upon
which these subroutines are based. The first of these routines is a deletion
filter. The deletion filter works by sequentially removing constraints from
the LP and testing for feasibility. If the LP is feasible, the last constraint
11
deleted is reinserted. This process is repeated until all constraints have
been checked. The resulting system is an IIS. This algorithm can be
computationally expensive, and so is used as one of the final pieces of the
integrated algorithm.
The second filter is an elastic filter, which is based upon the idea
of elastic programming. Elastic programming involves the introduction of
artificial variables which stretch the feasible region (as in Phase 1 LP
solutions). Chinneck and Dravnieks use this approach to generate a series
of LPs having various constraints relaxed. By looking at which constraints
have nonzero artificial variables in each LP, a subsystem containing an IIS
can be identified.
The final filter is a sensitivity filter. This filter is based upon
performing sensitivity analysis upon either a Phase 1 or elastic solution.
The set of constraints having nonzero shadow prices in the final tableau
of a Phase 1 LP contains at least one IIS (see [28]).
These three filtering routines can be combined in a number of
ways to create integrated algorithms. Sensitivity analysis is usually used
first, since most infeasibility is diagnosed upon solution of a Phase 1 LP.
Subsequent operations are based upon the objective of the analyst diag
nosis of single IIS or multiple IISs. Either a combination of deletion and
sensitivity filtering, or a combination of elastic and sensitivity filtering is
used (or both) along with a final deletion filter to identify the IIS.
In [22], [23], [24], [25], and [26], Greenberg explores techniques
for diagnosing infeasibility in linear programming models. These studies
12
provide demonstrations of the utility of IIS identification in infeasibil
ity analysis by exploring the strengths and weaknesses of traditional and
IIS isolation techniques on both general and specific models. In [21],
Greenberg considers theoretical and computational issues in the analysis
of consistency, redundancy, and implied equalities in linear programming
models. He provides an analysis and extension of necessary and sufficient
conditions for infeasible subsystems to be irreducible, and organizes the
results in the following theorem. We denote the alternative system of S
(see Theorem 2.1) as SA = {yT A = 0, yTb < 0, and y > 0}.
Theorem 2.7 (Greenberg [21]) If the system S is infeasible,
then the following are equivalent:
(1) S(I) is an IIS.
(2) rank[A(/)] =  I  1 and there exists a solution y to SA such that
I is the support of y.
(3) I is the support of an extreme point of {^Uy^b = 1}.
(4) I is the support of an extreme ray of SA.
In the same paper, Greenberg also explores issues in identifying
maximal feasible subsystems. We will address these issues as we develop
our algorithm in Chapter 5.
2.3 Hypergraph Framework
In [32] and [33], Ryan investigates the structure of the IIS hy
pergraph. A hypergraph is an ndimensional abstraction of a graph. In a
graph, we have a set of vertices and edges which connect pairs of vertices.
In a hypergraph, we also have a set of vertices and edges; however, an
edge is a subset of the vertices in V. We construct the IIS hypergraph
13
H(V,E) as outlined below. Given the inconsistent system S, we let the
set V index the constraints of the system, and let the elements of the set
E index the the IISs of S. Thus an edge of H consists of the indices of
the constraints of S which form an IIS. A transversal of H is a subset of
V which intersects all edges of E. Thus, the problem of finding a mini
mum cardinality I IS cover is the same as finding a minimum cardinality
transversal of H.
In [32], Ryan demonstrates an algorithm for identifying minimal
transversals without the explicit enumeration of the edges of H. We note
the following:
Lemma 2.8 (Ryan [32]) Let H be an IIS hypergraph arising
from the infeasible system S. Then any minimal transversal of H corre
sponds to a minimal set of faces of P that intersect outside of P, and vice
versa.
The heuristic Ryan presents is based upon using the simplex
algorithm to find extreme points of P. Once an initial extreme point is
found, some nonzero basic variable is set to 0 and this variable is included
in the cover. Then, one can continue to resolve the LP, set basic variables
to 0, and update the cover until P is empty. We demonstrate that the cover
obtained upon completion need not be minimal. Consider the following
infeasible system for S:
14
(1)
1. x2 < 1
2. Xi  x2 < 2
3. xx  x2 < 10
4. xx  x2 < 20
X\ and x2>Â§
Then P is the system:
1. 2/2 2/3 2/4 > 0
2. 2/i 2/2 2/3 2/4 > 0
3. 2/i 22/2  IO2/3  202/4 = 1
y >0
We find a solution to P of 2/1 : = 0.2, 2/2 = 0.1 2/3 = 0.1, and
.0, yielding ; the I IS {1,2. ,3}. If we set 2/3 = 0 and resolve the LP,
we find the solution 2/1 = 0.1, y2 = 0.05, 2/3 = 0, and 2/4 = 0.05, which
yields the IIS {1,2,4}. If we also set 2/1 = 0 and resolve the LP, we find
that it is now infeasible. Thus, we have identified the IIS cover {1,3}.
This is not minimal, since removal of constraint 1 from S yields a feasible
system.
15
If IT is a graph then it is 2uniform, which means that every
IIS of S has 2 elements. In this case, finding a hypergraph transversal is
equivalent to finding a vertex cover. Since a 2uniform IIS hypergraph can
contain no cycle of odd length, a 2uniform IIS hypergraph is a bipartite
graph. We can find a minimum vertex cover of any bipartite graph in
polynomial time; however, we can find a minimum vertex cover of a 2
uniform IIS hypergraph in linear time using a greedy algorithm.
Theorem 2.9 (Ryan [32]) Let H be a 2uniform IIS hyper
graph. Then the transversal obtained by successively picking the node
having maximum degree among the currently uncovered edges is a mini
mum transversal.
General IIS hypergraphs do not share this property; however,
they do generalize bipartite graphs according to the following:
Theorem 2.10 (Pulleyblank [30]) Let S be an infeasible lin
ear system. Then S can be partitioned into two consistent subsystems.
A hypergraph is bicolorable if there exists a partition of the nodes
into two sets such that neither set contains an edge (all edges cross the
partition). From the previous theorem, we have that an IIS hypergraph
is bicolorable.
In [33], Ryan details the relationship between IIS hypergraphs
and other hypergraphs generalizing bipartite graphs. Ryan also presents
an algorithm for finding the minimum transversal of H. This algorithm is
based upon the following result:
Theorem 2.11 (Ryan [33]) Let T be any minimal transversal
of an IIS hypergraph having corresponding polyhedron P. Then T is
16
indexed by the variables of P having positive tableau entries in some row
having positive right hand side for some extreme point of P.
Ryan then provides an algorithm that in the absence of degen
eracy in P, enumerates all minimal transversals in polynomial time with
respect to the size of H, and so the minimum cardinality transversal can
be found in time polynomial in the size of H. However, we should re
member that the size of H may be exponential in the size of the original
infeasible system S, since S may yield an exponential number of IISs.
Theorem 2.11 does provide an algorithm for identifying IIS cov
ers (though they need not be minimal).
2.4 Techniques in Approximating the MWFS
We may wonder what other techniques are available for identi
fying a maximum cardinality feasible subsystem or a maximum weight
feasible subsystem. This problem has been examined before (e.g. [26]). A
standard technique is to convert the standard Phase 1 LP (note that we
are including nonnegativity constraints in this formulation):
min E i
subject to
Ax + s s' = b
x, s, s' >0
into a fixed charge problem:
17
mm
sr= i *
subject to
Ax + s s' = b
s' < Mz for constant M sufficiently large
x, s, s' >0
z binary
This fixed charge problem will minimize the number of violated
constraints, and removal of this set of constraints yields a maximum cardi
nality feasible subsystem (see [26]). This problem is extremely difficult to
solve, and a comparison with our algorithm is given in Chapter 5. There
are many difficulties in implementing this formulation. If the constant M
is not large enough, then the problem will still be infeasible. In addition,
if the value of M is too large, then a large number of fractional solutions
can be introduced into the LP relaxation. A large value for M can also
cause stability problems as the Z{ variables can take on values below the
software tolerance for integers.
We may also look at the standard Phase 1 solution to approx
imate the maximum cardinality feasible subsystem. Using the Phase 1
formulation from above, we make the following observation about any
Phase 1 solution:
Lemma 2.12 The constraints having artificial variable nonzero
at the completion of Phase 1 comprise a set of functional constraints whose
removal from the infeasible system S = Ax < b yields a feasible system.
Further, this set of constraints is an IIS cover.
18
Proof: Let the set I consist of the constraints having artificial variable
nonzero at the completion of Phase 1. For the Phase 1 solution x*, S(I)
is the subsystem consisting of those i Â£ M with A;X* > which is
infeasible. All other constraints are of the form A;X* < 6; Vi ^ I. Thus
removal of these constraints yields a feasible subsystem, and x* is a feasible
solution. Further, since removal of all constraints in I restores feasibility
in S, all IISs of S must have an element in I. Thus I also denotes an IIS
cover.
How good a bound on the minimum cardinality I IS cover will the
Phase 1 solution be? We can demonstrate that in general, we might not
even obtain a minimal cardinality IIS cover from the Phase 1 solution.
To illustrate, we give the following example.
Let S be the following system, which is depicted in Figure 2.1:
1. x2 < 1
2. Xi  x2 < 2
3. xx  x2 < 10
4. xx  x2 < 20
X\ and x2>Â§
We then add the artificial variables a2, a3, and a4 to constraints
2, 3, and 4, obtaining the following Phase 1 LP:
19
Figure 2.1. Infeasible system demonstrating Phase 1 solution does not
necessarily provide a minimal IIS cover
20
min 2 + &3 + (Z4
1. x2 + < 1
2. Xi  x2 + a2 = 2
3. xx  x2 + a3 = 10
4. xx  x2 + (Z4 = 20
X\ and x2>Â§
An optimal solution to this LP is X\ = 9, cc2 = 1, a2 = 10, and
a4 = 10. Thus, removal of constraints 2 and 4 yields a feasible subsystem
of S. We note that this is not a minimal set of constraints to remove, since
removal of constraint 2 yields a subsystem satisfied by X\ = 19 and x2 = 1.
Thus, we cannot guarantee that a Phase 1 LP solution will provide even
a minimal IIS cover.
Recently, Chinneck [12] has developed a heuristic for identifying
the MCIC which is based on recognizing this idea. The algorithm uses
a greedy approach to build the cover, where the constraint affecting the
Phase 1 objective the most is removed at a particular step of the algorithm.
This process continues until the Phase 1 LP is yields a feasible solution
to the original problem, at which time the set of constraints removed
from the problem corresponds to an IIS cover. This approach does not
guarantee even a minimal cover upon completion. A comparison of this
approach and an algorithm for solving the MCIC problem exactly is given
in Chapter 5.
A Phase 1 LP can be viewed as the introduction of elastic vari
ables to allow the stretching of each constraint. The objective is to then
minimize the sum of the stretching over each constraint. By introducing
21
elastic variables for each constraint, rather than just those with negative
RHS, and for each variable bound, can we then guarantee a minimal IIS
cover as a solution to the elastic LP? Again, by a similar example, the
answer is no:
Let S be the following system, depicted in Figure 2.2:
1. x2 < 1
2. x2 < 0.5
3. Xi  x2 < 2
4. xx  x2 < 10
5. xx  x2 < 20
X\ and a:2 > 0
We then add the elastic variables ei, e2, e3, e4, e5, eXl, and eX2
to constraints 1, 2, 3, 4, and 5, and to the nonnegativity bounds on X\
and x2, obtaining the following elastic LP:
min Â£*2 e;
1. X2 ei < 1
2. X2 ^2 < 0.5
3. Xl  x2 63 < 2
4. Xx  x2 e4 < 10
5. Xx  x2 65 < 20
6. Xx + > 0
7. X2 + ^X2 > 0
il solution to this LP 1 is Xx = 4.25 , x2
e2 = 5.25, e3 = 0.5, and e5 = 10. Thus, removal of constraints 1, 2, 3,
22
Figure 2.2. Infeasible system demonstrating full elastic Phase 1 solution
does not necessarily provide a minimal I IS cover
23
and 5 yields a feasible subsystem of S. We note that this set is not
minimal, since removal of constraints 1 and 2 yields a subsystem satisfied
by X\ = 19.5 and x2 = 0.5. Thus, we cannot guarantee that a full elastic
LP solution will provide even a minimal IIS cover.
So we obtain an IIS cover simply by solving the Phase 1 LP. In
[12] Chinneck suggests that solving a full elastic programming LP may find
a smaller cardinality cover. We have answered this question by demon
strating that by modifying our Phase 1 problem formulation to a full
elastic programming LP, we still cannot guarantee a minimal cover; and
in general the cover found by either of these techniques will not be of the
same cardinality as the minimum cardinality IIS cover. This is not sur
prising, given the following results. In [9], Chakravarti proves that finding
the maximum cardinality feasible subsystem of the infeasible system S is
NPhard.
Theorem 2.13 (Chakravarti [9]) The problem of finding the
maximum cardinality feasible subsystem of the infeasible system S is NP
hard.
Chakravarti also demonstrates that there can exist an exponen
tial number of IISs in an infeasible system by exhibiting a system having
2n + 1 constraints, in n variables, with 2n IISs.
Theorem 2.14 (Chakravarti II [9]) An infeasible system of
constraints may possess exponentially many IISs.
Further analysis of the complexity of the problem is provided by
Sankaran [34].
24
Theorem 2.15 (Sankaran [34]) The problem of finding the
maximum cardinality feasible subsystem of the infeasible system S is NP
hard even when A is totally unimodular and b is integer.
Sankaran proves the existence of a class of infeasible systems
for which the maximum cardinality feasible subsystem can be found in
polynomial time.
Theorem 2.16 (Sankaran [34]) If the augmented matrix [A b]
is totally unimodular, then the constraints having artificial variable non
zero at the completion of Phase 1 comprise a minimum cardinality set
of functional constraints whose removal from the infeasible system S =
Ax < b yields a feasible system.
Thus, the Phase 1 LP solution will yield a maximum cardinality
feasible subsystem for certain classes of LPs.
In the special case when only a single artificial or elastic variable
has nonzero value at the conclusion of Phase 1, we note the following:
Lemma 2.17 If, at the conclusion of Phase 1, only a single ar
tificial variable is nonzero, then the constraint corresponding to that arti
ficial variable is a minimum cardinality IIS cover.
Proof: By Lemma 2.12, we have that the constraint corresponding to the
nonzero artificial variable is an IIS cover. Since the system is infeasible,
we have 0 <  minimum IIS cover  < 1, so we have a minimum
cardinality IIS cover.
Amaldi [1] and Amaldi and Kann [2], [3] also examine the com
plexity and approximability of both finding the maximum feasible sub
system and finding the minimum set of constraints to remove to attain
25
feasibility. While the two problems are equivalent in terms of complex
ity when solving optimally, they differ in complexity of approximation.
We illustrate this with the following example. Suppose we are given an
infeasible system having 2000 constraints with a MCIC consisting of 20
elements. If we find a set of 30 constraints whose removal from the system
yields a feasible system, we have approximated the maximum cardinaltiy
feasible subsystem to within (2000 30)/2000 = .985; however, we have
approximated the minimum set of constraints to remove in order to attain
feasibility to within (30 20)/20 = .5. Thus, as noted by Amaldi, the
second problem is more difficult to approximate due to its scale.
In particular, they prove the following (ignoring the trivial so
lution for the homogeneous case). APX denotes the class of problems in
NP which can be approximated in polynomial time within some constant
factor. MAX SNPhard problems are a subclass of the APX class which
are characterized by their approximability. MAX SNPhard problems can
be approximated in polynomial time within some constant, but there ex
ists some constant c > 1 such that finding an approximate solution within
c is NP hard. Thus, they can be approximated within some constant, but
not all constants, in polynomial time.
Theorem 2.18 (Amaldi and Kann [2]) The problem of find
ing the maximum feasible subsystem of an infeasible system S having
either {= or <} relations is MAX SNPhard even when restricted to
homogeneous systems with integer coefficients and no pairs of identical
relations.
26
In other words, the maximum feasible subsystem can be approx
imated within a constant but not within every constant unless P = NP.
Amaldi and Kann further define the approximability of the maximum
feasible subsystem problem for infeasible systems S having equality con
straints:
Theorem 2.19 (Amaldi and Kann [2]) Unless
P = NP, there is a constant e > 0 such that the maximum feasible
subsystem of the infeasible system Ax = b can not be approximated
within me, where m is the number of rows of A.
In the case of an infeasible system S having < constraints, Amandi
and Kann demonstrate that it is much easier to approximate the maximum
feasible subsystem.
Theorem 2.20 (Amaldi and Kann [2]) The maximum fea
sible subsystem of the infeasible system Ax < b can be approximated
in polynomial time within a factor of 2.
The proof for this result is constructive, and a polynomial time
algorithm is provided which guarantees a 2approximation.
If we restrict ourselves to identifying the MCIC, Amaldi and
Kann present the following. DTIME{T(n,)) denotes the class of problems
which can be solved in time T{n), where n is the size of the input.
Theorem 2.21 (Amaldi and Kann [3]) The problem of iden
tifying the MCIC of the infeasible linear system Ax < b cannot be ap
proximated within any constant unless P = NP and within clogn, for
any c < 1/8 unless NP C DTIMU(nloglogn), even when restricted to
homogeneous systems with ternary coefficients in { 1,0,1}.
27
We know that certain cases can either be solved optimally in
polynomial time, or approximated within a factor of 2 in polynomial time.
What other bounds can we determine for the cardinality of the maximum
feasible subsystem? We begin by making the following observations about
the infeasible system Ax < b, x > 0.
If all bi > 0, for i = 1, m, then the trivial solution Xj = 0, for j =
l,n satisfies the system. Thus, in forming the Phase 1 LP, we need only
add artificial variables to those rows having a negative right hand side and
we can make the following observation.
Lemma 2.22 The cardinality of the minimum cardinality IIS
cover will be less than or equal to the number of constraints with negative
right hand side.
Proof: If we have k negative 6;s, then we need k artificial variables for
the Phase 1 LP. At most, all k artificial variables will be nonzero at the
conclusion of Phase 1. Since removal of the constraints corresponding
to these k artificial variables yields a feasible subsystem (the 0 solution
satisfies the remaining constraints), the minimum cardinality IIS cover
will be of cardinality equal to or less than k.
28
3. Extensions and Unifications of IIS Results
In this chapter, we will look beyond the surface theory at the
strength behind several results and also explore the relationships among
them.
3.1 Examination of Van Loons Method
Several researchers have examined Van Loons results (see [13],
[19], [26]). A number of shortcomings of the method have been pointed
out the chief among these being that nonnegativity constraints must be
explicitly included in the formulation in order to obtain IISs. In this sec
tion, we will examine more closely the implications of Van Loons result in
an effort to illuminate a more general base theory which can be extracted.
Van Loons method as described in Theorem 2.4 and Theorem 2.5
requires the explicit inclusion of all nonnegativity constraints as func
tional constraints in the system Ax < b; however, exclusion of non
negativity constraints leads to the identification of those IISFs which are
IISs (if any exist); which is only a subset of all IISs of the system.
For example, consider the following infeasible system, displayed
in Figure 3.1:
1. Xi + x2 < 2
2. xx < 3
3. 2*1 CNJ a CO 1 < 8
*i, x2 > 0
(2) (3)
Figure 3.1: Infeasible system for example of Van Loons method
If only the functional constraints are included in Van Loons for
mulation (and X\ and x2 free), then we can pivot both X\ and x2 into the
basis yielding the following tableau:
Xi x2 Si S2 S3 RHS
Xi 1 0 3 0 1 2
S2 0 0 3 1 1 5
x2 0 1 2 0 1 4
0 0 3 1 1 5
Thus, using Theorem 2.5, we obtain the IIS {1,2,3} (the no
tation meaning that constraints 1, 2, and 3 form an IIS). Pivoting to all
other bases containing X\ and x2 yields no other IISs. By using Van Loons
theorem without explicitly including the nonnegativity constraints in the
functional constraints, we have identified all IISs which are IISFs. It is
easy to demonstrate that we will find all IISs which are IISFs in this way;
however, we may have to visit all bases in order to guarantee doing so. To
30
see why we will find all IISs which are IISFs, note that an IISF which is
an I IS of Ax < 6, x > 0 is still an I IS of the more general system Ax < 6,
x free. Thus, by Theorem 2.5 we can identify such an IIS. Since we can
find all IISs of the more general system by pivoting through its bases, we
can find the subset of IISs which are IISFs of the original system. It is
easily seen that we have other IISs in the system which rely on the non
negativity of X\ or x2, for example {1,3, 2:1 > 0} and {1,2, *2 > 0}. Using
this restricted tableau, we cannot identify these IISs unless we modify
Van Loons method. We will look at modifcations for doing this later. For
now, we concentrate on determining when we can identify IISs without
explicitly including nonnegativity constraints in our model formulation.
Given an infeasible system Ax < b, x > 0, there exist certain
conditions under which we know that a source of the infeasibility will lie
strictly within the set of functional constraints. In other words, the system
Ax < b has no solutions, let alone a nonnegative solution. Murty [28]
shows in general that an IIS is contained within the set of variables (prob
lem and slack) having nonzero reduced cost upon completion of Phase 1.
Further, at the conclusion of a standard Phase 1, if the reduced costs of
all problem variables are 0 and the artificial objective is positive, then the
system Ax < b is infeasible, and the source of the infeasibility is among
the constraints corresponding to the slack variables having nonzero re
duced costs in the final tableau. Thus, we know that at least one IISF
which is itself an IIS lies among these constraints (see [28]).
31
We again consider the simple example of Figure 3.1.
1. *i + x2 < 2
2. *i < 3
3. 2*i CNJ a CO 1 < 8
*1, x2 > 0
At the conclusion of the Phase 1 LP, we have the following tableau:
*1 x2 Sl S2 S3 RHS
*i 1 1 1 0 0 2
S2 0 1 1 1 0 1
S3 0 1 2 0 1 4
0 0 3 1 1 5
The reduced cost for problem variables *i and *2 is 0, and all 3
slack variables have nonzero reduced cost. Thus, we have an IISF among
the constraints {1,2,3} in fact, in this case the set corresponds exactly
to an IISF.
Otherwise, if the reduced cost of at least 1 variable is nonzero,
then Ax < b could have a solution, but not a nonnegative solution. Con
sider the following modification of the previous example:
1. X\ + *2 < 2
2. xi < 3
*i, x2 > 0
We note that *1 = 3 and x2 = 1 is a, solution to the system defined by
(1) and (2) (thus a solution exists, but no nonnegative solution exists).
32
This system has the following final Phase 1 tableau:
*1 2:2 Sl S2 RHS
*1 1 1 1 0 2
S2 0 1 1 1 1
0 1 1 1 1
From Murty [28], we see that an IIS exists among the constraints {1, 2, x2 >
0} again in this case, the set gives us an IIS, although it will not in gen
eral.
Looking beyond what Van Loon explicitly states in his paper, we
see how to use his ideas in a more general setting. Suppose we are working
with the infeasible system Ax < b, x > 0, and we choose not to explicitly
include nonnegativity constraints as functional constraints. Again, let us
use the example of Figure 3.1:
1. Xl + x2 < 2
2. X! < 3
3. 2xi CNJ a CO 1 < 8
*i, x2 > 0
At the conclusion of the Phase 1 LP, we have the tableau depicted in
Figure 3.2.
This is an optimal basis in the sense that all reduced costs are
nonnegative. Note that we are unable to pivot x2 into the basis without
pivoting X\ out of the basis. Since we have a 1 in the (52,2:2) position
of the tableau, we cannot use Theorem 2.5 to find an IIS in that row.
We cannot identify an IIS in row 53 because of the 1 in column 2:2. We
33
Xi x2 Sl S2 S3 RHS
Xi 1 1 1 0 0 2
S2 0 1 1 1 0 1
S3 0 1 2 0 1 4
0 0 3 1 1 5
Figure 3.2. Final Tableau, Not Including Nonnegativity in Functional
Constraints
now compare this basis with that obtained from the following equivalent
system:
1. Xi + X2 < 2
2. Xl < 3
3. 2*1 CNJ a CO 1 < 8
4. Xi > 0
5. X2 > 0
*1, x2 free
Xl x2 Sl S2 S3 S 4 S 5 RHS
Xl 1 1 1 0 0 0 0 2
S 2 0 1 1 1 0 0 0 1
S 3 0 1 2 0 1 0 0 4
S 4 0 1 1 0 0 1 0 2
S 5 0 1 0 0 0 0 1 0
0 0 3 1 1 0 0 5
From the all slack initial basis, we have pivoted in X\ and pivoted
out Si the same pivot performed to obtain the tableau of Figure 3.2. As
opposed to the tableau of Figure 3.2, we are able to pivot x2 into the basis
without pivoting out X\. The additional slack variable on the constraint
X\ > 0, s4, can be pivoted out of the basis. Our goal is to have a basis
34
similar to that in Figure 3.2, so we wish for x2 to be basic with activity
level 0. We force this to occur by pivoting in s4 and pivoting out s5; x2
and s5 must have the same activity level, so if one is not in the basis, the
other must be 0 also.
Xi x2 Si s2 S3 S 4 S 5 RHS
Xi 1 0 1 0 0 0 1 2
S2 0 0 1 1 0 0 1 1
S3 0 0 2 0 1 0 1 4
x2 0 1 0 0 0 0 1 0
s4 0 0 1 0 0 1 1 2
0 0 3 1 1 0 0 5
Figure 3.3. Final Tableau, Including Nonnegativity in Functional Con
straints
From row s2 of the tableau of Figure 3.3, we obtain the IIS
{si, s2, s5}. Looking back at row s2 of the tableau in Figure 3.2, we see
that it is identical, save that we have a 1 in the x2 column rather than a 1
in the s5 column (this column does not exist without explicitly including
nonnegativity constraints in the formulation). The key is to recognize
that x2 s5 = 0 > x2 = s5 and thus it is irrelevant whether or not
we include x2 > Â§ explicitly in the problem formulation. We have the
following generalization of Theorem 2.5:
Theorem 3.1 (Extension of Van Loons Theorem) Given
the infeasible system S = {Ax < b, x > 0}, suppose there exists a Phase
1 tableau that satisfies the following:
(1) a slack variable, s;, which is negative, and basic in row i of the current
tableau
(2) positive value in the column (or columns) of one (several) Xj in row i
(3) all Xj have 0 reduced cost
35
(4) all other slack variables have nonnegative tableau entries in row i.
Then, the variables having positive tableau entries in row i index an IIS
of S.
Proof: We note that if in the tableau row i described above there
are no problem variables having nonzero entries, then the hypothesis holds
trivially by Theorem 2.5. Otherwise, without loss of generality, assume
that some problem variable, say X\ has a positive tableau entry in row i.
Since slack variable S{ is basic in row i and X\ has a nonzero entry in row
i, we know that X\ is nonbasic and so X\ = 0 and further the reduced cost
for X\ is also 0. Now consider the system where we include the constraints
Xj + sXj = 0 in the formulation. Here sXj represents the slack variable
on the nonnegativity of Xj (so Xj = ). We can add these constraints to
the current tableau, making each newly added slack variable sXj basic. We
denote the row added for the nonnegativity of Xj as row m\j. Since each
Xj is nonnegative in the current tableau, the modified system will still be
feasible (in the sense that only slack variables have negative value). The
only modification to row i during this process is the addition of a 0 in the
column for each new slack variable sXj. We wish to pivot X\ into the basis,
but leave its value at 0. Thus, we can pivot X\ into the basis, and pivot sXj
out of the basis. If we view the tableau columns for X\ (prior to pivoting
it into the basis) and sXl (after pivoting it out of the basis) as being the
rate at which the basic variables change per unit change in the value of
X\ (resp. s^), then since X\ = we must have that the tableau column
of nonbasic variable X\ prior to pivoting it into the basis is identical to
the tableau column of nonbasic variable sXl upon completion of the pivot.
36
In particular, we note that upon pivoting X\ into the basis, there will be
a 0 in the X\ column of row i, and a nonzero value in the sXl column of
row i. We must only demonstrate that we have modified no other entries
in row i of the tableau by this pivot. Row m + 1 will have a 0 in every
column excluding column which has a 1, and column aq, which has a
1. Because of this, when pivoting x\ into the basis and pivoting sXl out
of the basis, we do not affect any columns of row i excepting column x\
and the previously discussed column sXl. We can repeat this argument for
any such variable Xj having a positive tableau entry in row i. I
3.2 Van Loons Method and the Gleeson and Ryan Method
Let us look closer at the method of Gleeson and Ryan [19]. We
note that the polyhedron P of Theorem 2.6 is a bounded form of the cone
of the alternative system (2) from Theorem 2.1. The following form of
Theorem 2.6 is also implied in [19]:
Theorem 3.2 (Conical version of GleesonRyan Theorem)
Let Ax < b denote an inconsistent set of inequalities. Then the IISs are
in 11 correspondence with the extreme rays of the cone
p' = {y G  yTA = 0, yTb < 0, y > 0}.
In particular, the nonzero components of any extreme ray of P' index an
IIS.
Thus, in the conical version of the GleesonRyan Method, we are
looking for the supports of extreme rays of the alternative system defined
by Farkas Theorem. The alternative system is simply the dual of our
original (primal) system with the primal objective function zeroed out.
37
Thus, by ignoring the objective function, the Phase 1 solution of S can be
used to identify an extreme ray of the unbounded dual system, or an IIS
of the original system. In other words, we can identify one (or more) IISs
with no more work than solving Phase 1 of our original system. In essence,
this generalizes the result of Van Loon [36]. Assume that we are working
with an infeasible system Ax < b, where any nonnegativity constraints
are considered for this discussion to be included. Equivalently, we have
the infeasible system Ax + s = b, where s is a vector of slack variables.
Consider the following LP:
max cTx
subject to
Ax + s = b
s >0
Suppose that at the termination of Phase 1 for the infeasible system we
have a basic slack variable, say si, which is strictly less than 0. Addition
ally, if the Phase 1 tableau entries for all nonbasic variables Xj are 0 and for
all nonbasic slack variables s; are nonnegative in the row corresponding
to Si, then in Theorem 2.5 Van Loon proves that the basic slack variable
Si and all slack variables having negative rate of substitution with respect
to Si form an IIS.
Now, from Theorem 3.2, we have that this same set of constraints
which forms an IIS of P must be the supports of an extreme ray of the
alternative cone P'. In other words, Van Loons algorithm, without explic
itly identifying it as such, finds extreme rays of the alternative system by
pivoting through bases of the original infeasible system looking for tableau
38
rows satisfying the above.
This relationship should not be surprising, given the form of a
solution row in Van Loons method. We have a row with the following
form:
[+ + ...+ 00...01].
Since all reduced costs are 0 or positive, there exist no pivot which will
change the sign of the RHS if we increase any nonbasic variable from 0,
we decrease the value of the RHS in this row. If we think in terms of a
dual pivot, if we try to pivot this row out of the basis, there is no entering
variable we can increase unblocked and so we have an extreme ray.
39
4. Facial Structure of the IIS Cover Polyhedron
In this chapter, we derive some facets for the IIS covering prob
lem. We will begin by introducing some preliminary concepts and previous
results.
4.1 Dimension of the Min Weight IIS Covering Polytope
A few preliminaries will be presented first. We say that the
cardinality of an IIS is the number of constraints and bounds contained
in the I IS. In some instances, we will wish to speak of the rowcardinality
of an IIS. This refers to the number of functional constraints contained
in the IIS. For the remainder of this chapter, we assume, without loss
of generality, that the infeasible system Ax < b has no row i of A with
dij = 0 for all j and bi < 0. If such a row exists, it can be preprocessed
out of the system and dealt with separately. We immediately make the
following observation which provides a lower bound on the size of an I IS
from a system containing no trivial inequalities.
Observation 4.1 Given an infeasible system Ax < b, every IIS
of this system will be of cardinality > 2.
Recall that an inequality A;x < bi is an implicit equality in
the system Ax < b if A;x = bi for all x satisfying Ax < b. We can thus
partition the constraints of Ax < b into the following:
(1) A=x < b is the system of implicit equalities in Ax < b.
(2) A
We also make use of the following wellknown theorem (see [35]
for example):
Theorem 4.2 ([35]) The dimension of the nonempty polyhe
dron Q = {x Â£ 9?n  Ax < b} is equal to n rank(A ).
Using these results, as well as the fact that each IIS has cardi
nality at least 2, we can derive the dimensionality of the IIS covering
polytope.
Theorem 4.3 Given an infeasible system S and the polytope
C = {z Â£ Bn  Dz > 1} constructed such that each row i of D is the
support vector of an IIS of S, then the dimension of C (dim(C)) is n.
Proof: Since a valid solution can be an overcovering, we can set all Z{ s
to be 1. From Observation 4.1, we have that every IIS has at least 2
elements, which implies that each row i of D has at least 2 nonzero d;js.
This implies that no constraint in our problem is implicit for all solutions,
and so the rank of D= is 0. Thus the dimension of C is n. I
A matrix A is called a clutter if the support of every row is not
properly contained in the support of any other row. Since the support of
each row of the 0 1 coefficient matrix of the MWIC problem consists of
the indices of an IIS of S, and since each IIS is minimal by definition, we
have that the coefficient matrix of the MWIC problem is a clutter.
We now examine known results on facets of general set covering
polytopes.
41
4.2 Known Properties of the General Set Covering Polytope
Within this section, we will discuss the general set covering poly
tope defined as:
GSCP(D) = conv{x G Bn  Dx > 1}
Among the basic facts known about the polyhedron GSC P(D)
are the following theorems (see [4] for example).
Theorem 4.4 (GSCP Dimensionality [4]) The polyhedron
GSCP(D) is full dimensional if and only if D is a clutter and each row of
D has 2 or more nonzero values.
As we have seen from Theorem 4.3, the MWIC polyhedron meets
the conditions for full dimensionality. The remaining results in this sec
tion depend upon the dimensionality of the general set covering polytope.
Thus, for the remainder of this section, we shall assume that the poly
hedron GSCP(D) is full dimensional. In general, this need not be true,
however; if a row of D has only a single nonzero element or if a row of D
is properly contained in another row of D, we can preprocess the covering
problem to yield a subproblem which is full dimensional. In particular,
the IIS covering problem is full dimensional.
Theorem 4.5 ([4]) All inequalities of the form Xj < 1 define
facets of the polyhedron GSCP(D)
Thus, the variable upper bounds for the MWIC polyhedron are
facet defining.
Theorem 4.6 ([4]) The inequality Xj > 0 defines a facet of the
polyhedron GSCP(D) if and only if the number of nonzero elements in
row i not including the jth element is at least 2 for all rows i of D.
42
Balas and Ng [4] provide necessary and sufficient conditions for
a standard covering constraint to be a facet defining inequality of the
general set covering polytope. We use the following notation. Nl is the
set of nonzero coefficients in row i of D, and M is the row index set.
Theorem 4.7 (BalasNg [4]) The inequality
Y^{xj  j Â£ Nl) > 1 defines a facet of GSCP(D) if and only if
(1) there exists no k Â£ M with Nk C Nl; and
(2) for each k Â£ N \ Nl, there exists j(k) Â£ Nl such that d^k) = 1 for
all h Â£ M(k), where M(k) = {h Â£ M \ dhk = 1 and dhj = 0, for all
jeN\N{ U{fc}}
They prove that a covering inequality i is a facet of the general set covering
polytope if and only if it is not properly contained in another row and for
every 0 element k in row i there exists a column j(k) having a 1 in row i
and a 1 in every row that has a 1 in column k and a 0 in all other columns
that row i has a 0 in.
We examine the implications of this result on a general set cov
ering instance. Below, we have the coefficient matrix D of a general set
covering problem:
X1 x2 x3 X4 x5 x6
(1) 1 1 0 0 1 1
(2) 0 1 1 0 0 1
(3) 0 1 1 0 1 0
(4) 1 0 1 1 1 1
We observe that row (1) of this problem is a facet. We first note
that row (1) is not properly contained in any other row of D, and thus row
43
(1) satisfies condition (1) of Theorem 4.7. We consider all columns where
row (1) has 0s to show that condition (2) is satisfied. First, we consider
column x3. Rows (2) and (3) have a 1 in column x3 and 0s in all other
columns where row (1) has a 0 (column a:4 is the only other column row (1)
has a 0). These two rows define the set M{x3). We have that rows (1),
(2) , and (3) all have a 1 in column x2, thus j{x3) = x2 and condition (2)
is satisfied for column x3. This condition is satisfied trivially for column
Xi since there are no rows having a 1 in column a:4 and a zero in column
x3 (so M(a;4) is empty). Thus, row (1) forms a facet defining constraint
of the general set covering problem Tx > 1. Similarly, we see that rows
(2) and (3) are also facet defining; however, row (4) is not. Condition (1)
of Theorem 4.7 holds for this row, but condition (2) fails. The set M{x2)
contains rows (1), (2), and (3). However, we are unable to find a column
j{x2) having ls in all four rows and so condition (2) fails.
4.3 Properties of the Min Weight IIS Covering Polytope
We can interpret the meaning of Theorem 4.7 within the con
text of our infeasible system. Let the original infeasible system of linear
inequalities be denoted by S. Let P be the polyhedron defined by the
feasible alternative system given in Theorem 2.6,
P = {y G 3?m  yTA = 0, yTb = 1, y > 0}
and let C denote the MWIC polyhedron
C = {z e Bm  zi > 1 ^ all j},
ieij
where Ij = jth IIS.
44
Note that we have the following correspondence between C and
P: covering constraints of C correspond to the supports of the extreme
points of P, and variables of C correspond to faces of P.
We will begin by proving the following general lemma.
Lemma 4.8 The support of an extreme point p of any polyhe
dron Ax < b, x > 0 consists of those faces of the polyhedron on which p
does not lie.
Proof: The support of an extreme point p is the set of nonzero variables
in an optimal basis for p. If X{ ^ 0, then the constraint X{ > 0 is not tight;
and so p does not lie on the face X{ = 0. Similarly, if X{ = 0, then the
constraint X{ > 0 is tight; and so p lies on the face X{ = 0. An identical
argument for slack variables concludes the proof.
The following corollary is a translation of Theorem 4.7 using the
relationship between C and P defined above.
Corollary 4.9 The support of an extreme point p of P is a facet
defining inequality of C if and only if for every face k of P having extreme
point p on it and having nonempty set of extreme points Lk of P which are
not on face k but on all other faces that extreme point p is on, there exists
another face j{k) of P not containing extreme point p or any extreme
point in Lk
Proof: The support of an extreme point p of P forms a covering con
straint J2 Xj > 1, for j Â£ Np in C. Since the covering constraints of C
form a clutter, we satisfy condition (1) of Theorem 4.7. We note that
the statement of this corollary is a direct translation of condition (2) of
Theorem 4.7 in light of Lemma 4.8. This completes the proof.
45
Let us now examine the facial structure of the MWIC polyhedron.
From Theorem 4.5 and the full dimensionality of the MWIC polyhedron,
we have that constraints of the form Z{ < 1 are facet defining for the
MWIC polyhedron. Theorem 4.6 states necessary and sufficient conditions
for constraints of the form Z{ > 0 to be facet defining. We see that in the
following instances, nonnegativity constraints are facets of the MWIC
polyhedron.
Corollary 4.10 If there exists a constraint j of S which is con
tained in no IIS, then Zj > 0 is a facet defining constraint of C.
Proof: If constraint j of S is contained in no IIS, then there are no
covering constraints of C having coefficient 1 for variable Zj. Since there
are at least 2 nonzero coefficients in each covering constraint of (7, neither
of which is the coefficient of Zj, we satisfy the conditions of Theorem 4.6
and the conclusion holds.
Of couse, we note that if a such a constraint j of S exists, then
we can delete variable Zj from the covering problem C. A nonnegativity
constraint will be a facet if one of two conditions are met:
Corollary 4.11 A nonnegativity constraint Zj > 0 is a facet
defining constraint of C if and only if one of the following holds:
(1) Constraint j of S appears in no IISs of S.
(2) Every IIS of S containing constraint j of S is of cardinality 3 or
greater.
Proof: To prove the only if direction, we note from Theorem 4.6 that in
order for the nonnegativity constraint Zj > 0 to be facet defining, removal
of the jth column of the coefficient matrix of C must yield a system still
46
having at least two nonzero coefficients in each row. Assume that Zj > 0
is a facet defining constraint of C. Now either constraint j of S appears
in an IIS of S or it doesnt.
Case 1 Assume constraint j of S appears in at least one IIS of S. By the
argument above, each IIS that constraint j appears in must have at
least 3 elements, since upon removal of j we must still have at least
2. Thus condition (2) holds.
Case 2 Assume constraint j of S appears in no IISs of S. Then condition
(1) holds.
To prove the if direction, we look at the two conditions speci
fied in the hypothesis.
Case 1 Assume constraint j of S appears in no IISs of S. Then by
Corollary 4.10, the nonnegativity constraint Zj > 0 is facet inducing
in C.
Case 2 Assume constraint j of S appears in at least one IIS of S, and
that the cardinality of every IIS j appears in is at least 3. Then
upon removal of variable j from (7, every row of C will contain at
least 2 nonzero coefficients. Thus by Theorem 4.6 the nonnegativity
constraint Zj > 0 is facet inducing in C.
We have all nonnegativity constraints as facet defining for the
MWIC polyhedron under the following special condition:
Corollary 4.12 All nonnegativity constraints z > 0 are facet
defining for the MWIC polyhedron if and only if each I IS is of cardinality
3 or larger.
47
Proof: This is an immediate extension of Corollary 4.11.
We now examine a special instance of the MWIC problem.
Corollary 4.13 If the cardinality of the minimum weight IIS
cover is 1, then all covering constraints are facet defining for the polyhe
dron C.
Proof: Since the cardinality of the MWIC is 1, there exists a column j
of the MWIC coefficient matrix which is 1. This implies that we have a
face j of P which has no extreme points of P on it. By Corollary 4.9 the
conclusion holds. I
What more can be said about the covering constraints being facet
defining for the MWIC polyhdron? First, let us look at the set Lk (defined
in Corollary 4.9) more closely. Given an extreme point p of P which is
contained on face k, Lk consists of those extreme points of P which are
not on face k, but are on all other faces that extreme point p of P is on. In
other words, Lk consists of those extreme points of P which can be visited
from extreme point p when we move off of face k. We first note that the
nonzero elements of the support of extreme point p will correspond to the
subset of basic variables which are nonzero in all bases of extreme point
p. In the case where p is nondegenerate, there will be only a single basis
and the nonzero elements of the support of p will correspond exactly to
the basic variables. We wish to characterize the extreme points in Lk]
in particular, we will do this by determining if the extreme points in Lk
are adjacent to p. In terms of the simplex algorithm, this is equivalent to
determining if each extreme point in Lk is one pivot away from some basis
of p. This is straightforward for p not degenerate since there is only a
48
single feasible basis corresponding to p. In the case where p is degenerate,
we have many bases corresponding to the same extreme point. In this
case, we view adjacency as meaning that there exists a single pivot from
a basis of p which will take us to the particular extreme point of Lk
Lemma 4.14 Each extreme point Lk of the set Lk for extreme
point p is adjacent to p.
Proof: We will demonstrate the existence of a face of dimension 1 which
contains both extreme points p and Lk, thus implying the adjacency of
the extreme points. Let the dimension of the alternative polyhedron P be
d. Since an extreme point is a face of dimension 0, we know that extreme
point p is determined by the intersection of at least d faces, say e > d
faces. We can pick a subset of size d of these e intersecting faces, always
including face k, which is sufficient to define p. Now Lk shares exactly
d 1 of the intersecting faces in this subset, since it does not lie on face
k. Thus there exists a face of dimension d (d 1) = 1 containing both
p and Lk. This implies that p and Lk are adjacent.
Given this result, how large can the set Lk be? By noting the
uniqueness of the extreme point we move to in a simplex pivot, we obtain
the following result.
Lemma 4.15 The cardinality of the set Lk for extreme point p
of P is at most 1.
Proof: From Lemma 4.14, we have that the extreme points of Lk are a
subset of those adjacent to extreme point p. By the simplex algorithm,
when we pivot in a specific nonbasic variable, say the kth, at a nonzero
value there is a unique extreme point which we pivot to. Thus, the set Lk
49
can have at most a single element.
Now, we can prove the following result on the covering constraints
of the MWIC polyhedron.
Theorem 4.16 (Covering Constraint Facet Theorem) All
covering constraints of the MWIC polyhedron C are facet defining.
Proof: Choose an arbitrary extreme point p of P. Look at all faces of P
that extreme point p is on. By Lemma 4.14, if we wish to pivot off of face
k, then we can visit those elements of Lk in 1 pivot. By Lemma 4.15, Lk
has at most 1 element. If Lk is empty, the hypothesis holds trivially via
Corollary 4.9. Otherwise, Lk is not empty. Extreme point p is defined by
the intersection of e faces (note e is not necessarily the dimension of P).
The extreme point in Lk, call it L\, is defined by the intersection of / > e
faces, of which e 1 also help define p. We note that their definitions
will differ in at least 2 faces. L\ is not on face k, and must be on a face
that p is not (otherwise, the support of p is a proper subset of the support
of L\ which is not possible). Since each IIS of S must have at least 2
constraints, each extreme point of P must have 2 nonzero variables in its
support. Since L\ is on / faces, there must be at least / + 2 faces in P.
Now L\ is on / faces, p is on e faces, and they share e 1 faces, so we
have / + e (e 1) faces which contain either L\ or p or both. This leaves
at least / + 2 (/ + e (e 1)) = 2 1 = 1 face which defines neither
p nor L\. Thus there exists a face of P containing neither p nor L\] and,
by Corollary 4.9 we have the hypothesis.
Thus, all covering constraints of the MWIC problem are facet
defining. If all facets of the MWIC problem are of this form, then the
50
integer hull of the MWIC polyhedron would be completely described, and
the solution to the linear programming relaxation would give us the op
timal cover. As the following example (from [32]) demonstrates, we have
not defined all facets of this problem.
1. Xi < 2
2. xx + x2 < 10
3. 2*1 3*2 < 49
4. 2*i 3*2 < 21
5. *i + x2 < 6
*1, *2 free
The I ISs of this system are: {2,4,5}, {1,3,4}, {2,3,5}, {1,2,4},
and {1,3,5}. Thus, the MWIC has cardinality 2; there are several opti
mal solutions including {3,4}. However, the optimal solution to the LP
relaxation of the MWIC problem is to let each variable take the value 1/3,
and thus the LP relaxation solution is 5/3.
This solution can be cut off using the family of facets derived by
Balas and Ng in [4]. In this paper, all facets with coefficients in {0,1, 2} are
identified for the general set covering problem. We have explored the facial
structure of the MWIC polyhedron further but found no simplification of
51
the necessary and sufficient conditions for these constraints to be facets in
the MWIC problem.
4.4 Generalizations
In this section we present an abstraction of the theorems in the
previous sections to a new family of covering problems, called Polyhedral
Covering Problems.
We first recognize that the MWIC problem is exactly one of
identifying the minimum weight set of faces of P which cover all extreme
points of the polyhedron P (or the minimum weight set of faces which
intersect outside of P see [32]). The special structure of the MWIC
problem is a direct consequence of the polyhedral nature of the covering
problem. In our case, the supports of the extreme points of P correspond
to IISs of S. However, the only conditions we used in proving the results
of Chapter 4 were the minimality of each IIS (thus having a clutter), that
each IIS has at least 2 elements, and the extreme point relationship.
Suppose we are given the more general problem of identifying the
minimum weight extreme point cover of the polyhedron GP we denote
this as the MWEPC problem. Let EP be the array whose rows are the
support vectors of the extreme points of GP, so EPv > 1 forms the
covering constraints of MWEPC. By the minimality of an extreme point,
we have that the rows of EP form a clutter.
We are not guaranteed that each extreme point of GP will have at
least 2 nonzero elements in its support. Consider the following polyhedron:
52
ep3
Since epi is defined by the intersection of faces a, 6, and c, the
support of extreme point epi is {0001}. We will call such polyhedra
pyradmidal. If GP is unbounded, then we can have extreme points
whose supports have no nonzero elements. Consider the trivial case
1. x1 >0
2. x2 > 0
*i, x2 free
This system has only a single extreme point X\ = 0,x2 = 0, whose support
vector is {00}.
If we wish to cover the extreme points of a polyhedron, these
2 cases can be trivially preprocessed out of the covering problem. If the
support of an extreme point has a single element nonzero, say the jth, then
we simply remove this row and all other rows having a 1 in column j from
EP and set the jth covering variable to 1. If we have any extreme points
having no nonzero elements in their supports, then there is no solution to
the covering problem (there exists no faces intersecting outside of P).
53
With this type of preprocessing, all properties of the MWIC prob
lem generalize to the MWEPC problem. In particular, all covering con
straints of the MWEPC problem will be facet defining (this is analagous
to Theorem 4.16).
54
5. Algorithm Description and Computational Results
5.1 Introduction
In this chapter we develop an algorithm for obtaining the MWIC
based upon the IIS identification method of Gleeson and Ryan discussed
previously. If we knew what the IISs of a system S were, we could formu
late the following set covering problem, where W{ is the weight on the ith
constraint.
min E1 WiZi
subject to
Y^ieJ zi 1 for HSs J.
Z{ binary
Unfortunately, as previously discussed, the number of IISs may be expo
nential in the size of the original problem, so we do not want to write
down the whole problem at once. Instead, we will generate constraints
dynamically for the problem and solve it iteratively as outlined below:
(1) Identify an initial set of IISs K. (K may be empty.)
(2) Solve the covering problem
min E 1 Wizi
subject to
EiGJz 1 fr HS>S J Â£ K.
Z{ binary
Let T index the elements in the optimal cover.
(3) Look for an IIS of S not covered by T. If there is none, STOP, T
is an optimal cover of all IISs. Otherwise, add the new IIS to K
and go to 2.
To identify IISs, we will make use of Theorem 2.6 due to Gleeson
and Ryan [19]. We examine the utility of this theorem in terms of our
algorithm presented above.
Let T denote the index set of a subset of the variables defining
P. Then T will also denote a subsystem of the system S. Let yr = 0 mean
that all the variables in T have been set to 0. If we search for an extreme
point of P with yr = 0, there are two possibilities. The first is that we
find an extreme point whose nonzero components index an IIS that does
not intersect T. The second is that there is no such extreme point of P.
In this case, the system {S \ T} is feasible.
We can now modify step 3 of our algorithm (outlined above):
(1) Identify an initial set of IISs K. (K may be empty.)
(2) Solve the covering problem
min Ya=i wizi
subject to
Y,ieJ zi > 1 for all IISs J Â£ K.
Z{ binary
Let T index the elements in the optimal cover.
(3) Look for an extreme point of P having yr = 0. If there is none,
STOP, T is an optimal cover of all IISs. Otherwise, add the IIS
corresponding to this extreme point to K and go to 2.
56
This implementation is generalized in Section 5.3 to operate on
an infeasible linear programming problem given in a more general format.
Later sections discuss enhancements including the selection of the initial
K in Step 1, and the choice of extreme point in Step 3. We also discuss
the efficacy of using a heuristic to solve the covering problem in Step 2
when possible. Now, we demonstrate the utility of the IIS cover isolation.
5.2 Min IIS Cover Isolation in Practice
Finding a minimum weight IIS cover will take more time than
identifying a single IIS and attempting infeasibility diagnosis. Is the extra
information obtained worth the extra time expense? We address this by
looking at several examples, and making a number of simple observations.
Observe that if there exists a constraint which is contained in every IIS, it
is a minimum IIS cover. So, in the best case, infeasibility can be isolated
to a single constraint.
This is illustrated by the following example from [36]: Consider
the infeasible system, which is depicted in Figure 5.1:
1. Xi  x2 < 0
2. 2*2 < 1
3. xx  x2 < 2
4.  x2 < 2
5. 2*1  x2 < 4
An IIS of this system is {1,2,3}. Based upon this information alone, out
of the context of the entire system, a modeler would have a difficult time
determining the source of the infeasibility. The unique min IIS cover
is {2}, which indicates that every IIS in the system contains the second
57
Figure 5.1: Infeasible system from Van Loon
58
constraint.
It is easily demonstrated, however, that the modeling error is not
always isolated by a particular minimum IIS cover. Any infeasible system
having only a single I IS will have a minimum I IS cover consisting of any
element of the IIS. By weighting the objective function of the covering
problem, alternative minima can be identified to aid in isolation. This
can be done by setting the objective function coefficients for variables
contained in the original cover to a suitably large integer, say n which is
the number of variables in the covering problem. We then resolve the
covering subproblem one time with the current IIS set. In summary, the
minimum IIS cover itself will not always provide a perfect isolation to the
modeling error; however, the isolation information in using this technique
to find the minimum IIS cover is always at least as useful as that obtained
from a single IIS. Using our algorithm to find the min IIS cover always
identifies at least one IIS. This combination of min IIS cover and IISs
is available to the user in her debugging analysis. Additionally, the IIS
cover will always give the modeler the means of eliminating infeasibility
from the model. A single IIS does not provide this level of isolation in
general.
We now examine the isolation power of this method on a larger
problem. We look at a real industry example of using the minimum weight
IIS cover to isolate infeasibility. This LP is a SONET network model hav
ing 845 rows, 1792 columns, and 8448 nonzero entries. The SONET model
arises from a new family of problems in the telecommunications industry
59
 it is a multidimensional packing problem with many complicating con
straints. Specifically, there are a large number of capacity and demand
constraints and a large number of side constraints. These side constraints
are generated by a number of different software codes depending upon the
exact model being analyzed. An instance of the model was found to be
infeasible, and was analyzed using our algorithm. The min cardinality IIS
cover isolated the infeasibility to a single demand constraint. Since this
portion of the model was known to be valid, weights were assigned to rows
of the infeasible problem and the min weight I IS cover was found. A weight
of 1 was assigned to all software generated constraints, which accounted
for 32% of all rows, and a weight of 5 was assigned to all capacity and
demand constraints. These weights become the objective function value
in the covering problem for each covering variable. The covering variables
correspond to constraints of the original infeasible system. Resolving, we
were able to isolate the infeasibility to an incorrectly generated constraint.
Looking at the code used to generate this constraint led to the discovery
of a family of 5 other improperly generated constraints and correction of
a section of code. Using OSL, it initially took 3.26 seconds on the RS6000
to determine that the problem was infeasible. Using our algorithm built
around the OSL library, the iterative procedure of identifying IISs and
solving the minimum cardinality IIS cover to optimality took 7.28 sec
onds. Once we decided to resolve the minimum weight IIS cover, our
procedure took 7.21 seconds to conclude the iterative process of IIS and
optimal cover identification. In order to compare our solution timeliness
with state of the art IIS identification routines, we performed another
60
test to identify a single IIS. Again using the RS6000, we used the builtin
CPLEX IIS identification routines (based upon the work of Chinneck) to
identify a single IIS. This diagnosis took 86 seconds (after infeasibility
was diagnosed), and yielded an IIS having 6 elements. In this example,
we were able to find both minimum weight and minimum cardinality IIS
covers in less time than the current state of the art IIS identifier found
a single IIS. The analysis path used to debug this example has proven
successful isolating infeasibility in several other problems.
Suppose a modeler takes the extra time during model develop
ment to generate weights for each constraint and includes these weights
as an extra column in the LP formulation. As a practical consideration,
when running the model the bounds for this column can be set to zero.
Thus the supplemental debugging information is ignored when exercising
the LP model. If the model is found to be infeasible, the weights will be
used by the min weight IIS cover algorithm to weight the objective func
tion of the covering subproblem in order to help isolate the infeasibility.
As seen in this example, having constraint weights available can greatly
increase the effectiveness of postinfeasibility analysis.
We present an example from the NETLIB infeasible library to
demonstrate another key advantage of the min IIS cover. The WOOD
INFE problem is a small network example with 36 rows and 89 columns.
An IIS infeasibility isolation from MINOS(IIS) is a single functional con
straint (plus nonnegativity constraints). However, the min IIS cover con
sists of 2 functional constraints. This problem has two disjoint modeling
errors which can not both be identified by a single IIS. In infeasibility
61
instances with multiple modeling errors the covering approach is especially
powerful.
5.3 Formulation of P, the Alternative Polyhedron, for General
Linear Programming Problems.
We now turn our attention back to the problem of identifying
IISs. Theorem 2.6 can be restated in a more general setting:
Theorem 5.1 (General Version of GleesonRyan Theorem)
Given the inconsistent system
5 = {xÂ£ Qn  Ax < b, Cx = d, L < x < U},
the indices of the minimal infeasible subsystems of S are exactly the sup
ports of the vertices of the polyhedron P = {y,w,v,z Â£ Qm  yTA +
wrC+vz = 0, yTb+wTd+vTUzrL = 1, y,z,v > 0, w unrestricted}.
Note that if the only bounds on x are nonnegativity constraints,
we can simplify the above formulation:
Theorem 5.2 (General Version II of GleesonRyan Theorem)
Given the inconsistent system
S = {x Â£ Qn  Ax < b, Cx = d, x > 0},
the indices of the minimal infeasible subsystems of S are exactly the sup
ports of the vertices of the polyhedron P = {y, w Â£ Qm \ yTA\wTC >
0, yTb + wTd = 1, y > 0, w unrestricted}.
In other words, we do not need to explicitly handle nonnegativity
constraints, but can simply check the status of the slack variables of the
alternative system to determine if nonnegativity of some X{ is included
62
in an IIS. Also, this helps reduce the size of the LP instance we solve at
each step.
If the right hand side of the conebounding constraint were
left as 1 for large problems, numerical instability would result. We ob
served on several problems that when we fixed at 0 those variables in the
alternative system which are in the covering solution, we obtained an IIS
identical to the one just previously generated. But this means that in try
ing to find an IIS not covered by the current solution, we have generated
one that is covered by the current solution. Examine what can happen if
P has many columns.
Assume that we have the following system for P: yTA > 0, where
each a,ij > 0 for i = 1,...,m and j = 1,... ,n, and yTb = 1, where b = 1
( 1 is the mvector of ls). Also assume that the zero tolerance cutoff is
1.0E07, so all values equal to or less than 1.0E07 are considered to be 0.
Then, y = 1.0E 07 satisfies the first constraint, and if m = 10,000,000,
then Â£)(1.0.E 07)( 1) = 1, so the second constraint is also satisfied.
Now each y; is within epsilon of 0 and so should be considered 0. Instead,
we have allowed a solution which is numerically feasible to be identified
by the optimizer.
However, since the values of the basic variables are below the
software imposed tolerance, they should be considered 0, and so we should
have that YJiLi(yi*ki) = 0 for any k; which means that the solution to the
alternative system is not basic feasible. When this solution is identified
as being feasible, then we identify subsystems which are not IISs. In this
example, we can alleviate this problem by setting the right hand side of
63
the second (or conebinding) constraint to be equal to = m (the
negative of the number of variables in the problem). This will eliminate
the problem for tolerances greater than or equal to 1 /m for the conditions
outlined above which are not necessarily worst case.
For the general case described in Theorem 5.1, we extend the
logic used above to determine that a conebinding constraint eliminating
such problems could be:
yTb + wTd + vTU ztL = ((Â£ 6*) + \dk\) + \Uo\ + \Lo\))
k k j
To see why absolute values are included on the sum, consider the following
modification to the previous example. Assume that there is a 10,001st
constraint, having a right hand side value of 10,000. Then, = 0,
which does not eliminate the solution y = 0. We have not yet encountered
a problem for which this normalization fails to eliminate the problem.
5.4 Finding IISs
Two slightly different approaches may be used to identify IISs
of S. First, we consider using the simplex algorithm to find extreme
points of P. By bounding the objective function yTb of the alternative
system and including it in the constraint set of P, we free ourselves to
use a surrogate objective function to heuristically guide our search. We
have experimented with using 1 as the objective weight. This should
tend to find small cardinality IISs, although to find the true minimum
cardinality I IS we must solve a fixedcharge integer programming problem
(as demonstrated by Greenberg and Murphy [26]). Additionally, these
weights can be modified at each step by incrementing the weight of each
64
variable appearing in the current IIS. In this way, we heuristically tend
to find IISs which overlap in the fewest number of elements. This should
help in the identification an optimal cover to the full MWIC problem by
identifying sets of nonoverlapping IISs.
We have also considered ignoring the objective function when
looking for extreme points of P and using the first feasible solution found.
Since every extreme point corresponds to an IIS, we still identify an IIS.
As expected, this takes fewer pivots to find an IIS than solving to opti
mality with the surrogate objective described above. However, the savings
in I IS identification time may be offset by the typically larger cardinality
IISs found and the increased number of covering subproblems needed to
solve.
Rather than generating IISs individually, we can generate many
by solving a single LP if we instead search for extreme rays on the cone
P', as suggested by Greenberg [21]. We consider the following linear pro
gramming instance based upon our definition of P':
min yTb
subject to
yTA =0
y >o
Since S is infeasible, Theorem 2.1 implies that P' is feasible and hence
unbounded. Therefore, we must be able to find at least one nonbasic
variable of nonoptimal sign at termination of our new LP. If this nonbasic
variable is not blocked, then the variable and all basic variables which
correspond to nonzero tableau column entries for the nonbasic form the
65
support set of an IIS. In other words, the supports of the extreme rays
of P' are IISs in the original infeasible system, S. In general, we will
have more than a single such nonbasic variable, so we can find many IISs
from one LP solution. By pivoting we can find all IISs of S by such a
procedure.
In general, we will have to perform several pivots before identi
fying unboundedness due to the degeneracy of the 0 solution. In prac
tice, this method can reduce the number of iterations to solve the min
imum weight IIS cover. For example, let an IIS of S be identified as
{1,2,3,4,5,8,10,15} and suppose that constraint 15 is in every IIS (and so
is the minimum IIS cover). If {1} is identified as the cover, there could
exist another IIS of the form {2,3,4,5,6,8,10,15} and so forth. There could
be potential to identify many IISs before the min IIS cover is solved op
timally. If a conical solution yields multiple IISs, the total number of
covering subproblems (and hence IIS identification problems) can be re
duced. This becomes important for large infeasible problems which can
have a single constraint as the optimal min IIS cover, while having IISs
with hundreds of elements in them.
Since solving on the cone of the alternative system allows us the
potential to identify multiple IISs from a single basis and in general takes
fewer pivots to solve, the idea is to use this as a jumpstart for the
algorithm, and then to use the extreme point method to find IISs with
specific characteristics.
We can illustrate each of these methods using the following ex
ample from [13] using LINDO. Suppose we are given the infeasible system
66
S defined as:
1. 0.5*i + x2 > 0.5
2. 2*1 x2 > 3.0
3. 3*i + X2 < 6.0
4. *5 < 2.0
5. 3*4  x5 < 2.0
6. *4 > 5.0
7. *i + X5 < 10.0
8. *i + 2*2 + *4 < 14.0
9. X2 + *4 > 1.0
with all X{ > 0
If we solve to optimality using objective weights 1 for all variables of the
alternative system, after 6 pivots, we find {4,5,6} as an IIS. If we solve to
feasibility only (ignore the objective weights), we find the IIS {1,2,3} after
5 pivots. Solving on the cone we find 3 IISs after only 4 pivots: {4,5,6},
{1,2,3}, and {1,2,5,6,7}. The min IIS cover is {1,5}, so by solving on
the cone, we initialize our procedure with enough IISs to solve the cover
problem only once.
5.5 Heuristic Solution of Covering Problems
The covering problems can be solved heuristically at intermediate
steps. We can determine if these suboptimal covers are true covers of the
min weight covering problem just as we did when solving this problem
optimally in Step 3 of our algorithm. If a true optimal cover is desired,
the covering problem must be solved optimally before terminating.
The greedy heuristic [14] can be used at intermediate steps.
67
When no IIS is found that is not covered by the greedy solution, we
solve the covering problem optimally. If the cover is the same cardinality
as that found by the greedy heuristic, we are done. Otherwise, we find an
IIS not covered by the current solution and continue the algorithm. The
greedy algorithm will not guarantee an optimal cover; however, it seems
to work well in practice.
For the problems in the infeasible library on NETLIB, we have
found that typically only a small fraction of total algorithm time (usually
less than 10%) is spent solving the covering subproblems. This result is
based on identifying IISs singly by searching for extreme point solutions
of P, so the results could change significantly with improvements over the
basic form of the algorithm. It should be noted that the difficulty of the
covering problem has been displayed on a few relatively small problems.
For the NETLIB problem MONDOU2, more than 97% of the CPU time
(115 of 118 seconds) was spent solving a single instance of the covering
subproblem having only 9 constraints. This demonstrates a need to both
learn more about the structure of this special IIS covering problem and
perhaps explore more fully using the greedy algorithm, or a modification
of it, at intermediate steps.
5.6 Computational Results
All comparisons (unless otherwise stated) were run on an IBM
RS6000 using the IBM OSL object library and FORTRAN code written
by the author. All runs were made with approximately the same computer
load only a single user was on the system. We experimented with three
versions of our algorithm. All three solve the covering subproblem to
68
optimality at each step using the OSL EKKMSSL subroutine. We have not
yet completed implementation of a version which will solve on the cone, so
all three versions presented here search for extreme point solutions on the
bounded alternative system. We distinguish each version by the objective
function used in solving the alternative system. The baseline algorithm,
IIS_C0V_1, weights the coefficients of the objective function to all ls in
an attempt to find small cardinality IISs. Version 2, IIS_C0V_2, weights
the coefficient of each variable according to how many generated IISs it
already appears in. Intuitively, this will tend to find IISs which overlap
as little as possible. Finally, version 3, IIS_C0V_3, ignores the objective
function, and the first extreme point found is the solution. This will tend
to identify IISs faster, though perhaps at the trade off of finding larger
cardinality IISs. Note that IIS_C0V_2 will differ from IIS_C0V_1 only
when more than 1 IIS is found to optimally solve the covering problem.
Therefore, we did not run IIS_C0V_2 if we found that only 1 IIS was
needed to find the optimal cover.
The test bed of problems consists of the infeasible LP library on
NETLIB, originally set up by John Chinneck. A summary of the problems
is given in Table 5.1.
In order to facilitate the analysis of results, we partitioned the
problems into 3 sets according to their size. We considered small prob
lems to be those having fewer than 100 rows and 100 columns. Medium
problems are those with between 100 and 1000 rows and 100 to 1000
columns. The remainder are large problems.
Table 5.2 presents the results of our 3 approaches on the small
69
Problem Original Problem Alternative System
Constraints Variables Nonzeros Constraints Variables Nonzeros
BGDBGl 348 407 1440 408 390 1737
BGETAM 400 688 2409 689 689 2957
BGINDY 2671 10116 65502 10117 2671 67589
BGPRTR 20 34 64 35 20 76
BOX1 231 261 651 262 492 1173
CERIA3D 3576 824 17602 825 3576 17851
CHEMCOM 288 720 1566 721 625 2180
CPLEX1 3005 3221 8944 3222 3223 10883
EX72A 197 215 467 216 412 897
EX73A 193 211 457 212 404 879
FOREST6 66 95 210 96 71 226
GALENET 8 8 16 9 16 38
GOSH 3792 10733 97231 10734 3792 97433
GREENBEA 2393 5405 30885 5406 2941 31926
ITEST2 9 4 17 5 9 26
ITEST6 11 8 20 9 11 31
KLEIN1 54 54 696 55 54 700
KLEIN2 477 54 4585 55 477 4600
KLEIN3 994 88 12107 89 994 12115
MEXP 1383 1500 5027 1501 1383 5755
MONDOU2 312 604 1208 605 1520 3088
PANG 361 460 2652 461 453 2587
PILOT4I 410 1000 5141 1001 717 5860
QUAL 323 464 1646 465 835 2662
REACTOR 318 637 2420 638 932 3699
REFINERY 323 464 1626 465 835 2641
VOL1 323 464 1646 465 835 2662
WOODINFE 35 89 140 90 69 208
Table 5.1: Problem Test Bed
70
problems. The measures we use in comparing the approaches are total
solution time of the covering problem (CPU seconds), number of IISs
identified while solving the covering problem optimally (not the number
of IISs in the cover), number of pivots to first IIS, average number of
pivots per IIS, and the smallest cardinality IIS. In analyzing infeasibility,
it may be useful to measure the size of an IIS in terms of the number
of actual constraints it contains, rather than constraints and variable
bounds both nonnegativity and general upper and lower bounds. Note
that IIS size refers to the number of constraints and variable bounds
exclusive of nonnegativity bounds. Information on nonnegativity
bounds is available with the solution approach, we have chosen to not
include it in the IIS reporting. The columns for average IIS size and
smallest cardinality IIS are thus subdivided into IIS size and number of
actual constraints.
On most problems, very little time is spent in solving the min
weight covering subproblem, and from 50% to 95% of the time is spent in
identifying IISs solving the alternative system LP. Therefore, another
reasonable measure of how well each algorithm performs is the number of
simplex pivots required to find an IIS.
The first few pivots made by OSL during Phase 1 will be random.
This is done initially to speed up the simplex algorithm, and later other
pricing schemes are used. This means that when rerunning a problem
with the same algorithm we will have variance in our solution times. On
the problems we looked at, this variance was typically 5% or less. For
this reason, we will consider time differences between algorithms to be
71
Problem Algorithm Cover Time # USs Generated Pivots Avg. IIS Smallest IIS
IIS 1 Avg. Size Rows Size Rows
BGPRTR IIS_COV_l 0.19 i 18 10.0 7.0 7.0 7 7
BGPRTR IIS_COV_3 0.20 i 14 8.0 14.0 14.0 14 14
FOREST6 IIS_COV_l 0.73 2 124 50.3 64.0 59.0 64 59
FOREST6 IIS_COV_2 0.71 2 124 51.0 64.0 59.0 64 59
FOREST6 IIS_COV_3 0.61 2 81 29.3 69.5 64.5 69 64
GALENET IIS_COV_l 0.19 1 7 3.5 6.0 3.0 6 3
GALENET IIS_COV_3 0.20 1 5 3.0 6.0 3.0 6 3
ITEST2 IIS_COV_l 0.38 3 4 2.0 3.7 3.7 3 3
ITEST2 IIS_COV_2 0.35 3 4 2.0 3.7 3.7 3 3
ITEST2 IIS_COV_3 0.36 3 4 1.8 3.7 3.7 3 3
ITEST6 IIS_COV_l 0.65 3 6 2.8 3.3 3.3 3 3
ITEST6 IIS_COV_2 0.69 3 9 4.0 3.3 3.7 3 3
ITEST6 IIS_COV_3 0.65 6 3 1.7 3.7 3.7 3 3
KLEIN1 IIS_COV_l 0.89 1 162 81.5 51.0 51.0 51 51
KLEIN1 IIS_COV_3 0.82 1 116 71.5 51.0 51.0 51 51
WOODINFE IIS_COV_l 0.46 2 24 12.6 2.0 1.0 2 1
WOODINFE IIS_COV_2 0.41 2 24 12.6 2.0 1.0 2 1
WOODINFE IIS_COV_3 0.48 2 9 11.0 2.0 1.0 2 1
Table 5.2: Results for Small Problems
72
significant only if they are greater than 10%. In this light, no significant
time difference is found between the algorithms on the small problem test
bed. On the 4 problems where all 3 algorithms were run, IIS_COV_2 was
faster on 2, IIS_COV_3 and IIS_COV_l were faster on 1 each, with all three
indistinguishable on one. If we try to verify our assumptions on strengths
of each algorithm, we see that IIS_COV_3 takes fewer pivots both to find
the first IIS and on average; but requires more IISs to solve the cover
problem only on ITEST6. IIS_COV_l does find smaller IISs on average
than the other algorithms. Not much more performance information can
be obtained from the small problems.
Algorithmic comparisons for the midsized problems are pre
sented in Table 5.3. We have several interesting problems in terms of the
size of the min weight IIS covering problem solved. With these harder
problems, we see a number of interesting trends. In 10 of the 12 prob
lems, IIS_COV_3 takes fewer pivots to find an initial IIS as expected.
However, this algorithm has the lowest average number of pivots per IIS
in only 7 of the 12 problems. What we see is that both IIS_COV_l and
IIS_COV_2 typically take more pivots to find an initial solution. However,
only a few pivots, typically fewer than 25, are needed to find IISs satisfy
ing optimality conditions for the alternative system after the initial basic
feasible solution is found. Thus some of the advantage of IIS_COV_3 is
lost when finding many IISs. In fact, on those problems where IIS_COV_3
took fewer pivots to find its initial IIS but had a higher average pivot
value, an algorithm needing to find a larger number of IISs to solve the
covering problem had the lowest average pivot value. Thus the more IISs
73
one needs to find, the less important the initial number of pivots becomes
in terms of solution time.
Additionally, we see that IIS_C0V_3 solves the covering problem
faster on 8 of the 9 problems with time distinctions. We also note that
it finds the smallest average I IS on 3 of the 9 problems where distinction
is made, and finds more IISs in solving the cover on only 4 problems and
finds the least IISs in solving the cover 5 times (excluding ties). This seems
to contradict the intuition that we would find IISs faster, but require more
IISs to solve the covering problem.
As we look at the results for the large problems (see Table 5.4),
we see that an undirected search for IISs is faster. IIS_C0V_3 again
dominates, being the fastest algorithm on 8 of the 9 problems, taking the
fewest pivots to the first IIS on all problems, and taking fewest average
number of pivots on 6 of 9 problems. It also finds the smallest average IIS
on 4 of 6 problems where distinction is made.
We also compare (Table 5.5) the information provided by the
IIS cover to that obtained from IIS isolation via MINOS(IIS) (from [11]).
Many of the problems in this test bed were created by taking a feasible LP
instance and modifying a single bound or constraint until the problem was
infeasible. Four of the problems in the test bed we know to be infeasible
in original form BGDBG1, BGPRTR, GREENBEA, and M0ND0U2.
Of these problems, only BGPRTR has an IIS cover of 1 (and requires a
single IIS to solve the cover). Thus although there are a large number of
problems in the test bed having singleton I IS covers and requiring only a
single IIS to find their cover, this may be an artifact of their construction.
74
Problem Algorithm Cover # IISs Pivots Avg. IIS Smallest IIS
Time Generated IIS 1 Avg. Size Rows Size Rows
BGDBGl IIS_COV_l 8.05 33 112 12.4 8.1 7.4 2 2
BGDBG1 IIS_COV_2 6.15 24 112 14.6 7.0 6.5 2 2
BGDBGl IIS_COV_3 7.74 36 34 8.6 6.9 6.1 2 2
BGETAM IIS_COV_l 10.42 5 242 206.8 68.0 62.2 8 7
BGETAM IIS_COV_2 11.79 6 150 145.4 59.5 51.7 13 12
BGETAM IIS_COV_3 9.24 7 20 89.1 173.1 140.7 18 17
BOX1 IIS_COV_l 1.46 2 13 36.0 53.5 52.5 10 9
BOX1 IIS_COV_3 1.46 2 12 34.3 54.5 53.5 10 9
CHEMCOM IIS_COV_l 3.74 2 177 136.0 26.0 16.0 25 15
CHEMCOM IIS_COV_2 3.73 2 177 142.0 24.0 14.0 23 13
CHEMCOM IIS_COV_3 3.63 1 137 204.5 27.0 15.0 27 15
EX72A IIS_COV_l 1.35 3 104 27.0 69.0 68.0 59 58
EX72A IIS_COV_2 1.66 3 104 39.5 70.3 69.3 61 60
EX72A IIS_COV_3 1.22 2 108 36.0 66.5 65.5 59 58
EX73A IIS_COV_l 0.92 1 88 44.0 28.0 27.0 28 27
EX73A IIS_COV_3 0.97 1 79 42.5 26.0 25.0 26 25
KLEIN2 IIS_COV_l 8.03 13 597 85.4 53.2 53.2 53 53
KLEIN2 IIS_COV_2 5.46 4 574 173.8 54.0 54.0 53 53
KLEIN2 IIS_COV_3 5.38 6 476 113.9 55.2 55.2 53 53
PANG IIS_COV_l 3.21 1 392 204.5 16.0 13.0 16 13
PANG IIS_COV_2 2.59 1 250 127.5 16.0 13.0 16 13
PANG IIS_COV_3 2.65 2 183 76.3 19.5 16.0 18 15
QUAL IIS_COV_l 8.05 5 707 149.3 185.4 124.0 142 92
QUAL IIS_COV_2 12.12 5 707 223.2 184.8 103.6 143 82
QUAL IIS_COV_3 7.40 6 558 107.9 180.6 124.0 134 90
REACTOR IIS_COV_l 5.58 2 152 192.0 5.0 1.0 5 1
REACTOR IIS_COV_2 4.44 2 152 125.7 5.0 1.0 5 1
REACTOR IIS_COV_3 3.89 2 100 119.3 5.0 1.0 5 1
REFINERY IIS_COV_l 22.26 38 665 42.5 135.2 91.2 92 61
REFINERY IIS_COV_2 19.99 31 665 48.1 134.0 89.0 93 63
REFINERY IIS_COV_3 16.51 23 577 72.6 145.7 93.4 97 62
VOL1 IIS_COV_l 13.45 13 699 83.3 180.8 121.7 137 91
VOL1 IIS_COV_2 20.70 10 699 278.5 180.3 121.6 137 91
VOL1 IIS_COV_3 10.75 8 715 138.6 182.6 120.9 160 104
Table 5.3: Results for Midsized Problems
75
Problem Algorithm Cover Time # IISs Generated Pivots Avg. IIS Smallest IIS
IIS 1 Avg. Size Rows Size Rows
BGINDY IIS_COV_l 139.19 i 1908 1140.0 3.0 3.0 3 3
BGINDY IIS_COV_3 126.34 i 219 1114.0 3.0 3.0 3 3
CERIA3D IIS_COV_l 56.32 3 1905 758.0 123.3 123.3 73 73
CERIA3D IIS_COV_2 66.46 3 2406 921.0 141.3 141.3 74 74
CERIA3D IIS_COV_3 26.45 8 538 99.0 144.8 144.8 73 73
CPLEX1 IIS_COV_l 38.50 1 1473 1214.5 5.0 5.0 5 5
CPLEX1 IIS_COV_3 33.83 1 212 1058.5 5.0 5.0 5 5
GOSH IIS_COV_l 563.91 1 6009 3305.5 49.0 49.0 49 49
GOSH IIS_COV_3 637.34 2 1885 2350.0 72.0 72.0 68 68
GREENBEA IIS_COV_l 410.50 3 2983 1955.8 9.0 6.3 4 2
GREENBEA IIS_COV_2 359.95 4 2983 1319.6 17.8 15.0 4 2
GREENBEA IIS_COV_3 322.34 3 10 1442.8 8.3 5.3 4 1
KLEIN3 IIS_COV_l 97.16 29 1571 506.0 101.7 101.7 95 95
KLEIN3 IIS_COV_2 49.77 12 1560 538.8 87.4 87.4 86 86
KLEIN3 IIS_COV_3 36.34 21 1137 205.6 85.8 85.8 84 84
MEXP IIS_COV_l 12.37 2 377 157.0 8.0 8.0 7 7
MEXP IIS_COV_3 8.76 1 176 237.5 6.0 6.0 6 6
MONDOU2 IIS_COV_l 17.69 14 503 60.8 163.5 146.6 22 17
MONDOU2 IIS_COV_2 118.63 13 503 58.1 182.3 163.8 22 17
MONDOU2 IIS_COV_3 17.11 9 460 62.6 146.9 128.9 22 17
PILOT4I IIS_COV_l 28.82 1 659 930.0 1.0 1.0 1 1
PILOT4I IIS_COV_2 18.05 1 1010 629.0 1.0 1.0 1 1
PILOT4I IIS_COV_3 7.20 1 86 202.5 1.0 1.0 1 1
Table 5.4: Results for Large Problems
76
We feel that the min weight I IS cover will be a valuable tool in debugging
LPs at the model development and integration stage.
In order to gain a perspective on the solution time to solve the
MCIC problem exactly, we make a comparison with the heuristic ap
proach of Chinneck [12] on a subset of the NETLIB infeasible library.
Chinnecks runs were made using a modified version of MINOS(IIS) on
an IBMcompatible 66 MHz 80486DX2 microcomputer. Chinnecks results
are presented in [12] in terms of a time ratio: the covering time divided by
the Phase 1 solution time. We convert our results into the same form, so
the comparison is as fair as possible (considering that we use a different
optimization package). These results are presented in Table 5.6.
It is interesting to note that Chinnecks heuristic finds the min
imum cardinality cover in all instances; however, as demonstrated previ
ously, it will not guarantee a minimal cover upon termination. The times
presented are particularly intriguing since the time ratio to solve exactly
is smaller on 6 of the 14 problems! We should also note that in solving
exactly a large set of IISs is determined. Using Chinnecks algorithm, no
IISs are identified. In [12], an extension is given for doing so, but the CPU
times presented are for cover identification only. Thus, more information
is given in less time on a substantial portion of the test bed by solving
optimally!
77
Problem MINOS(IIS) Min I IS Cover Smallest I IS
Rows Cardinality I ISs Found Size Rows
BGDBG1 2 12 38 2 2
BGETAM 7 1 5 8 7
BGINDY 1 1 3 3
BGPRTR 5 1 1 7 7
BOX1 8 1 2 10 9
CERIA3D 73 1 3 73 73
CHEMCOM 7 1 2 23 13
CPLEX1 5 1 1 5 5
EX72A 58 1 3 59 58
EX73A 24 1 1 26 25
FOREST6 55 1 2 64 59
GALENET 2 1 1 6 3
GOSH 1 1 49 49
GREENBEA 1 2 3 4 1
ITEST2 3 2 3 3 3
ITEST6 2 2 3 3 3
KLEIN1 50 1 1 51 51
KLEIN2 51 1 4 53 53
KLEIN3 74 1 21 84 84
MEXP 5 1 1 6 6
MONDOU2 15 3 9 22 17
PANG 11 1 1 16 13
PILOT4I 1 1 1 1 1
QUAL 76 1 6 134 90
REACTOR 1 1 2 5 1
REFINERY 47 1 38 92 61
VOL1 80 1 10 137 91
WOODINFE 1 2 2 2 1
Table 5.5: Min IIS Cover and MINOS(IIS) IIS Isolation Comparison
78
Finally, we compare this approach with the fixed charge formu
lation presented in Section 2.4:
mm E=1
subject to
Ax + s s' = b
s' < Mz for constant M sufficiently large
x, s >0
z binary
The fixed charge IP formulations were solved on the RS6000 com
puter using version 3.0 of the CPLEX optimization library. Results for
this comparison are given in Table 5.7. The time given is CPU seconds to
completely solve the problems. The Min IIS Cover results presented are
for the variant IIS_COV_3. The test bed consists of a subset of problems
from the NETLIB infeasible library. For small problems (WOODINFE,
ITEST2, and ITEST6), the fixed charge approach outperforms the MWIC
approach. However, the largest of these problems is WOODINFE with 35
constraints and 89 variables. As we move to larger problems, we see that
the fixed charge formulation becomes increasingly more difficult to solve.
CPLEX was unable to prove the optimality of the integer solution for the
BGDBG1 problem, which has 348 constraints and 407 variables, given a
maximum of 20,000 nodes for the branch and bound tree. The time to
solve this problem is thus greater than the 825 seconds taken to evalu
ate 20,000 nodes. IIS_COV_3 solves the largest problem in this test bed,
MONDOU2 (312 constraints and 604 variables), in approximately 6% of
79
the time the fixed charge formulation takes. Thus, as problem size in
creases, the MWIC formulation becomes the preferred algorithm.
80
Problem MINOS(IIS) Min IIS Cover
Cardinality Time Ratio Cardinality Time Ratio
BGDBG1 12 55.5 12 24.6
BGINDY 1 0.2 1 3.4
BGPRTR 1 1.0 1 1.5
CHEMCOM 1 0.6 1 4.3
CPLEX1 1 1.3 1 1.2
GREENBEA 2 2.1 2 3.1
ITEST2 2 1.0 2 35.0
ITEST6 2 2.2 2 16.3
KLEIN2 1 1.7 1 1.4
KLEIN3 1 6.0 1 3.1
M0ND0U2 3 69.3 3 26.3
REACTOR 1 7.1 1 1.9
REFINERY 1 7.1 1 10.6
WOODINFE 2 2.5 2 6.8
Table 5.6: Min IIS Cover and MINOS(IIS) IIS Cover Comparison
Problem Fixed Charge Min IIS Cover
Time Time
BGDBG1 >825.00 7.74
ITEST2 0.18 0.36
ITEST6 0.30 0.65
KLEIN2 307.50 5.38
MONDOU2 297.21 17.11
WOODINFE 0.24 0.48
Table 5.7: Min IIS Cover and Fixed Charge IIS Cover Comparison
81
6. Extensions to Solving the Linear Discriminant Problem
We now consider the problem of finding a linear separator, or
separating hyperplane for two sets of data. Given two point sets A1
and A2 (where the coordinates of a point correspond to a row of the ap
propriate matrix), we wish to identify a hyperplane H = {cto:h = 6} such
that cth > b if a Â£ A1 and cth < b if a Â£ A2. If such a hyperplane H
exists, we say that the sets A1 and A2 are linearly separable. In the case
where the sets are not linearly separable, for any h and b there exists a
point (WLOG) a Â£ A1 such that cth < b and we say that a is misclassified
for this h and b. Thus, if the sets are not linearly separable, we wish to
obtain the hyperplane that minimizes some measure of misclassification
of points. This classification problem has a variety of applications across
a large spectrum of disciplines including pattern recognition and neural
networks. Figure 6.1 demonstrates a linear separable system with an opti
mal separating hyperplane (left) and a nonlinearly separable system with
a hyperplane minimizing the number of misclassifications (right).
o
o
o
Figure 6.1: Linearly Separable (left) and NonSeparable (right) Sets
We can formulate the problem of finding a linear discriminant as
the following feasibility problem:
1. cth b > e
2. ahb < 0
h, b free
for all a Â£ A1
for all a Â£ A2
Note that any feasible solution h and b to the linear program
will define a hyperplane separating the sets A1 and A2. We force a true
separation of the sets by restricting the points of A1 to be distance at
least efrom the hyperplane. This also eliminates the trivial solution h = 0,
6 = 0. We need not force the points of set A2 off of cth = 6, since our true
separator is the hyperplane cth = 6 + (e/2). Also note that the choice of
objective is arbitrary at this point if the sets are separable, we care only
to find a separating hyperplane. There are many modifications we can
make to this formulation in order to bias the hyperplane towards one
set or the other (for example, see Glover [20] or Bennett and Mangasarian
[5])
This linear programming formulation is infeasible if there is no
separating hyperplane. If we find the minimum weight IIS cover, we have
found the minimum weight subset of points which must be removed from
the system in order for a feasible solution to be found. In other words, we
will find the minimum weight subset of points which must be misclassified
in order that a separator be found for the remaining points.
Using Theorem 5.1, we obtain the following alternative system
83
for the discriminant problem:
1. yT A1 + zT A2 = 0
2. yT zT =0
3. ~yTe = 1
y < 0, z > 0
Since the problem of minimizing the number or weight of mis
classified points is NP hard, research efforts have focused on identifying
linear programming formulations which minimize different measures of the
misclassification and on heuristic approaches to approximating the true
minimum cardinality/weight set of misclassified points.
We can compare the performance of this exact formulation with
a linear programming formulation due to Bennett and Mangasarian [5].
Let us assume that there are m points in A1 and k points in A2. Then
Bennett and Mangasarian solve the following:
min YJ?=ieilm + EL fi/k
subject to
+ 1 A G > e for all a Â£ A1
i 1 A 8 < 0 for all a Â£ A2
e, f > 0
h, b free
The principal property that distinguishes this formulation from
other linear programming methods is that for the linearly inseparable case
this formulation will always generate a nontrivial solution to the linear dis
criminant problem and does so without the addition of extra constraints.
Note the similarity between this formulation and a standard Phase 1 LP;
84
the vectors e and f are the artificial or elastic variable vectors of a Phase
1 formulation, and the objective seeks to minimize a normalization of the
sum of infeasibilities.
In [5], Bennett and Mangasarian compare this formulation with a
number of others on samples consisting of data points from the Wisconsin
Breast Cancer Database (see the same article for a complete description).
This data was collected by by Dr. William H. Wolberg of University of
Wisconsin Hospitals in Madison. The data base consists of malignant
and benign samples collected in a 9dimensional space. Of the formula
tions they examined, theirs performed the best in terms of both fewest
misclassifications and computer time used.
This application lends itself to a deeper discussion of the prac
ticality of the linear discriminant problem. What we are really looking
for is a solution, or separating hyperplane, which can be found on a small
sample set of the data. This sample set is commonly called a training set
in the neural network community. Once we have obtained this separating
hyperplane, it can be used to make decisions about the category which
other data points fall into. So, by looking at a representative sample of
data points whose classification we know, we wish to identify a classifica
tion strategy and then test the classifier on expanded data sets. The
Wisconsin Breast Cancer Database is being used to develop an intelligent
tissue analyzer.
In order to evaluate the effectiveness of our MWIC algorithm, we
made a set of comparisons on the same data set. We used the 353 data
points of Group 1 of the data set, of which 165 are malignant and 188 are
85
benign. The data set is inseparable, so we seek to minimize the number of
misclassified points. The main question to be answered here is how well
do the current state of the art LP formulations perform in this task and
does our exact approach solve the problem in a timely manner.
Our alternative system is based upon the previously given feasi
bility problem, which is identical to Bennett and Mangasarians LP for
mulation with the exclusion of the elastic variables e and /.
We noted the similarity between the Bennett and Mangasarian
formulation and that of a Phase 1 LP, and also decided to see how much
better a solution they find over a standard Phase 1 LP. In our compar
isons, we also included a version of their formulation without the elastic
variables e and /. Upon completion of a Phase 1 LP, the artificial variables
correspond to data points which have been misclassified.
The Phase 1 LP and Bennett and Mangasarians formulation
were run using the CPLEX optimization package. We modified a version
of our best performing MWIC algorithm, IIS_C0V_3. The algorithm was
modified to find a set of disjoint IISs prior to solving the covering sub
problem. The idea behind this modification was to reduce the amount
of time needed to solve the MCIC problem optimally. Again, this code
is based upon the IBM OSL optimization package object libraries. All
comparisons were run on an IBM RS6000. The results are presented in
Table 6.1
IIS_C0V_3 BM Phase 1
Misclassified 6 25 25
CPU Time (sec) 739.3 1.3 1.0
Table 6.1: Linear Discriminant Analysis Comparison
86
It is interesting to note that the BennettMangasarian (BM)
formulation misclassifies the same number of points as a standard Phase
1 LP. From this example, it appears that the extra effort in solving these
problems exactly is worth it from a solution quality viewpoint. Although
the exact solution took approximately 570 times longer to reach than the
BM formulation, it still took less than 15 minutes of computing time 
relatively small for a problem which you would be interested in solving
only once.
Another interesting result is that all 6 points which were mis
classified by the MCIC algorithm were benign even without explicitly
weighting misclassifications in this direction as being more favorable. In
contrast, for both the Phase 1 and BM formulations, 14 malignant and 11
benign points were misclassified. In a true classification system, it would
be desirable to err on the side of classifying benign as malignant rather
than the reverse.
It appears that this approach is a viable means of solving linear
discriminant problems of fair magnitude.
87
7. Summary and Areas for Further Research
We have developed an algorithm for finding the MWIC of an
infeasible system of linear equations. We have demonstrated the utility
of this algorithm for infeasibility analysis of linear programming problems
and in linear discriminant analysis where we choose to minimize the num
ber of misclassified points.
In addition to this algorithmic development, we have noted that
these covering problems have a structure to them which seems to make
them more tractable than general set covering problems. We have explored
the facial structure of these covering polyhedra and identified facet defining
inequalities. We have also generalized these results to a larger class of
covering problems, called polyhedral covering problems.
We have reviewed the theory of irreducible inconsistent subsys
tems and provided a generalization of Van Loons result. Additionally,
we have established a link between the method of Gleeson and Ryan with
Van Loons.
We have evaluated a number of prototypes of our algorithm on
the NETLIB infeasible library and demonstrated the utility of these algo
rithms on a few industry examples of infeasible LPs. The problems in the
NETLIB infeasible library in many instances are feasible problems which
have been perturbed, perhaps artificially, into infeasible instances. At this
point, it would be interesting to analyze other infeasible industry problems
to determine on what types of problems the MWIC approach provides a
useful infeasibility isolation.
We have also compared this algorithm with a heuristic proposed
by Chinneck, and found that on many problems solving optimally takes
less time than solving heuristically. This may be due in part to the differ
ences in implementation. Our algorithms solve the alternative system of
the original infeasible system, which is essentially the dual of that problem.
Chinnecks method involves solving many Phase 1 instances of subprob
lems of the original infeasible system. Such factors as cover size, size
of individual IISs, and problem size probably contribute to making the
optimal cover more tractable.
We are also interested in determining the utility of identifying
I ISs by searching for extreme rays of the alternative system directly (either
in the alternative system, or in the original infeasible system). This may
help speed up the algorithm a small amount. A version of our code which
finds a maximal set of disjoint IISs before solving the covering subproblem
also looks very promising in terms of reducing the number of I ISs necessary
to find the optimal cover (and thus reducing total CPU time).
We would also be interested in determining if inclusion of facets
in a modified branch and cut algorithm would be beneficial to reducing the
time needed in the covering subproblem. At the other extreme, we could
try to minimize the amount of time spent on the covering subproblem by
using a heuristic.
89
BIBLIOGRAPHY
[1] Amaldi E., From Finding Maximum Feasible Subsystems of Linear
Systems to Feedforward Neural Network Design, Ph.D. Dissertation,
Fcole Polytechnique Federate de Lausanne, 1994.
[2] Amaldi E., and Kann V., The Complexity and Approximability of
Finding Maximum Feasible Subsystems of Linear Relations, to appear
in Theoretical Computer Science. (Also appearing as Technical Report
ORWP1193, Ecole Polytechnique Federate de Lausanne, 1993).
[3] Amaldi E., and Kann V., On the Approximability of Removing the
Smallest Number of Relations from Linear Systems to Achieve Fea
sibility, Technical Report ORWP694, Ecole Polytechnique Federate
de Lausanne, 1994.
[4] Balas E., and Ng S., On the Set Covering Polytope: I. All the Facets
with Coefficients in {0, 1, 2}, Mathematical Programming, Vol. 43
(1989).
[5] Bennett K.P., and Mangasarian O.L., Robust Linear Programming
Discrimination of Two Linearly Inseparable Sets, Optimization Meth
ods and Software, Vol. 1 (1992), pp. 2334.
[6] Berge C., Hypergraphs, NorthHolland, Amsterdam, 1989.
[7] Boneh A., Identification of Redundancy by a Set Covering Equiv
alence, in Operational Research 84, edited by Brans J.P., Elsevier
Science Publishers B. V., Amsterdam, The Netherlands, 1984, pp.
407422.
[8] Carver W. B., Systems of Linear Inequalities, Annals of Mathematics,
Vol. 23 (19211922), pp. 212220.
[9] Chakravarti N., Some Results Concerning PostInfeasibility Analysis,
European Journal of Operational Research, Vol. 73 (1994), pp. 139
143.
[10] Chinneck J., Finding Minimal Infeasible Sets of Constraints in Infea
sible Mathematical Programs, Technical Report SCE9301, Depart
ment of Systems and Computer Engineering, Carleton University,
Ottawa, Canada, 1993.
[11] Chinneck J., Finding the Most Useful Subset of Constraints for Anal
ysis in an Infeasible Linear Program, Technical Report SCE9307,
Department of Systems and Computer Engineering, Carleton Uni
versity, Ottawa, Canada, 1993.
[12] Chinneck J., An Effective Polynomial Time Algorithm for the Mini
mum Cardinality IIS Set Covering Problem, Technical Report SCE
9502, Department of Systems and Computer Engineering, Carleton
University, Ottawa, Canada, 1995.
[13] Chinneck J., and Dravnieks E., Locating Minimal Infeasible Con
straint Sets in Linear Programs, ORSA Journal on Computing, Vol.
3 (1991), pp. 157168.
[14] Chvatal V., A Greedy Heuristic for the Set Covering Problem, Math
ematics of Operations Research, Vol. 4 (1979), pp. 233235.
[15] Debrosse C., and Westerberg A., A FeasiblePoint Algorithm for
Structured Design Systems in Chemical Engineering, American In
stitute of Chemical Engineers Journal, Vol. 19 (1973), pp. 251258.
[16] Dyer, M., The Complexity of Vertex Enumeration Methods, Mathe
matics of Operations Research, Vol. 8 (1983), pp. 381402.
[17] Fan K., On Systems of Linear Inequalities, in Annals of Mathematical
Studies Number 38: Linear Inequalities and Related Systems, edited
by Kuhn H.W. and Tucker A.W., Princeton University Press, Prince
ton, NJ, 1956, pp. 99156.
[18] Gary M., and Johnson D., Computers and Intractability, W.H. Free
man, New York, 1979.
[19] Gleeson J., and Ryan J., Identifying Minimally Infeasible Subsystems
of Inequalities, ORSA Journal on Computing, Vol. 2 (1990), pp. 61
63.
[20] Glover F., Improved Linear and Integer Programming Models for
Discriminant Analysis, in Creative and Innovative Approaches to the
91
Science of Management, edited by Ijiri Y., Quorum Books, Westport,
CT, 1993.
[21] Greenberg H.J., Consistency, Redundancy, and Implied Equalities in
Linear Systems, UCD/CCM Report No. 14, Mathematics Depart
ment, University of Colorado at Denver, 1993.
[22] Greenberg H.J., Diagnosing Infeasibility in Mincost Network Flow
Problems Part II: Primal Infeasibility, IMA Journal of Mathematics
Applied in Business and Industry, Vol. 2 (1988/9), pp. 3950.
[23] Greenberg H.J., Diagnosing Infeasibility in Mincost Network Flow
Problems Part I: Dual Infeasibility, IMA Journal of Mathematics in
Management, Vol. 1 (1987), pp. 99109.
[24] Greenberg H.J., An Empirical Analysis of Infeasibility Diagnosis for
Instances of Linear Programming Blending Models, IMA Journal of
Mathematics Applied in Business and Industry, Vol. 4 (1992), pp.
163210.
[25] Greenberg H.J., How to Analyze the Results of Linear Programs Part
3: Infeasibility Diagnosis, Interfaces, Vol. 23, No. 6 (1993).
[26] Greenberg H.J., and Murphy F.H., Approaches to Diagnosing Infea
sibile Linear Programs, ORSA Journal on Computing, Vol. 3, No. 3
(1991), pp. 253261.
[27] Motzkin T.S., Contributions to the Theory of Linear Inequalities,
Doctoral Dissertation, University of Basel, 1933, translated by D.R.
Fulkerson, in Theodore S. Motzkin: Selected Papers, edited by Cantor
D., Gordon B., and Rothschild B., Birkhauser,1983.
[28] Murty K., Linear Programming, John Wiley and Sons, 1983.
[29] Nemhauser G., and Wolsey L., Integer and Combinatorial Optimiza
tion, John Wiley and Sons, 1988.
[30] Pulleyblank W., Personal Communication to J. Ryan.
[31] Roodman G., PostInfeasibility Analysis in Linear Programming,
Management Science, Vol. 25 (1979), pp. 916922.
[32] Ryan J., Transversals of IISHypergraphs, Congressus Numerantium,
Vol. 81 (1991), pp. 1722.
92
[33] Ryan J., IISHypergraphs, preprint, 1993.
[34] Sankaran J.K., A Note on Resolving Infeasiblity in Linear Pro
grams by Constraint Relaxation, Operations Research Letters, Vol.
13 (1993), pp. 1920.
[35] Schrijver, A., Theory of Linear and Integer Programming, John Wiley
and Sons, 1986.
[36] Van Loon J., Irreducibly Inconsistent Systems of Linear Inequalities,
European Journal of Operations Research, Vol. 8 (1981), pp. 283288.
93

Full Text 
PAGE 1
ASET CO VERINGAPPR O A CHTO INFEASIBILITYANAL YSISOFLINEAR PR OGRAMMINGPR OBLEMSANDRELA TED ISSUES b y MarkRic hard P ark er B.A.,Univ ersit yofColorado at Den v er,1984 M.S.,Univ ersit yof Colorado at Den v er,1992 Athesis submitted to the F acult yoftheGraduate Sc hool ofthe Univ ersit yof Colorado atDen v er in partial fulllmen t of therequiremen tsforthedegreeof Doctor ofPhilosoph y Applied Mathematics 1995
PAGE 2
This thesis fortheDoctor ofPhilosoph y degreeb y MarkRic hard P ark er has beenappro v edb y JenniferRy an Harv eyGreen berg GaryKoc hen berger J.Ric hardLundgren BurtSimon Date
PAGE 3
P ark er,Mark Ric hard(Ph. D.,Applied Mathematics) ASetCo v eringApproac htoInfeasibilit yAnalysisofLinearProgramming Problems and RelatedIssues Thesis directedb yAssociate Professor JenniferRy an ABSTRA CT With the increased sophistication of both computers and optimizationsoft w are,linearprogrammingproblemsofasizeinconceiv ableto solv e only a few y ears ago are no w readily accessible. As model size and complexit yincrease,theissueoffeasibilit ybecomesamajorissueinmodel dev elopmen t. This thesis explores the analysis of linear programming infeasibilit y through the use of Irreducible Infeasible Subsystems or IISs. Inparticular,w edev elopaconstrain tgenerationalgorithmforidentifyingtheminim umw eigh tIISco v er,whic hisolatesaminimalw eigh tset of constrain ts whose remo v al fromthesystemyields a feasible system. It hasbeensho wnthatthissetco v eringproblemhasav eryspecialstructure. W ealsoexplorethefacialstructureofthesetco v eringpolyhedraandprovide a generalization to a class of co v ering problems. The link bet w een this problemand thelinear discriminan t problem is also explored. This abstract accurately represen tsthe con ten t of the candidate's thesis. Irecommendits publication. Signed Jennifer Ry an iii
PAGE 4
CONTENTS Chapter 1. In troduction : : : : : : : : : : : : : : : : : : : : : : : : : 1 2. Finding the Maxim um W eigh t F easible Subsystem of an Infeasible Systemof Linear Equations : : : : : : : : : : : 3 2.1 In troduction andNotation : : : : : : : : : : : : : : 3 2.2 Bac kground onIISs : : : : : : : : : : : : : : : : : : 7 2.3 Hypergraph F ramew ork : : : : : : : : : : : : : : : : 13 2.4 T ec hniquesin Appro ximating theMWFS : : : : : : 17 3. Extensions and Unications of IISResults : : : : : : : : : 29 3.1 Examination ofV anLoon's Method : : : : : : : : : 29 3.2 V anLoon'sMethodandtheGleesonandRy anMethod 37 4. F acial StructureoftheIISCo v erP olyhedron : : : : : : : 40 4.1 Dimension of theMinW eigh t IISCo v eringP olytope 40 4.2 Kno wnPropertiesoftheGeneralSetCo v eringP olytope 42 4.3 Properties oftheMin W eigh tIISCo v ering P olytope 44 4.4 Generalizations : : : : : : : : : : : : : : : : : : : : : 52 5. Algorithm Description and Computational Results : : : : 55 5.1 In troduction : : : : : : : : : : : : : : : : : : : : : : 55 5.2 Min IISCo v erIsolation in Practice : : : : : : : : : 57 5.3 F orm ulation of P the Alternativ e P olyhedron, for General Linear Programming Problems. : : : : : : : 62 5.4 Finding IISs : : : : : : : : : : : : : : : : : : : : : : 64
PAGE 5
5.5 Heuristic Solution of Co v eringProblems : : : : : : : 67 5.6 Computational Results : : : : : : : : : : : : : : : : 68 6. Extensions toSolving theLinear Discriminan t Problem : 82 7. Summaryand Areasfor F urtherResearc h : : : : : : : : : 88 Bibliograph y : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 90 1
PAGE 6
1. In troduction This thesis is organized as follo ws. Chapter 2 in troduces the problem of nding a maxim umw eigh t feasible subsystem of an infeasible system of linear inequalities (the MWFSproblem). W ereview past w ork on this problem, including the notion of an Irr e ducible Inc onsistent Subsystem or IIS. W e use a constrain t generation algorithm com bined with branc h and bound to solv e the MWFS problem. Our approac h is based on nding theminim umw eigh tco v ero v erall IISs,whic his equiv alen tto ndingtheminim umw eigh tsetofinequalitiestoremo v efromtheinfeasiblesysteminordertorestorefeasibilit y W edenotethisco v eringproblem as theMWICproblem. Chapter3con tainsnewextensionsandunicationstothetheory of IISs. Chapter4con tainsnewtheoreticalresultsobtainedinexamining thefacial structureoftheMWICproblem. Inparticular, w edemonstrate thatallco v eringconstrain ts,whic hcorrespondtotheIISsoftheinfeasible system, are facets of the MWIC problem. W e also examine a generalizationoftheseresultstoacategoryofproblemscalled\polyhedral co v ering problems." Chapter5describesanalgorithmforsolvingtheMWICproblem, and presen ts computational results. Also, a comparison is made bet w een thealgorithmandaxedc hargein tegerprogramform ulationoftheMWIC problem.
PAGE 7
Chapter 6 discusses further applications of the algorithm to the linear discriminan t problem. Chapter 7 summarizes the results and discusses areas still open for furtherresearc h. 2
PAGE 8
2. Finding the Maxim um W eigh t F easible Subsystem of an Infeasible System of Linear Equations Inthis c hapter,w ewill establish notation and presen ttheproblem of nding a maxim umw eigh tfeasible subsystem ofan infeasible systemof linear equations. 2.1 In troduction and Notation Let A be an m n real matrix and let b be a real m {v ector. W e thendene S = f A x b g as thesystemof linear inequalities arising from A and b Let M = f 1 ;:::;m g bethesetindexingthero wsof A W e denethefollo wing subsystemsof S forasubsetofthero wsof A I M S ( I )= f A i x b i for i 2 I g S n S ( I )= f A i x b i for i 62 I g S n i = S nf A i x b i g S = = f A i x b i j A i x = b i for i 2 M andfor all x satisfying A x b g If there exists an x satisfying all inequalities in S then S is feasible,and x isfeasiblein S Ifthereisno x satisfyingallinequalitiesof S ,w esa ythat S isinfeasible. Similarly ,if S ( I )isfeasiblefor I M ,then S ( I )is called a feasible subsystem If S ( I )is infeasible for I M w e call S ( I ) an infeasible subsystem If S ( I ) is a feasible subsystem and S ( I ) S f A i x b i g is infeasible for ev ery i 62 I then S ( I ) is a maximal
PAGE 9
feasible subsystem Similarly if S ( I ) is an infeasible subsystem and S ( I 0 ) is a feasible subsystem for ev ery I 0 I then S ( I ) is a minimal infeasible subsystem or an irreducible infeasible subsystem (IIS). If S is feasible, then S = is thesetof implicit equalities of S In the general setting, w e will also ha v e nonnegativit y constrain ts on x W e denethe set of functional constrain ts to be the set of constrain ts exclusiv eof all nonnegativit y constrain ts. Insome instances, w e will wish to distinguish bet w een nonnegativit y constrain ts and functionalconstrain tswhenw eareiden tifyingIISs. W ein troducethefollo wing denition due to Chinnec k and Dra vnieks [13]: An irreducible inconsisten t set of functional constrain ts (IISF)is thecompletesubset of functional constrain ts in an IIS. Suppose that S is infeasible. W e dene a maxim um cardinalit y feasible subsystemof S as S ( I mcf )where I mcf =argmax I M fj I jj S ( I )is amaximal feasible subsystem g This extendsnaturally toamaxim um w eigh t feasible subsystemof S If w e assign w eigh ts w i to eac hro w i of A ,w e seekto nd a feasible subset of ro ws maximizing the sum of the w eigh ts. W e denote this as S ( I mwf ) where I mwf =argmax I M f X i 2 I w i j S ( I )is a maximal feasible subsystem g W ealsowishtoreviewthefollo wingbasicpolyhedraltheory W e referto the dual system of S as S d = f y T A =0 ; y T b 0 ; y 0 g : 4
PAGE 10
Muc hofthetheoryinthispaperisbasedupontheoremsofthealternativ e. Inparticular,w ewillmak euseofthefollo wingv arian tofF ark as'Theorem of theAlternativ e: Theorem 2.1 (F ark as [35]) Exactlyoneofthefollo wingholds: (1) A x b is consisten t. (2) Thereexists y 2 R m suc hthat y T A =0, y T b < 0,and y 0. Note that the alternativ e system iden tied in (2) abo v e is equiv alen t to S d S f y T b < 0 g W e will also mak e reference to the nal tableau obtained via a simplex algorithm. Giv en asystem max P n i =1 c i x i subjectto A x b x 0 where A isan m n realmatrix,w eusethefollo wingstandardLPtableau notation; x B refersthev ectorof m basicv ariables, x N referstothev ector of the remaining n m non basic v ariables, B refers to the columns of A corresponding to the basic v ariables, and N refers to the columns of A corresponding tothenon basic v ariables. Thev ector y corresponds to the dual v ariables (or reduced costs) of the system. W e dene the rate of substitution of a non basic v ariable x j with respect to a basic v ariable x i as the rate at whic h x i m ust c hange with respect to a c hange in x j to main tain theequations A x + s = b with all other non basics held xedat 0. This is the negativ e of the updated tableau en try in column j in the ro w where i is basic. Th us, if w e speak of a negativ e rate of substitution 5
PAGE 11
for non basic v ariable j with respecttobasic v ariable i ,w emeanthat the tableau en tryin column j of ro w i is positiv e. W ealso refertothe support ofav ector. W edenethesupport of a v ector x as thesetof nonzeroelemen tsof x A serious problem in dev eloping or modifying large linear programming modelsistheiden tication ofmodeling errorsandinconsistencies. Man yresearc hersha v eproposediden tifying anIISandusingthisto assistthemodelerindebuggingherform ulation(seesection2.2). Ho w ev er it is kno wn that an IIS can con tain as man y as n +1 inequalities, and thisinformationispoten tiallyuselessbecausealargesystemisdicultto comprehend. W e propose to go a step further, to iden tify the maxim um cardinalit yfeasiblesubsystem. Amorepracticalv ersionallo wstheanalyst tow eigh ttheconstrain tsaccording toimportance orrexibilit y Thenthe maxim um w eigh t feasible subsystem is sough t. Equiv alen tly w e w an t to iden tifythe minimumweight setofine qualities thatc oversall IISs ,whic h w e shall call the minimum weight IIS c over (MWIC). If w e knew what theIISsofasystem S w ere,w ecouldform ulatethefollo wing setco v ering problem, where w i is thew eigh ton the i thconstrain t. min P m i =1 w i z i subjectto P i 2 J z i 1 for all IISs, J: z i binary Unfortunately ,ithasbeensho wn(see[9])thatthen um berofIISsma ybe exponen tialinthesizeoftheoriginal problem,sow edonotw an ttowrite do wn the whole problem at once. Instead, w e will generate constrain ts 6
PAGE 12
dynamically for theproblemand solv e ititerativ ely 2.2 Bac kground on IISs IISs,also called minimal infe asible systems and minimal unsolvablesystems ,w ererstin troducedinthecon textoflinearinequalit ytheory in theearly part ofthis cen tury[8]. In his doctoral dissertation [27], Motzkin pro vides an excellen t review of the theory of linear inequalities. He extends the previous w ork b yderiving sev eralresults pertaining to systemsof inequalities, themost in terestinginthiscon textisanecessarycondition foraninconsisten tsystemto bean IIS. Theorem 2.2 (Motzkin [27]) The coecien t matrix A of an IIS f A x b g ,where A 2 R m n x 2 R n ,and b 2 R m ,has rank m 1. Motzkin pro v esthat if an infeasible system is irreducibly infeasible, then therankofthecoecien tmatrixofthesystemisonelessthanthen um ber of constrain ts in thesystem. F an[17]againconsolidatedman yofthekno wnresultsforsystems of inequalities. Additionally he presen ted the follo wing strengthening of Motzkin's c haracterization of an IIS to pro vide necessary and sucien t conditions fora systemofinequalities tobe anIIS: Theorem 2.3 (F an [17 ]) The system f A x b g is an IIS if, and only if, thefollo wing conditions hold. 1. Thereexists exactly m 1linearly independen t ro ws. 2. Thereexists y 2 R m suc hthat y A =0, yb < 0,and y > 0. F an extends Motzkin's results b y noting that a necessary and 7
PAGE 13
sucien tconditionforasystemtobeinfeasibleistheexistenceofa\special" solution to thealternativ e systemfrom F ark as'Theorem (seeTheorem2.1). Inordertoguaran teetheirreducibilit y oftheinfeasible system, thesolution tothealternativ esystemm ustha v e y > 0,ratherthan y 0 as in Theorem2.1. V anLoon[36]w asthersttoiden tifyIISswithlinearprogramming infeasibilit y analysis. He in terprets the result of F an in ligh t of the simplex method and pro v es the result giv en in Theorem 2.4. Again, w e consider the system A x + s = b with s 0 W e will solv e the system in termsof a single slac k v ariable, sa y s 1 Th us,w econsider this ro w the objectiv efunctionof alinear program. Inthenotation belo w,w ereferto thematrix A 1 astheremaining m 1 n submatrixof A aftertheremo v al ofro w1. W eadditionally usethefollo wing standardLPtableaunotation (see section 2.1); x B refers the v ectorof m 1 basic v ariables, x N refers to the v ector of the remaining n m +1 non basic v ariables, B refers to the columns of A 1 corresponding to the basic v ariables, and N refers to the columns of A 1 corresponding to the non basic v ariables. Thev ector y corresponds to thedual v ariables of thesystem. Theorem 2.4 (V an Loon [36]) Thesystem A x + s = b s 0 is anIISifandonlyifthereisaslac kv ariable, sa y s 1 ,andv ector y ,suc h that the system can be solv ed with respect to s 1 and a set x B of basic v ariables asfollo ws: (1) s 1 = y T b =y 1 P n j =2 y j s i =y 1 ; (2) x B = B 1 ( b n b 1 ) B 1 N x N B 1 ( s n s 1 ) with y T b < 0 and y 1 ; :::; y m > 0 : 8
PAGE 14
Inotherw ords,thesystemofinequalities is anIISifandonlyif upon solution of a standard Phase 1 LP w e ha v e a slac k v ariable whic h is negativ e, sa y s 1 and all other slac k v ariables ha v e a strictly negativ e rateofsubstitution withrespectto s 1 andallproblemv ariables x i ha v ea 0 rateof substitution with respectto s 1 W edemonstratethis theoremonthefollo wing example: 1 : x 2 1 2 : x 1 x 2 0 3 : x 1 x 2 4 W ebegin with theall slac kbasis, and will consider ro w3of our tableau as theobjectiv e: 2 6 6 6 6 6 6 6 6 6 6 4 x 1 x 2 s 1 s 2 s 3 RHS 0 1 1 0 0 1 1 1 0 1 0 0 1 1 0 0 1 4 3 7 7 7 7 7 7 7 7 7 7 5 Upon piv oting x 1 and x 2 in to the basis, w e ha v e the follo wing optimal tableau: 2 6 6 6 6 6 6 6 6 6 6 4 x 1 x 2 s 1 s 2 s 3 RHS 0 1 1 0 0 1 1 0 1 1 0 1 0 0 2 1 1 2 3 7 7 7 7 7 7 7 7 7 7 5 Inthistableau,w eha v e s 3 = 2 2 s 1 s 2 = 2(whic hsatises (1) fromthe theorem), x 1 =1 s 1 s 2 =1, and x 2 =1 s 1 =1 (whic h satisfy(2)fromthetheorem). Notealsothat y > 0 soalloftheconditions of Theorem2.4 aresatised, and th usthesystemis an IIS. 9
PAGE 15
V anLoonstrengthensthistheoremb yobservingthatatleastone IIScan be obtained froma nonminimally infeasible system A x + s = b s 0 b y examining the nal Phase 1 tableau. If there exists a slac k v ariable, sa y s 1 whic h is negativ e and all problem v ariables x i ha v e a 0 rateofsubstitutionwithrespectto s 1 ,thenanIIScanbeiden tiedwithin this ro was follo ws: Theorem 2.5 (V an Loon [36]) The subsystem, consisting of the constrain ts corresponding to s 1 and all slac k v ariables ha ving strictly negativ e rateof substitution with respectto s 1 ,is an IIS. V anLoon also notesthatb ypiv oting throughotherbasesofthe Phase 1 LP otherIISscan beiden tied. By using IISs as a tool in LP infeasibilit y analysis, V an Loon pro vides thefoundation of m uc hof themorerecen tw ork in thearea. Gleeson and Ry an[19]deriv ea geometricapproac h to IISidenticationthatisbaseduponF ark as'TheoremoftheAlternativ eandbasic polyhedral theory They iden tify an alternativ e system whose extreme v ertices are in one to one correspondence with the IISs of the original infeasible LP .Intheabsenceofdegeneracyofthealternativ esystem,this impro v esuponthew orkofV anLooninthat every piv otinthealternativ e systemiden ties a unique IISin theoriginal system. Theorem 2.6 (GleesonRy an [19 ]) Let A x b denote an inconsisten t set of inequalities. Then the IISs are in 11 correspondence with the extreme poin ts of the polyhedron P = f y 2 < m j y T A = 0 ; y T b = 1 ; y 0 g : In particular, the nonzero componen ts of an y extremepoin t of P indexan IIS. 10
PAGE 16
Once a basic feasible solution to the alternativ e system exists, through solution of a Phase 1 LP of the alternativ e system for instance, GleesonandRy anproposetheuseofanalgorithmduetoDy er[16]tovisit allextremepoin ts. Thisalgorithm,intheabsenceofdegeneracy ,pro vides an ecien t means of visiting all extreme poin ts. In this w a y all IISs of an infeasible system S can been umerated. Since remo v al of an y constrain t from an IIS yields a feasible subsystem,nding theminim um cardinalit y co v ero v erall IISswill identify the minim um n um ber of constrain ts to modify or remo v e from the systemto attain feasibilit y This minim um setofconstrain ts will pro vide a localization of the modeling error/inconsistency Th us, this approac h pro vides a framew orkwith whic h not only to isolate the infeasibilit y but also to diagnose the infeasibilit y T o date, this approac h had only been explored in thetheoretical sense. Recen tly Chinnec k (e.g. [13], [10], [11]) has dev eloped a set of soft w are tools to bring IIS isolation in to practical use in LP infeasibilit y analysis. The goal of these algorithms is to iden tify a small cardinalit y IISs,theidea being that thesmaller theconstrain t settheinfeasibilit y is isolated to the easier theactual infeasibilit y analysis will be. Thesetools areno wimplemen tedinthecommercialLPsolv ersMINOS(IIS),CPLEX, and LINDO. In [13], Chinnec k and Dra vnieks dev elop the foundations upon whic hthesesubroutinesarebased. Therstoftheseroutinesisa deletion lter Thedeletionlterw orksb ysequen tiallyremo vingconstrain tsfrom theLPand testing forfeasibilit y IftheLP isfeasible, thelast constrain t 11
PAGE 17
deleted is reinserted. This process is repeated un til all constrain ts ha v e been c hec k ed. The resulting system is an IIS. This algorithm can be computationally expensiv e,andsoisusedasoneofthenal piecesofthe in tegrated algorithm. Thesecondlterisan elastic lter ,whic hisbasedupontheidea ofelasticprogramming. Elasticprogrammingin v olv esthein troduction of articial v ariables whic h \stretc h" the feasible region (as in Phase 1 LP solutions). Chinnec kandDra vnieksusethisapproac htogenerateaseries ofLPsha vingv ariousconstrain tsrelaxed. Bylookingatwhic hconstrain ts ha v enonzeroarticialv ariablesineac hLP ,asubsystemcon taininganIIS can beiden tied. The nal lter is a sensitivity lter This lter is based upon performing sensitivit y analysis upon either a Phase 1 or elastic solution. The set of constrain ts ha ving nonzero shado w prices in the nal tableau of a Phase 1LP con tains at least oneIIS(see[28]). These three ltering routines can be com bined in a n um ber of w a ys to createin tegrated algorithms. Sensitivit y analysis is usually used rst, since most infeasibilit y is diagnosed upon solution of a Phase 1 LP Subsequen toperations arebasedupontheobjectiv eoftheanalystdiagnosis of single IISorm ultiple IISs. Either a com bination ofdeletion and sensitivit y ltering, or a com bination of elastic and sensitivit y ltering is used (orboth) along with anal deletion lter toiden tify theIIS. In [22], [23], [24], [25], and [26], Green berg explores tec hniques for diagnosing infeasibilit y in linear programming models. These studies 12
PAGE 18
pro vide demonstrations of the utilit y of IIS iden tication in infeasibilit y analysis b yexploring thestrengths and w eaknessesof traditional and IIS isolation tec hniques on both general and specic models. In [21], Green berg considers theoretical and computational issues in the analysis of consistency ,redundancy and implied equalities in linear programming models. Hepro videsananalysis andextensionofnecessaryandsucien t conditions for infeasible subsystems to be irreducible, and organizes the results in the follo wing theorem. W e denote the alternativ e system of S (seeTheorem2.1) as S A = f y T A =0, y T b < 0, and y 0 g Theorem 2.7 (Green berg [21 ]) If thesystem S is infeasible, then thefollo wing are equiv alen t: (1) S ( I )is an IIS. (2) rank[ A ( I )]= j I j 1andthereexistsasolution y to S A suc hthat I is thesupport of y (3) I is thesupport of anextremepoin t of f S A S y T b = 1 g (4) I is thesupport of anextremera yof S A Inthe same paper, Green berg also explores issues in iden tifying maximal feasible subsystems. W e will address these issues as w edev elop our algorithm in Chapter 5. 2.3 Hypergraph F ramew ork In[32] and [33],Ry an in v estigates the structure of the IIS h ypergraph Ah ypergraphisan n dimensionalabstractionofagraph. Ina graph,w eha v easetofv erticesandedgeswhic hconnectpairsofv ertices. In a h ypergraph, w e also ha v e a set of v ertices and edges; ho w ev er, an edge is a subset of the v ertices in V W e construct the IIS h ypergraph 13
PAGE 19
H ( V;E ) as outlined belo w. Giv en the inconsisten t system S w e let the set V index theconstrain ts of thesystem,and let theelemen tsoftheset E index the the IISs of S Th us an edge of H consists of the indices of the constrain ts of S whic h form an IIS.Atransv ersal of H is a subset of V whic h in tersects all edges of E Th us, the problem of nding a minim um cardinalit y IIS co v eris the same as nding a minim um cardinalit y transv ersal of H In[32],Ry andemonstratesanalgorithm foriden tifying minimal transv ersals without theexplicit en umerationoftheedgesof H W enote thefollo wing: Lemma 2.8 (Ry an [32]) Let H be an IISh ypergraph arising from the infeasible system S Then an y minimal transv ersal of H corresponds toaminimalsetoffacesof P thatin tersectoutsideof P ,andvice v ersa. The heuristic Ry an presen ts is based upon using the simplex algorithm to nd extreme poin ts of P Once an initial extreme poin t is found,somenonzerobasicv ariableissetto0andthisv ariableisincluded intheco v er. Then,onecancon tin uetoresolv etheLP ,setbasicv ariables to0,andupdatetheco v erun til P isempt y W edemonstratethattheco v er obtained upon completion need not be minimal. Consider the follo wing infeasible systemfor S : 14
PAGE 20
? (1) @ I (2) @ @ @ @ @ @ @ (3) @ @ @ @ @ @ @ @ @ @ @ @ (4) 1 : x 2 1 2 : x 1 x 2 2 3 : x 1 x 2 10 4 : x 1 x 2 20 x 1 and x 2 0 Then P is thesystem: 1 : y 2 y 3 y 4 0 2 : y 1 y 2 y 3 y 4 0 3 : y 1 2 y 2 10 y 3 20 y 4 = 1 y 0 W e nd a solution to P of y 1 = 0 : 2, y 2 = 0 : 1, y 3 = 0 : 1, and y 4 =0 : 0, yielding the IIS f 1 ; 2 ; 3 g If w e set y 3 =0 and resolv e the LP w e nd the solution y 1 = 0 : 1, y 2 = 0 : 05, y 3 = 0, and y 4 = 0 : 05, whic h yields the IIS f 1 ; 2 ; 4 g Ifw ealso set y 1 =0 and resolv e the LP w end that it is no w infeasible. Th us, w e ha v e iden tied the IIS co v er f 1 ; 3 g This isnotminimal, sinceremo v alofconstrain t1from S yieldsafeasible system. 15
PAGE 21
If H is a graph then it is 2uniform, whic h means that ev ery IIS of S has2elemen ts. Inthiscase,nding ah ypergraphtransv ersalis equiv alen ttondingav ertexco v er. Sincea2uniformIISh ypergraphcan con tain no cycleof odd length,a 2uniform IISh ypergraph is a bipartite graph. W e can nd a minim um v ertex co v er of an y bipartite graph in polynomial time; ho w ev er, w e can nd a minim um v ertex co v er of a 2uniform IISh ypergraph in linear timeusing a greedyalgorithm. Theorem 2.9 (Ry an [32]) Let H be a 2uniform IIS h ypergraph. Then the transv ersal obtained b y successiv ely pic king the node ha ving maxim um degree among the curren tly unco v ered edges is a minim umtransv ersal. General IIS h ypergraphs do not share this propert y; ho w ev er, theydo generalize bipartite graphs according to thefollo wing: Theorem 2.10 (Pulleyblank [30]) Let S beaninfeasiblelinear system. Then S canbe partitioned in to t w oconsisten t subsystems. Ah ypergraphisbicolorableifthereexistsapartitionofthenodes in to t w o sets suc h that neither set con tains an edge (all edges cross the partition). F rom the previous theorem, w e ha v e that an IIS h ypergraph is bicolorable. In [33], Ry an details the relationship bet w een IIS h ypergraphs and other h ypergraphs generalizing bipartite graphs. Ry an also presen ts analgorithmforndingtheminim umtransv ersalof H Thisalgorithmis based upon thefollo wing result: Theorem 2.11 (Ry an [33]) Let T bean yminimaltransv ersal of an IIS h ypergraph ha ving corresponding polyhedron P Then T is 16
PAGE 22
indexedb ythev ariables of P ha ving positiv e tableau en triesinsomero w ha ving positiv e righ t hand side forsomeextremepoin t of P Ry an then pro vides an algorithm that in the absence of degeneracy in P en umeratesall minimal transv ersals in polynomial time with respect to the size of H and so theminim um cardinalit y transv ersal can be found in time polynomial in the size of H Ho w ev er, w e should remem berthat the size of H ma ybe exponen tial in thesize of theoriginal infeasible system S ,since S ma yyield an exponen tial n um berofIISs. Theorem2.11doespro videanalgorithm foriden tifying IISco vers (though theyneednot be minimal). 2.4 T ec hniques in Appro ximating the MWFS W e ma y w onder what other tec hniques are a v ailable for iden tifying a maxim um cardinalit y feasible subsystem or a maxim um w eigh t feasiblesubsystem. Thisproblemhasbeenexaminedbefore(e.g. [26]). A standard tec hnique is to con v ert the standard Phase 1 LP (note that w e are including nonnegativit y constrain ts in this form ulation): min P m i =1 s 0 i subjectto A x + s s 0 = b x ; s ; s 0 0 in toa xedc hargeproblem: 17
PAGE 23
min P m i =1 z i subjectto A x + s s 0 = b s 0 M z forconstan t Msucien tlylarge x ; s ; s 0 0 z binary This xedc harge problem will minimize then um ber of violated constrain ts,andremo v alofthissetofconstrain tsyieldsamaxim umcardinalit y feasiblesubsystem(see[26]). This problemisextremelydicultto solv e, and a comparison with our algorithm is giv en in Chapter 5. There areman ydiculties inimplemen tingthisform ulation. Iftheconstan t M is not large enough, thenthe problemwill still be infeasible. In addition, if thev alue of M is too large, then a large n um berof fractional solutions can be in troduced in to the LP relaxation. A large v alue for M can also cause stabilit y problems as the z i v ariables can tak e on v alues belo w the soft w are tolerancefor in tegers. W e ma y also look at the standard Phase 1 solution to appro ximate the maxim um cardinalit y feasible subsystem. Using the Phase 1 form ulation from abo v e, w e mak e the follo wing observ ation about an y Phase 1 solution: Lemma 2.12 Theconstrain ts ha vingarticial v ariable nonzero atthecompletionofPhase1compriseasetoffunctionalconstrain tswhose remo v al from the infeasible system S = A x b yields a feasible system. F urther,this setof constrain ts is an IISco v er. 18
PAGE 24
Proof: Let the set I consist of the constrain ts ha ving articial v ariable nonzero at the completion of Phase 1. F or the Phase 1 solution x S ( I ) is the subsystem consisting of those i 2 M with A i x > b i whic h is infeasible. All other constrain ts are of the form A i x b i 8 i 62 I Th us remo v aloftheseconstrain tsyieldsafeasiblesubsystem,and x isafeasible solution. F urther,since remo v al of all constrain ts in I restores feasibilit y in S ,allIISsof S m ustha v eanelemen tin I Th us I also denotesanIIS co v er. Ho wgoodaboundontheminim umcardinalit yIISco v erwillthe Phase 1 solution be? W e can demonstrate that in general, w e migh t not ev en obtain a minimal cardinalit y IIS co v er from the Phase 1 solution. T o illustrate, w egiv ethefollo wing example. Let S bethefollo wing system,whic his depictedin Figure 2.1: 1 : x 2 1 2 : x 1 x 2 2 3 : x 1 x 2 10 4 : x 1 x 2 20 x 1 and x 2 0 W ethenadd thearticial v ariables a 2 a 3 ,and a 4 toconstrain ts 2, 3,and 4,obtaining thefollo wing Phase1 LP: 19
PAGE 25
? (1) 6 @ I (2) @ @ @ @ @ @ @ @ @ @ (3) @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ (4) Figure 2.1. Infeasible system demonstrating Phase 1 solution does not necessarily pro videa minimal IISco v er 20
PAGE 26
min a 2 + a 3 + a 4 1 : x 2 + 1 2 : x 1 x 2 + a 2 = 2 3 : x 1 x 2 + a 3 = 10 4 : x 1 x 2 + a 4 = 20 x 1 and x 2 0 Anoptimal solution tothis LP is x 1 =9, x 2 =1, a 2 = 10,and a 4 = 10. Th us,remo v alofconstrain ts2and4yieldsafeasiblesubsystem of S W enotethatthisisnotaminimalsetofconstrain tstoremo v e,since remo v alofconstrain t2yieldsasubsystemsatisedb y x 1 =19and x 2 =1. Th us, w e cannot guaran tee that a Phase 1 LP solution will pro vide ev en a minimal IISco v er. Recen tly ,Chinnec k[12]has dev elopedaheuristic foriden tifying the MCIC whic h is based on recognizing this idea. The algorithm uses a greedy approac h to build the co v er, where the constrain t aecting the Phase1objectiv ethemostisremo v edataparticularstepofthealgorithm. This process con tin ues un til the Phase 1 LP is yields a feasible solution to the original problem, at whic h time the set of constrain ts remo v ed from the problem corresponds to an IIS co v er. This approac h does not guaran tee ev ena minimal co v erupon completion. A comparison of this approac handanalgorithmforsolvingtheMCICproblemexactlyisgiv en in Chapter 5. APhase 1 LP can be view ed as thein troduction of elastic v ariablestoallo wthe\stretc hing"ofeac hconstrain t. Theobjectiv eistothen minimizethesumofthe\stretc hing"o v ereac hconstrain t. Byin troducing 21
PAGE 27
elastic v ariables for eac h constrain t,ratherthan justthosewith negativ e RHS, and for eac h v ariable bound, can w e then guaran tee a minimal IIS co v eras a solution to the \elastic" LP? Again, b ya similar example, the answ er is no: Let S bethefollo wing system,depictedin Figure 2.2: 1 : x 2 1 2 : x 2 0 : 5 3 : x 1 x 2 2 4 : x 1 x 2 10 5 : x 1 x 2 20 x 1 and x 2 0 W e then add the elastic v ariables e 1 e 2 e 3 e 4 e 5 e x 1 and e x 2 to constrain ts 1, 2, 3, 4, and 5, and to the nonnegativit y bounds on x 1 and x 2 ,obtaining thefollo wing elastic LP: min P x 2 1 e i 1 : x 2 e 1 1 2 : x 2 e 2 0 : 5 3 : x 1 x 2 e 3 2 4 : x 1 x 2 e 4 10 5 : x 1 x 2 e 5 20 6 : x 1 + e x 1 0 7 : x 2 + e x 2 0 AnoptimalsolutiontothisLPis x 1 =4 : 25, x 2 =5 : 75, e 1 =4 : 75, e 2 = 5 : 25, e 3 = 0 : 5, and e 5 = 10. Th us, remo v al of constrain ts 1, 2, 3, 22
PAGE 28
? (1) ? (2) 6 @ I (3) @ @ @ @ @ @ @ @ @ @ (4) @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ (5) Figure 2.2. Infeasible system demonstrating full elastic Phase 1 solution does not necessarily pro vide aminimal IISco v er 23
PAGE 29
and 5 yields a feasible subsystem of S W e note that this set is not minimal, sinceremo v alofconstrain ts1and2yields asubsystemsatised b y x 1 =19 : 5 and x 2 =0 : 5. Th us, w ecannot guaran tee that a full elastic LP solution will pro videev enaminimal IISco v er. So w eobtain an IISco v ersimply b ysolving thePhase 1 LP In [12]Chinnec ksuggeststhatsolvingafullelasticprogrammingLPma ynd a smaller cardinalit y co v er. W e ha v e answ ered this question b y demonstrating that b y modifying our Phase 1 problem form ulation to a full elastic programming LP w e still cannot guaran tee a minimal co v er; and in general theco v erfound b yeitherofthesetec hniqueswill notbeof the same cardinalit y as the minim um cardinalit y IIS co v er. This is not surprising,giv enthefollo wing results. In[9],Chakra v artipro v esthatnding the maxim umcardinalit y feasible subsystemof theinfeasible system S is NPhard. Theorem 2.13 (Chakra v arti [9 ]) Theproblemofnding the maxim umcardinalit y feasiblesubsystemoftheinfeasiblesystem S isNPhard. Chakra v arti also demonstrates that there can exist an exponential n um berofIISsinan infeasible systemb yexhibiting asystemha ving 2 n +1 constrain ts, in n v ariables, with 2 n IISs. Theorem 2.14 (Chakra v arti II [9 ]) An infeasible system of constrain ts ma ypossess exponen tially man yIISs. F urtheranalysis ofthecomplexit yoftheproblemispro videdb y Sank aran [34]. 24
PAGE 30
Theorem 2.15 (Sank aran [34]) The problem of nding the maxim umcardinalit y feasiblesubsystemoftheinfeasiblesystem S isNPhard ev enwhen A is totally unimodular and b is in teger. Sank aran pro v es the existence of a class of infeasible systems for whic h the maxim um cardinalit y feasible subsystem can be found in polynomial time. Theorem 2.16 (Sank aran [34]) Iftheaugmen tedmatrix[ A j b ] is totally unimodular, then the constrain ts ha ving articial v ariable nonzero at the completion of Phase 1 comprise a minim um cardinalit y set of functional constrain ts whose remo v al from the infeasible system S = A x b yields a feasible system. Th us,thePhase1LPsolution will yieldamaxim umcardinalit y feasible subsystemfor certainclasses of LPs. Inthespecialcasewhenonlyasinglearticialorelasticv ariable has nonzero v alue at theconclusion ofPhase 1,w enotethefollo wing: Lemma 2.17 If,at the conclusion of Phase 1, only a single articial v ariable isnonzero,thentheconstrain tcorresponding tothatarticial v ariable is a minim umcardinalit y IISco v er. Proof: ByLemma2.12,w eha v ethattheconstrain tcorrespondingtothe nonzero articial v ariable is an IIS co v er. Since thesystemis infeasible, w e ha v e 0 < j minim um IIS co v er j 1, so w e ha v e a minim um cardinalit y IISco v er. Amaldi [1] and Amaldi and Kann [2],[3] also examine thecomplexit y and appro ximabilit y of both nding the maxim um feasible subsystem and nding the minim um set of constrain ts to remo v e to attain 25
PAGE 31
feasibilit y While the t w o problems are equiv alen t in terms of complexit y when solving optimally they dier in complexit y of appro ximation. W e illustrate this with the follo wing example. Suppose w e are giv en an infeasible system ha ving 2000 constrain ts with a MCIC consisting of 20 elemen ts. Ifw endasetof30constrain tswhoseremo v alfromthesystem yields a feasible system,w eha v eappro ximated the maxim umcardinaltiy feasible subsystem to within (2000 30) = 2000 = : 985; ho w ev er, w e ha v e appro ximatedtheminim umsetofconstrain tstoremo v einordertoattain feasibilit y to within (30 20) = 20 = : 5. Th us, as noted b y Amaldi, the second problem is moredicultto appro ximate dueto its scale. In particular, they pro v e the follo wing (ignoring the trivial solution for the homogeneous case). APX denotes the class of problems in NP whic hcanbeappro ximatedinpolynomial timewithinsomeconstan t factor. MAX SNPhard problems are a subclass of the APX class whic h arec haracterizedb ytheirappro ximabilit y MAXSNPhardproblemscan be appro ximated in polynomial timewithin someconstan t, but thereexistssomeconstan t c> 1suc hthatndinganappro ximatesolution within c is NP hard. Th us,theycanbeappro ximatedwithinsomeconstan t,but not all constan ts,in polynomial time. Theorem 2.18 (Amaldi and Kann [2 ]) Theproblemofnding the maxim um feasible subsystem of an infeasible system S ha ving either f = or g relations is MAX SNPhard ev en when restricted to homogeneous systems with in teger coecien ts and no pairs of iden tical relations. 26
PAGE 32
Inotherw ords,themaxim umfeasiblesubsystemcanbeappro ximated within a constan t but not within ev eryconstan t unless P = NP Amaldi and Kann further dene the appro ximabilit y of the maxim um feasible subsystem problem for infeasible systems S ha ving equalit y constrain ts: Theorem 2.19 (Amaldi and Kann [2 ]) Unless P = NP there is a constan t > 0 suc h that the maxim um feasible subsystem of the infeasible system A x = b can not be appro ximated within m ,where m is then um berof ro ws of A Inthecaseofaninfeasiblesystem S ha ving constrain ts,Amandi andKanndemonstratethatitism uc heasiertoappro ximatethemaxim um feasible subsystem. Theorem 2.20 (Amaldi and Kann [2 ]) The maxim um feasible subsystem of the infeasible system A x b can be appro ximated in polynomial timewithin a factorof 2. The proof for this result is constructiv e, and a polynomial time algorithm is pro videdwhic h guaran tees a2appro ximation. If w e restrict ourselv es to iden tifying the MCIC, Amaldi and Kannpresen tthefollo wing. DTIME ( T ( n ))denotestheclassofproblems whic h canbe solv edin time T ( n ),where n is thesizeof theinput. Theorem 2.21 (Amaldi and Kann [3 ]) Theproblemofidentifying the MCIC of the infeasible linear system A x b cannot be appro ximated within an y constan t unless P = NP and within c log n for an y c < 1 = 8 unless NP DTIME ( n loglog n ), ev en when restricted to homogeneous systemswith ternarycoecien tsin f 1 ; 0 ; 1 g 27
PAGE 33
W e kno w that certain cases can either be solv ed optimally in polynomial time,orappro ximatedwithinafactorof2inpolynomialtime. Whatotherboundscanw edetermineforthecardinalit yofthemaxim um feasiblesubsystem? W ebeginb ymakingthefollo wingobserv ationsabout theinfeasible system A x b ; x 0 Ifall b i 0 ; for i =1 ;m ,thenthetrivialsolution x j =0 ; for j = 1 ;n satises the system. Th us, in forming the Phase 1 LP w e need only addarticialv ariablestothosero wsha vinganegativ erigh thandsideand w ecan mak ethefollo wing observ ation. Lemma 2.22 The cardinalit y of the minim um cardinalit y IIS co v erwillbelessthanorequaltothen um berofconstrain tswithnegativ e righ t hand side. Proof: If w e ha v e k negativ e b i 's, then w e need k articial v ariables for the Phase 1 LP A t most, all k articial v ariables will be nonzero at the conclusion of Phase 1. Since remo v al of the constrain ts corresponding to these k articial v ariables yields a feasible subsystem (the 0 solution satises the remaining constrain ts), the minim um cardinalit y IIS co v er will beof cardinalit y equal to orless than k 28
PAGE 34
3. Extensions and Unications of IIS Results In this c hapter, w e will look bey ond the surface theory at the strength behind sev eral results and also explore the relationships among them. 3.1 Examination of V an Loon's Method Sev eral researc hers ha v e examined V an Loon's results (see [13], [19], [26]). A n um ber of shortcomings of the method ha v e been poin ted outthec hiefamongthesebeingthatnonnegativit yconstrain tsm ustbe explicitly included in theform ulation inordertoobtain IISs. Inthissection,w ewillexaminemorecloselytheimplicationsofV anLoon'sresultin aneorttoilluminateamoregeneralbasetheorywhic hcanbeextracted. V anLoon'smethodasdescribedinTheorem2.4andTheorem2.5 requires the explicit inclusion of all nonnegativit y constrain ts as functional constrain ts in the system A x b ; ho w ev er, exclusion of nonnegativit y constrain ts leads totheiden tication ofthoseIISFswhic hare IISs(if an yexist);whic h is only asubset of all IISsof thesystem. F or example, consider the follo wing infeasible system, displa y ed in Figure 3.1: 1 : x 1 + x 2 2 2 : x 1 3 3 : 2 x 1 3 x 2 8 x 1 ;x 2 0
PAGE 35
@ @ @ @ @ (1) 6 (2) Q Q Q Q Q Q Q Q Q Q n n (3) Figure 3.1: Infeasible systemfor exampleofV anLoon's method Ifonlythefunctional constrain tsareincludedinV anLoon'sform ulation (and x 1 and x 2 free),thenw ecanpiv ot both x 1 and x 2 in to the basis yielding thefollo wing tableau: x 1 x 2 s 1 s 2 s 3 RHS x 1 1 0 3 0 1 2 s 2 0 0 3 1 1 5 x 2 0 1 2 0 1 4 0 0 3 1 1 5 Th us, using Theorem 2.5, w e obtain the IIS f 1 ; 2 ; 3 g (the notation meaning that constrain ts 1, 2, and 3 form an IIS).Piv oting to all otherbasescon taining x 1 and x 2 yieldsnootherIISs. ByusingV anLoon's theoremwithoutexplicitlyincludingthenonnegativit yconstrain tsinthe functional constrain ts, w e ha v e iden tied all IISs whic h are IISFs. It is easytodemonstratethatw ewillndallIISswhic hareIISFsinthisw a y; ho w ev er,w ema yha v etovisitallbasesinordertoguaran teedoingso. T o 30
PAGE 36
seewh yw ewill ndall IISswhic hare IISFs,notethat an IISFwhic his anIISof A x b x 0 is still anIISofthemoregeneralsystem A x b x free. Th us, b y Theorem 2.5 w e can iden tify suc h an IIS. Since w e can ndall IISsofthemoregeneral systemb ypiv oting throughits bases,w e can nd the subset of IISs whic h are IISFs of the original system. It is easily seen that w e ha v eother IISs in the systemwhic h rely on thenonnegativit yof x 1 or x 2 ,forexample f 1 ; 3 ;x 1 0 g and f 1 ; 2 ;x 2 0 g Using this restricted tableau, w e cannot iden tify these IISs unless w e modify V anLoon'smethod. W ewilllookatmodifcationsfordoingthislater. F or no w, w e concen trate on determining when w e can iden tify IISs without explicitly including nonnegativit y constrain ts in our model form ulation. Giv en an infeasible system A x b x 0 there exist certain conditions under whic h w e kno w that a source of the infeasibilit y will lie strictlywithinthesetoffunctionalconstrain ts. Inotherw ords,thesystem A x b has no solutions, let alone a nonnegativ e solution. Murt y [28] sho wsingeneralthatanIISiscon tainedwithinthesetofv ariables(problem and slac k) ha ving nonzero reducedcost upon completion of Phase 1. F urther, at the conclusion of a standard Phase 1, if the reduced costs of allproblemv ariables are0andthearticial objectiv eispositiv e,thenthe system A x b is infeasible, and the source of the infeasibilit y is among the constrain ts corresponding to the slac k v ariables ha ving nonzero reduced costs in the nal tableau. Th us, w e kno w that at least one IISF whic h is itself an IISlies among theseconstrain ts (see[28]). 31
PAGE 37
W eagain consider thesimple exampleofFigure 3.1. 1 : x 1 + x 2 2 2 : x 1 3 3 : 2 x 1 3 x 2 8 x 1 ;x 2 0 A ttheconclusion ofthePhase 1 LP ,w eha v ethefollo wing tableau: x 1 x 2 s 1 s 2 s 3 RHS x 1 1 1 1 0 0 2 s 2 0 1 1 1 0 1 s 3 0 1 2 0 1 4 0 0 3 1 1 5 Thereducedcost for problem v ariables x 1 and x 2 is 0, and all 3 slac k v ariables ha v enonzeroreducedcost. Th us,w eha v eanIISFamong the constrain ts f 1 ; 2 ; 3 g in fact, in this case the set corresponds exactly to an IISF. Otherwise, if the reduced cost of at least 1 v ariable is nonzero, then Ax b c ould ha v easolution, butnotanonnegativ e solution. Consider thefollo wing modication oftheprevious example: 1 : x 1 + x 2 2 2 : x 1 3 x 1 ;x 2 0 W e note that x 1 =3 and x 2 = 1 is a solution to the system dened b y (1) and (2) (th us a solution exists, but no nonnegativ e solution exists). 32
PAGE 38
This systemhas thefollo wing nal Phase 1tableau: x 1 x 2 s 1 s 2 RHS x 1 1 1 1 0 2 s 2 0 1 1 1 1 0 1 1 1 1 F romMurt y[28],w eseethatanIISexistsamongtheconstrain ts f 1 ; 2 ;x 2 0 g againinthiscase,thesetgiv esusanIIS,although itwill notingeneral. Lookingbey ondwhatV anLoonexplicitlystatesinhispaper,w e seeho wtousehisideasinamoregeneralsetting. Supposew earew orking withtheinfeasiblesystem A x b ; x 0 ,andw ec hoose not toexplicitly includenonnegativit y constrain tsasfunctional constrain ts. Again,letus use theexampleofFigure 3.1: 1 : x 1 + x 2 2 2 : x 1 3 3 : 2 x 1 3 x 2 8 x 1 ;x 2 0 A t the conclusion of the Phase 1 LP w e ha v e the tableau depicted in Figure 3.2. This is an optimal basis in the sense that all reduced costs are nonnegativ e. Notethat w eare unable to piv ot x 2 in to thebasis without piv oting x 1 out of the basis. Since w e ha v e a 1 in the ( s 2 ;x 2 ) position of the tableau, w e cannot use Theorem 2.5 to nd an IIS in that ro w. W e cannot iden tify an IIS in ro w s 3 because of the 1 in column x 2 W e 33
PAGE 39
x 1 x 2 s 1 s 2 s 3 RHS x 1 1 1 1 0 0 2 s 2 0 1 1 1 0 1 s 3 0 1 2 0 1 4 0 0 3 1 1 5 Figure 3.2. Final T ableau, Not Including Nonnegativit y in F unctional Constrain ts no w compare this basis with that obtained from the follo wing equiv alen t system: 1 : x 1 + x 2 2 2 : x 1 3 3 : 2 x 1 3 x 2 8 4 : x 1 0 5 : x 2 0 x 1 ;x 2 free x 1 x 2 s 1 s 2 s 3 s 4 s 5 RHS x 1 1 1 1 0 0 0 0 2 s 2 0 1 1 1 0 0 0 1 s 3 0 1 2 0 1 0 0 4 s 4 0 1 1 0 0 1 0 2 s 5 0 1 0 0 0 0 1 0 0 0 3 1 1 0 0 5 F romtheallslac kinitialbasis,w eha v epiv otedin x 1 andpiv oted out s 1 thesamepiv otperformedtoobtainthetableau ofFigure3.2. As opposedtothetableauofFigure3.2,w eareabletopiv ot x 2 in tothebasis without piv oting out x 1 The additional slac k v ariable on the constrain t x 1 0, s 4 can be piv oted out of the basis. Our goal is to ha v e a basis 34
PAGE 40
similar to that in Figure 3.2, so w e wish for x 2 to be basic with activit y lev el 0. W e force this to occur b y piv oting in s 4 and piv oting out s 5 ; x 2 and s 5 m ust ha v ethesameactivit ylev el,soifoneisnotinthebasis, the other m ustbe0 also. x 1 x 2 s 1 s 2 s 3 s 4 s 5 RHS x 1 1 0 1 0 0 0 1 2 s 2 0 0 1 1 0 0 1 1 s 3 0 0 2 0 1 0 1 4 x 2 0 1 0 0 0 0 1 0 s 4 0 0 1 0 0 1 1 2 0 0 3 1 1 0 0 5 Figure 3.3. Final T ableau, Including Nonnegativit y in F unctional Constrain ts F rom ro w s 2 of the tableau of Figure 3.3, w e obtain the IIS f s 1 ;s 2 ;s 5 g Looking bac k at ro w s 2 of the tableau in Figure 3.2, w e see thatitisiden tical,sa v ethatw eha v ea1inthe x 2 columnratherthana1 in the s 5 column (this column does not exist without explicitly including nonnegativit y constrain ts in the form ulation). The k ey is to recognize that x 2 s 5 = 0 x 2 = s 5 and th us it is irrelev an t whether or not w e include x 2 0 explicitly in the problem form ulation. W e ha v e the follo wing generalization of Theorem2.5: Theorem 3.1 (Extension of V an Loon's Theorem) Giv en theinfeasible system S = f A x b ; x 0 g ,suppose thereexistsa Phase 1 tableau thatsatises thefollo wing: (1) aslac kv ariable, s i ,whic hisnegativ e,andbasicinro w i ofthecurren t tableau (2) positiv ev alueinthecolumn(orcolumns)ofone(sev eral) x j inro w i (3) all x j ha v e0 reducedcost 35
PAGE 41
(4) all otherslac kv ariables ha v enonnegativ e tableau en triesin ro w i Then, the v ariables ha ving positiv e tableau en tries in ro w i index an IIS of S Proof: W enotethatifinthetableauro w i describedabo v ethere arenoproblemv ariablesha vingnonzeroen tries,thentheh ypothesisholds trivially b y Theorem 2.5. Otherwise, without loss of generalit y assume that some problem v ariable, sa y x 1 has a positiv e tableau en tryin ro w i Sinceslac k v ariable s i is basic inro w i and x 1 has anonzero en tryinro w i ,w ekno wthat x 1 isnon basicandso x 1 =0andfurtherthereducedcost for x 1 isalso0. No wconsiderthesystemwherew eincludetheconstrain ts x j + s x j = 0 in the form ulation. Here s x j represen ts the slac k v ariable onthenonnegativit yof x j (so x j = s x j ). W ecanaddtheseconstrain tsto thecurren ttableau,makingeac hnewlyaddedslac kv ariable s x j basic. W e denotethero waddedforthenonnegativit yof x j asro w m + j Sinceeac h x j isnonnegativ einthecurren ttableau,themodiedsystemwillstill be \feasible"(inthesensethatonlyslac kv ariablesha v enegativ ev alue). The onlymodication toro w i duringthisprocessistheaddition ofa0inthe columnforeac hnewslac kv ariable s x j W ewishtopiv ot x 1 in tothebasis, butlea v eitsv alueat0. Th us,w ecanpiv ot x 1 in tothebasis,andpiv ot s x j out ofthe basis. Ifw eview thetableau columns for x 1 (prior to piv oting it in to the basis) and s x 1 (after piv oting it out of the basis) as being the rate at whic h the basic v ariables c hange per unit c hange in the v alue of x 1 (resp. s x 1 ),thensince x 1 = s x 1 ,w em ustha v ethatthetableaucolumn of non basic v ariable x 1 prior to piv oting it in to the basis is iden tical to thetableaucolumnofnon basicv ariable s x 1 uponcompletionofthepiv ot. 36
PAGE 42
In particular, w e note that upon piv oting x 1 in to the basis, there will be a 0 in the x 1 column of ro w i and a nonzero v alue in the s x 1 column of ro w i W em ustonly demonstratethat w eha v emodied no otheren tries in ro w i of the tableau b y this piv ot. Ro w m +1 will ha v e a 0 in ev ery column excludingcolumn s x 1 ,whic hhas a1,andcolumn x 1 ,whic hhas a 1. Becauseof this, when piv oting x 1 in to the basis and piv oting s x 1 out of the basis, w e do not aect an y columns of ro w i excepting column x 1 andthepreviouslydiscussedcolumn s x 1 W ecanrepeatthisargumen tfor an y suc hv ariable x j ha ving a positiv e tableau en tryin ro w i 3.2 V an Loon's Method and the Gleeson and Ry an Method Let us look closer at the method of Gleeson and Ry an [19]. W e notethatthepolyhedron P ofTheorem2.6isaboundedformofthecone of the alternativ e system (2) from Theorem 2.1. The follo wing form of Theorem2.6 is also implied in [19]: Theorem 3.2 (Conical v ersion of GleesonRy an Theorem) Let A x b denote an inconsisten t set of inequalities. Then the IISsare in 11 correspondencewith theextremera ysof thecone P 0 = f y 2< m j y T A =0 ; y T b < 0 ; y 0 g : In particular, thenonzero componen ts of an y extremera yof P 0 index an IIS. Th us,intheconicalv ersionoftheGleesonRy anMethod,w eare looking forthesupports ofextremera ysofthealternativ esystemdened b y F ark as' Theorem. The alternativ e system is simply the dual of our original (primal) system with the primal objectiv e function zeroed out. 37
PAGE 43
Th us,b yignoringtheobjectiv efunction,thePhase1solution of S canbe used to iden tifyan extremera yof theun bounded dual system,or an IIS oftheoriginal system. Inotherw ords,w ecaniden tifyone(ormore)IISs withnomorew orkthansolvingPhase1ofouroriginalsystem. Inessence, this generalizes theresult of V an Loon [36]. Assumethat w earew orking with an infeasible system A x b where an y non{negativit y constrain ts are considered for this discussion to be included. Equiv alen tly w e ha v e the infeasible system A x + s = b where s is a v ector of slac k v ariables. Consider thefollo wing LP: max c T x subjectto A x + s = b s 0 Suppose that at the termination of Phase 1 for the infeasible system w e ha v eabasicslac kv ariable,sa y s 1 ,whic hisstrictlylessthan0. Additionally ,ifthePhase1tableauen triesforallnon basicv ariables x j are0andfor all non basic slac k v ariables s i are non{negativ e in the ro w corresponding to s 1 ,thenin Theorem2.5 V anLoon pro v esthat thebasic slac k v ariable s 1 andallslac kv ariablesha vingnegativ erateofsubstitutionwithrespect to s 1 forman IIS. No w,fromTheorem3.2,w eha v ethatthissamesetofconstrain ts whic h forms an IIS of P m ust be the supports of an extreme ra y of the alternativ econe P 0 Inotherw ords,V anLoon'salgorithm,withoutexplicitly iden tifying it assuc h,ndsextremera ysofthealternativ esystemb y piv otingthroughbasesoftheoriginalinfeasiblesystemlookingfortableau 38
PAGE 44
ro ws satisfying theabo v e. This relationship should not be surprising, giv en the form of a solution ro w in V an Loon's method. W e ha v e a ro w with the follo wing form: [ ++ ::: +00 ::: 0 j ] : Since all reduced costs are 0 or positiv e, there exist no piv ot whic h will c hange thesign oftheRHSif w eincreasean ynon basic v ariable from0, w e decrease the v alue of the RHS in this ro w. If w e think in terms of a dualpiv ot,ifw etrytopiv otthisro woutofthebasis,thereisnoen tering v ariable w ecanincrease un bloc k edandso w eha v eanextremera y 39
PAGE 45
4. F acial Structure of the IIS Co v er P olyhedron Inthis c hapter,w ederiv esomefacetsfortheIISco v eringproblem. W ewillbeginb yin troducingsomepreliminaryconceptsandprevious results. 4.1 Dimension of the Min W eigh t IIS Co v ering P olytope A few preliminaries will be presen ted rst. W e sa y that the cardinalit y ofanIISisthen um berofconstrain ts andbounds con tained intheIIS.Insomeinstances,w ewillwishtospeakofthe ro wcardinalit y of an IIS. This refers to the n um ber of functional constrain ts con tained in the IIS. F or the remainder of this c hapter, w e assume, without loss of generalit y that the infeasible system A x b has no ro w i of A with a ij = 0 forall j and b i < 0. If suc h a ro w exists, it can be preprocessed out of the system and dealt with separately W e immediately mak e the follo wing observ ation whic h pro vides a lo w er bound on thesize of an IIS from asystemcon taining no trivial inequalities. Observ ation 4.1 Giv enaninfeasiblesystem A x b ,ev eryIIS of this systemwill beof cardinalit y 2. Recall that an inequalit y A i x b i is an implicit equalit y in the system A x b if A i x = b i for all x satisfying A x b W e can th us partition theconstrain ts of A x b in to thefollo wing: (1) A = x b = is thesystemof implicit equalities in A x b (2) A < x b < is thesystemof all other inequalities in A x b
PAGE 46
W e also mak e use of the follo wing w ellkno wn theorem (see[35] for example): Theorem 4.2 ([35]) The dimension of the nonempt y polyhedron Q = f x 2< n j A x b g is equalto n r ank ( A = ). Using these results, as w ell as the fact that eac h IIS has cardinalit y at least 2, w e can deriv e the dimensionalit y of the IIS co v ering polytope. Theorem 4.3 Giv en an infeasible system S and the polytope C = f z 2 B n j D z 1 g constructed suc h that eac h ro w i of D is the support v ectorof an IISof S ,then thedimension of C ( dim ( C ))is n Proof: Since a v alid solution can be an o v erco v ering, w e can set all z i 's to be 1. F rom Observ ation 4.1, w e ha v e that ev ery IIS has at least 2 elemen ts,whic himplies that eac hro w i of D has at least 2 nonzero d ij 's. Thisimpliesthatnoconstrain tinourproblemisimplicitforallsolutions, and so therank of D = is 0. Th us thedimension of C is n Amatrix A iscalleda clutter ifthesupport ofev eryro wisnot properly con tained in the support ofan y other ro w. Since thesupport of eac hro wofthe0 1 coecien tmatrixoftheMWICproblem consists of theindices ofanIISof S ,andsinceeac hIISisminimalb ydenition, w e ha v ethat thecoecien tmatrix oftheMWICproblem is a clutter. W eno wexaminekno wn results on facetsofgeneral setco v ering polytopes. 41
PAGE 47
4.2 Kno wn Properties of the General Set Co v ering P olytope Withinthissection,w ewilldiscussthegeneralsetco v eringpolytope denedas: GSCP ( D )=con v f x 2 B n j D x 1 g Among the basic facts kno wn about the polyhedron GSCP ( D ) are thefollo wing theorems(see[4]for example). Theorem 4.4 (GSCP Dimensionalit y [4]) Thepolyhedron GSCP ( D )isfulldimensional ifandonlyif D isaclutterandeac hro wof D has 2or morenonzerov alues. Asw eha v eseenfromTheorem4.3,theMWICpolyhedronmeets the conditions for full dimensionalit y The remaining results in this sectiondependuponthedimensionalit y ofthegeneralsetco v eringpolytope. Th us, for the remainder of this section, w e shall assume that the polyhedron GSCP ( D ) is full dimensional. In general, this need not be true, ho w ev er;if aro w of D has only a single nonzeroelemen tor if aro w of D isproperlycon tainedinanotherro wof D ,w ecanpreprocesstheco v ering problem to yield a subproblem whic h is full dimensional. In particular, theIISco v eringproblem is full dimensional. Theorem 4.5 ([4]) All inequalities of the form x j 1 dene facets ofthepolyhedron GSCP ( D ) Th us, the v ariable upper bounds for the MWIC polyhedron are facetdening. Theorem 4.6 ([4]) Theinequalit y x j 0denesafacetofthe polyhedron GSCP ( D ) if and only if the n um ber of nonzero elemen ts in ro w i not including the j th elemen tis atleast 2 forall ro ws i of D 42
PAGE 48
Balas and Ng [4] pro vide necessary and sucien t conditions for a standard co v ering constrain t to be a facet dening inequalit y of the general set co v ering polytope. W e use the follo wing notation. N i is the set ofnonzero coecien tsinro w i of D and M is thero windexset. Theorem 4.7 (BalasNg [4]) Theinequalit y P ( x j j j 2 N i ) 1denesa facetof GSCP ( D ) ifand only if (1) thereexists no k 2 M with N k N i ;and (2) for eac h k 2 N n N i there exists j ( k ) 2 N i suc h that d hj ( k ) =1 for all h 2 M 0 ( k ),where M 0 ( k )= f h 2 M j d hk =1and d hj =0,forall j 2 N n N i S f k gg Theypro v ethataco v eringinequalit y i isafacetofthegeneralsetco v ering polytope ifandonlyifitisnotproperlycon tainedinanotherro wandfor ev ery0 elemen t k in ro w i thereexists a column j ( k ) ha ving a 1 in ro w i anda1inev eryro wthathasa1incolumn k anda0inallothercolumns that ro w i has a0 in. W eexamine the implications of this result on a general set co vering instance. Belo w, w e ha v e the coecien t matrix D of a general set co v eringproblem: x 1 x 2 x 3 x 4 x 5 x 6 (1) 1 1 0 0 1 1 (2) 0 1 1 0 0 1 (3) 0 1 1 0 1 0 (4) 1 0 1 1 1 1 W eobserv ethatro w(1)ofthisproblemisafacet. W erstnote thatro w(1)isnotproperlycon tainedinan yotherro wof D ,andth usro w 43
PAGE 49
(1) satises condition (1)ofTheorem4.7. W econsiderall columns where ro w (1) has 0's to sho w that condition (2) is satised. First, w e consider column x 3 Ro ws (2) and (3) ha v e a 1 in column x 3 and 0's in all other columnswherero w(1)hasa0(column x 4 istheonlyothercolumnro w(1) has a 0). These t w o ro ws dene the set M 0 ( x 3 ). W e ha v ethat ro ws (1), (2), and (3) all ha v ea 1 in column x 2 th us j ( x 3 )= x 2 and condition (2) is satised for column x 3 This condition is satised trivially for column x 4 since thereare no ro ws ha ving a 1 in column x 4 and a zero in column x 3 (so M 0 ( x 4 ) is empt y). Th us, ro w (1) forms a facetdening constrain t of the general set co v ering problem D x 1 Similarly w e see that ro ws (2) and(3) arealso facetdening;ho w ev er,ro w(4)is not. Condition (1) ofTheorem4.7holdsforthisro w,butcondition (2)fails. Theset M 0 ( x 2 ) con tains ro ws (1), (2), and (3). Ho w ev er,w eare unable to nd a column j ( x 2 )ha ving 1's in all four ro ws andso condition (2) fails. 4.3 Properties of the Min W eigh t IIS Co v ering P olytope W e can in terpret the meaning of Theorem 4.7 within the context of our infeasible system. Let the original infeasible system of linear inequalities be denoted b y S Let P be the polyhedron dened b y the feasible alternativ e systemgiv en in Theorem2.6, P = f y 2< m j y T A =0 ; y T b = 1 ; y 0 g and let C denote theMWICpolyhedron C = f z 2 B m j X i 2 I j z i 1 forall j g ; where I j = j th IIS. 44
PAGE 50
Notethat w e ha v ethe follo wing correspondence bet w een C and P : co v ering constrain ts of C correspond to the supports of the extreme poin ts of P ,andv ariables of C correspond to facesof P W ewill begin b ypro ving thefollo wing general lemma. Lemma 4.8 The support of an extremepoin t p of an y polyhedron A x b x 0 consists of those faces ofthe polyhedron on whic h p does not lie. Proof: Thesupport ofan extremepoin t p is thesetofnonzerov ariables inanoptimalbasisfor p If x i 6 =0,thentheconstrain t x i 0isnottigh t; and so p does not lie on the face x i = 0. Similarly if x i = 0, then the constrain t x i 0 is tigh t; and so p lies on the face x i = 0. An iden tical argumen t forslac k v ariables concludes theproof. Thefollo wing corollaryisatranslation ofTheorem4.7using the relationship bet w een C and P denedabo v e. Corollary 4.9 Thesupportofanextremepoin t p of P isafacet deninginequalit yof C ifandonlyifforev eryface k of P ha vingextreme poin t p onitandha vingnonempt ysetofextremepoin ts L k of P whic hare notonface k butonallotherfacesthatextremepoin t p ison,thereexists another face j ( k ) of P not con taining extreme poin t p or an y extreme poin t in L k Proof: The support of an extreme poin t p of P forms a co v ering constrain t P x j 1, for j 2 N p in C Since the co v ering constrain ts of C form a clutter, w e satisfy condition (1) of Theorem 4.7. W e note that the statemen t of this corollary is a direct translation of condition (2) of Theorem4.7 in ligh t of Lemma4.8. This completestheproof. 45
PAGE 51
Letusno wexaminethefacialstructureoftheMWICpolyhedron. F rom Theorem4.5 and thefull dimensionalit y of theMWICpolyhedron, w e ha v e that constrain ts of the form z i 1 are facet dening for the MWICpolyhedron. Theorem4.6statesnecessaryandsucien tconditions for constrain ts of theform z i 0 tobefacetdening. W eseethat in the follo wing instances, nonnegativit y constrain ts are facets of the MWIC polyhedron. Corollary 4.10 Ifthereexistsaconstrain t j of S whic hiscontained in no IIS,then z j 0is a facetdening constrain t of C Proof: If constrain t j of S is con tained in no IIS, then there are no co v ering constrain ts of C ha ving coecien t 1 for v ariable z j Since there areatleast2nonzerocoecien tsineac hco v eringconstrain tof C ,neither of whic h is the coecien tof z j w e satisfy the conditions of Theorem 4.6 and theconclusion holds. Of couse, w e note that if a suc h a constrain t j of S exists, then w e candelete v ariable z j from theco v ering problem C Anonnegativit y constrain t will bea facetifone oft w o conditions aremet: Corollary 4.11 A nonnegativit y constrain t z j 0 is a facet dening constrain t of C if and only if oneof thefollo wing holds: (1) Constrain t j of S appears in no IISsof S (2) Ev ery IIS of S con taining constrain t j of S is of cardinalit y 3 or greater. Proof: T opro v ethe\onlyif"direction,w enotefromTheorem4.6thatin orderforthenonnegativit yconstrain t z j 0tobefacetdening,remo v al of the j th column of the coecien t matrix of C m ust yield a system still 46
PAGE 52
ha ving at least t w ononzero coecien tsin eac hro w. Assume that z j 0 is a facet dening constrain t of C No w either constrain t j of S appears in an IISof S or it doesn't. Case 1 Assumeconstrain t j of S appearsinatleastoneIISof S Bythe argumen t abo v e, eac hIIS that constrain t j appears in m ust ha v eat least 3 elemen ts,since upon remo v al of j w e m ust still ha v eat least 2. Th uscondition (2) holds. Case 2 Assumeconstrain t j of S appearsinnoIISsof S Thencondition (1) holds. T opro v ethe\if" direction,w elook at thet w oconditions specied intheh ypothesis. Case 1 Assume constrain t j of S appears in no IISs of S Then b y Corollary 4.10,thenonnegativit y constrain t z j 0is facetinducing in C Case 2 Assume constrain t j of S appears in at least one IIS of S and that the cardinalit y of ev ery IIS j appears in is at least 3. Then upon remo v al of v ariable j from C ev ery ro w of C will con tain at least2nonzerocoecien ts. Th usb yTheorem4.6thenonnegativit y constrain t z j 0is facetinducing in C W e ha v e all nonnegativit y constrain ts as facet dening for the MWICpolyhedron underthefollo wing special condition: Corollary 4.12 All nonnegativit y constrain ts z 0 are facet deningfortheMWICpolyhedronifandonlyifeac hIISisofcardinalit y 3 or larger. 47
PAGE 53
Proof: This is an immediateextension ofCorollary 4.11. W eno wexaminea special instance oftheMWICproblem. Corollary 4.13 If the cardinalit y of the minim um w eigh t IIS co v er is 1, then all co v ering constrain ts are facet dening for the polyhedron C Proof: Since the cardinalit y of the MWIC is 1, there exists a column j of the MWIC coecien t matrix whic h is 1 This implies that w e ha v e a face j of P whic h has no extremepoin ts of P onit. ByCorollary 4.9 the conclusion holds. Whatmorecanbesaidabouttheco v eringconstrain tsbeingfacet deningfortheMWICpolyhdron? First,letuslookattheset L k (dened in Corollary 4.9) more closely Giv en an extreme poin t p of P whic h is con tained on face k L k consists of those extreme poin ts of P whic h are notonface k ,butareonallotherfacesthatextremepoin t p of P ison. In otherw ords, L k consistsofthoseextremepoin tsof P whic hcanbevisited from extremepoin t p when w e mo v eo of face k W erst note that the nonzeroelemen tsofthesupportofextremepoin t p will correspondtothe subset of basic v ariables whic h are nonzero in all bases of extremepoin t p In the case where p is nondegenerate, there will be only a single basis and the nonzero elemen ts of the support of p will correspond exactly to the basic v ariables. W e wish to c haracterize the extreme poin ts in L k ; in particular, w e will do this b y determining if the extreme poin ts in L k areadjacen tto p Intermsofthesimplex algorithm, this is equiv alen tto determiningifeac hextremepoin tin L k isonepiv ota w a yfromsomebasis of p This is straigh tforw ard for p not degenerate since there is only a 48
PAGE 54
singlefeasiblebasiscorresponding to p Inthecasewhere p isdegenerate, w e ha v e man y bases corresponding to the same extreme poin t. In this case, w e view adjacency as meaning that there exists a single piv ot from a basis of p whic h will tak eusto theparticular extremepoin t of L k Lemma 4.14 Eac h extremepoin t L j k of the set L k for extreme poin t p is adjacen tto p Proof: W ewill demonstratetheexistenceof afaceof dimension 1whic h con tains both extreme poin ts p and L j k th us implying the adjacency of theextremepoin ts. Letthedimensionofthealternativ epolyhedron P be d Sinceanextremepoin tis afaceofdimension 0,w ekno wthatextreme poin t p is determined b y the in tersection of at least d faces, sa y e d faces. W e can pic ka subset of size d of these e in tersecting faces,alw a ys including face k whic h is sucien t to dene p No w L j k shares exactly d 1 of the in tersecting faces in this subset, since it does not lie on face k Th us there exists a face of dimension d ( d 1)=1 con taining both p and L j k This implies that p and L j k areadjacen t. Giv en this result, ho w large can the set L k be? By noting the uniquenessoftheextremepoin t w emo v etoinasimplexpiv ot,w eobtain thefollo wing result. Lemma 4.15 Thecardinalit y of theset L k for extremepoin t p of P is atmost 1. Proof: F rom Lemma 4.14, w e ha v e that the extreme poin ts of L k are a subset of those adjacen t to extreme poin t p By the simplex algorithm, when w e piv ot in a specic non basic v ariable, sa y the k th at a nonzero v aluethereisauniqueextremepoin twhic hw epiv otto. Th us,theset L k 49
PAGE 55
can ha v eat mosta single elemen t. No w,w ecanpro v ethefollo wingresultontheco v eringconstrain ts of theMWICpolyhedron. Theorem 4.16 (Co v ering Constrain t F acet Theorem) All co v eringconstrain ts of theMWICpolyhedron C arefacetdening. Proof: Choose an arbitrary extremepoin t p of P Look at all facesof P thatextremepoin t p ison. ByLemma4.14,ifw ewishtopiv otoofface k thenw e can visit those elemen tsof L k in 1 piv ot. ByLemma 4.15, L k has at most 1 elemen t. If L k is empt y the h ypothesis holds trivially via Corollary 4.9. Otherwise, L k is not empt y Extremepoin t p is denedb y the in tersection of e faces (note e is not necessarily the dimension of P ). Theextremepoin tin L k ,callit L 1 k ,isdenedb ythein tersectionof f e faces, of whic h e 1 also help dene p W e note that their denitions will dier in at least 2 faces. L 1 k is not on face k and m ust be on a face that p isnot(otherwise,thesupportof p isapropersubsetofthesupport of L 1 k whic h is not possible). Since eac h IIS of S m ust ha v e at least 2 constrain ts, eac hextremepoin t of P m ustha v e2 nonzero v ariables in its support. Since L 1 k is on f faces, there m ust be at least f +2 faces in P No w L 1 k is on f faces, p is on e faces, and they share e 1 faces, so w e ha v e f + e ( e 1)faceswhic hcon taineither L 1 k or p orboth. Thislea v es at least f +2 ( f + e ( e 1))=2 1=1 facewhic h denesneither p nor L 1 k Th us thereexists a faceof P con taining neither p nor L 1 k ;and, b yCorollary 4.9w eha v etheh ypothesis. Th us, all co v ering constrain ts of the MWIC problem are facet dening. If all facets of the MWIC problem are of this form, then the 50
PAGE 56
in tegerh ulloftheMWICpolyhedronw ouldbecompletelydescribed,and the solution to the linear programming relaxation w ould giv e us the optimal co v er. As the follo wing example(from [32])demonstrates, w e ha v e not denedall facetsof this problem. 1 : x 1 2 2 : x 1 + x 2 10 3 : 2 x 1 3 x 2 49 4 : 2 x 1 3 x 2 21 5 : x 1 + x 2 6 x 1 ;x 2 free ? (1) @ R (2) Q Q Q Q Q Q Q Q Q Q Q n n (3) J J ] (4) @ @ @ @ @ @ (5) TheIISsofthissystemare: f 2 ; 4 ; 5 g f 1 ; 3 ; 4 g f 2 ; 3 ; 5 g f 1 ; 2 ; 4 g and f 1 ; 3 ; 5 g Th us, the MWIC has cardinalit y 2; there are sev eral optimal solutions including f 3 ; 4 g Ho w ev er, the optimal solution to the LP relaxationoftheMWICproblemistoleteac hv ariabletak ethev alue1 = 3, and th us theLP relaxation solution is 5 = 3. Thissolution canbecutousingthefamilyoffacetsderiv edb y BalasandNgin[4]. Inthispaper,allfacetswithcoecien tsin f 0 ; 1 ; 2 g are iden tiedforthegeneralsetco v eringproblem. W eha v eexploredthefacial structureoftheMWICpolyhedron furtherbutfoundnosimplication of 51
PAGE 57
thenecessaryandsucien tconditions fortheseconstrain tstobefacetsin theMWICproblem. 4.4 Generalizations Inthis section w e presen tan abstraction of the theorems in the previoussectionstoanewfamilyofco v eringproblems,called P olyhedral Co v ering Problems W e rst recognize that the MWIC problem is exactly one of iden tifying theminim umw eigh tsetof facesof P whic hco v erall extreme poin ts of the polyhedron P (or the minim um w eigh t set of faces whic h in tersect outside of P see [32]). The special structure of the MWIC problem is a direct consequence of the polyhedral nature of the co v ering problem. Inourcase,thesupports oftheextremepoin ts of P correspond to IISsof S Ho w ev er,theonly conditions w eusedin pro ving theresults ofChapter4w eretheminimalit yofeac hIIS(th usha vingaclutter),that eac hIIShas atleast 2elemen ts,and theextremepoin t relationship. Supposew earegiv enthemoregeneralproblemofiden tifyingthe minim um w eigh t extremepoin t co v er of the polyhedron GP w e denote this as the MWEPC problem. Let EP be the arra y whose ro ws are the support v ectors of the extreme poin ts of GP so EP v 1 forms the co v eringconstrain ts ofMWEPC.Bytheminimalit y ofan extremepoin t, w eha v ethatthero ws of EP forma clutter. W earenotguaran teedthateac hextremepoin tof GP willha v eat least2nonzeroelemen tsinitssupport. Considerthefollo wingpolyhedron: 52
PAGE 58
r r r r H H H H H @ @ @ @ @ ep 2 ep 3 ep 4 ep 1 a b c (bac k) d Since ep 1 is dened b y the in tersection of faces a b and c the support of extreme poin t ep 1 is f 0001 g W e will call suc h polyhedra \p yradmidal." If GP is un bounded, then w e can ha v e extreme poin ts whose supports ha v enononzero elemen ts. Consider thetrivial case 1 : x 1 0 2 : x 2 0 x 1 ;x 2 free Thissystemhasonlyasingleextremepoin t x 1 =0 ;x 2 =0,whosesupport v ectoris f 00 g If w e wish to co v er the extreme poin ts of a polyhedron, these 2 cases can be trivially preprocessed out of the co v ering problem. If the supportofanextremepoin thasasingleelemen tnonzero,sa ythe j th ,then w esimplyremo v ethisro wandallotherro wsha vinga1incolumn j from EP and set the j th co v ering v ariable to 1. Ifw eha v ean yextremepoin ts ha ving nononzeroelemen tsintheirsupports,thenthereisnosolution to theco v eringproblem (thereexistsno facesin tersecting outside of P ). 53
PAGE 59
Withthist ypeofpreprocessing,allpropertiesoftheMWICproblem generalize to the MWEPC problem. In particular, all co v ering constrain ts of the MWEPC problem will be facet dening (this is analagous to Theorem4.16). 54
PAGE 60
5. Algorithm Description and Computational Results 5.1 In troduction Inthisc hapterw edev elopanalgorithmforobtainingtheMWIC based upon theIISiden tication method ofGleeson and Ry andiscussed previously Ifw eknewwhattheIISsofasystem S w ere,w ecouldform ulate thefollo wing setco v eringproblem, where w i is thew eigh ton the i th constrain t. min P m i =1 w i z i subjectto P i 2 J z i 1 for all IISs J: z i binary Unfortunately as previously discussed, then um berof IISs ma ybe exponen tial in the size of the original problem, so w e do not w an t to write do wn the whole problem at once. Instead, w e will generate constrain ts dynamically for theproblemand solv e ititerativ ely as outlined belo w: (1) Iden tifyaninitial setof IISs K ( K ma ybe empt y .) (2) Solv e theco v eringproblem min P m i =1 w i z i subjectto P i 2 J z i 1 for all IISs J 2 K: z i binary Let T index theelemen tsin theoptimal co v er.
PAGE 61
(3) Look foranIISof S notco v eredb y T Ifthereisnone,STOP T is an optimal co v erof all IISs. Otherwise,add the newIISto K and go to 2. T oiden tifyIISs,w ewillmak euseofTheorem2.6duetoGleeson and Ry an [19]. W e examine the utilit y of this theorem in terms of our algorithm presen tedabo v e. Let T denote the index set of a subset of the v ariables dening P Then T willalsodenoteasubsystemofthesystem S Let y T =0mean thatall thev ariables in T ha v ebeensetto0. Ifw esearc hforanextreme poin t of P with y T = 0, there are t w o possibilities. The rst is that w e nd an extremepoin t whose nonzero componen ts index an IISthat does not in tersect T The second is that there is no suc h extremepoin t of P Inthis case,thesystem f S n T g is feasible. W ecanno w modify step3of our algorithm (outlined abo v e): (1) Iden tifyaninitial setof IISs K ( K ma ybe empt y .) (2) Solv e theco v eringproblem min P m i =1 w i z i subjectto P i 2 J z i 1 for all IISs J 2 K: z i binary Let T index theelemen tsin theoptimal co v er. (3) Look for an extremepoin t of P ha ving y T = 0. If there is none, STOP T is an optimal co v erof all IISs. Otherwise, add the IIS corresponding to this extremepoin t to K and go to 2. 56
PAGE 62
This implemen tation is generalized in Section 5.3 to operate on aninfeasiblelinearprogrammingproblemgiv eninamoregeneralformat. Later sections discuss enhancemen ts including the selection of the initial K in Step 1, and the c hoice of extremepoin t in Step 3. W e also discuss the ecacy of using a heuristic to solv e the co v ering problem in Step 2 whenpossible. No w,w edemonstratetheutilit yoftheIISco v erisolation. 5.2 Min IIS Co v er Isolation in Practice Finding a minim um w eigh t IIS co v er will tak e more time than iden tifyingasingleIISandattemptinginfeasibilit ydiagnosis. Istheextra information obtained w orth the extra time expense? W e address this b y looking atsev eralexamples,andmakingan um berofsimpleobserv ations. Observ ethatifthereexistsaconstrain twhic hiscon tainedin ev ery IIS,it isaminim umIISco v er. So,inthe best case,infeasibilit y canbeisolated to a single constrain t. This is illustrated b y the follo wing example from [36]: Consider theinfeasible system,whic his depictedin Figure 5.1: 1 : x 1 x 2 0 2 : 2 x 2 1 3 : x 1 x 2 2 4 : x 2 2 5 : 2 x 1 x 2 4 An IIS of this systemis f 1,2,3 g Based upon this information alone, out of thecon textoftheen tiresystem,amodeler w ould ha v ea diculttime determining the source of the infeasibilit y The unique min IIS co v er is f 2 g whic h indicates that ev eryIIS in the system con tains the second 57
PAGE 63
@ I (1) ? (2) 6 @ @ @ @ @ @ @ @ @ @ (3) 6 (4) A A A A A A A A A A A A A A A A A A A A (5) Figure 5.1: Infeasible systemfromV an Loon 58
PAGE 64
constrain t. Itiseasilydemonstrated,ho w ev er,thatthemodelingerrorisnot alw a ysisolatedb yaparticularminim umIISco v er. An yinfeasiblesystem ha ving onlyasingle IISwill ha v eaminim umIISco v erconsisting of an y elemen t of the IIS. By w eigh ting the objectiv e function of the co v ering problem, alternativ e minima can be iden tied to aid in isolation. This can be done b y setting the objectiv e function coecien ts for v ariables con tained in the original co v erto a suitably large in teger, sa y n whic h is the n um ber of v ariables in the co v ering problem. W e then resolv e the co v ering subproblem one time with thecurren tIIS set. Insummary the minim umIISco v er itself willnotalw a yspro videaperfectisolationtothe modeling error;ho w ev er,theisolation information inusing thistec hnique tondtheminim umIISco v erisalw a ysatleastasusefulasthatobtained from a single IIS. Using our algorithm to nd the min IIS co v er alw a ys iden ties at least one IIS. This com bination of min IIS co v er and IISs is a v ailable to the user in her debugging analysis. Additionally the IIS co v erwill alw a ys giv e themodeler the means of eliminating infeasibilit y from the model. A single IIS does not pro vide this lev el of isolation in general. W eno w examine theisolation po w er of this method on a larger problem. W elookatarealindustryexampleofusingtheminim umw eigh t IISco v ertoisolateinfeasibilit y ThisLPisaSONETnet w orkmodelha ving845ro ws,1792columns,and8448nonzeroen tries. TheSONETmodel arises from a newfamily of problems in thetelecomm unications industry 59
PAGE 65
{ it is a m ultidimensional pac king problem with man ycomplicating constrain ts. Specically there are a large n um ber of capacit y and demand constrain ts andalargen um berofsideconstrain ts. Thesesideconstrain ts aregeneratedb yan um berofdieren tsoft w arecodesdependinguponthe exact model being analyzed. An instance of the model w as found to be infeasible,andw asanalyzedusingouralgorithm. Themincardinalit yIIS co v er isolated the infeasibilit y to a single demand constrain t. Since this portionofthemodelw askno wntobev alid,w eigh tsw ereassignedtoro ws oftheinfeasibleproblemandthemin weight IISco v erw asfound. Aw eigh t of 1 w as assigned to all soft w are generated constrain ts, whic h accoun ted for 32% of all ro ws, and a w eigh t of 5 w as assigned to all capacit y and demand constrain ts. These w eigh ts become the objectiv e function v alue intheco v eringproblemforeac hco v eringv ariable. Theco v eringv ariables correspondtoconstrain tsoftheoriginal infeasiblesystem. Resolving, w e w ereabletoisolatetheinfeasibilit ytoanincorrectlygeneratedconstrain t. Looking at the code used to generate this constrain t led to the disco v ery of a family of 5 other improperly generated constrain ts and correction of asectionofcode. UsingOSL,itinitially took3.26secondsontheRS6000 to determine that the problem w as infeasible. Using our algorithm built around the OSL library the iterativ e procedure of iden tifying IISs and solving the minim um cardinalit y IIS co v er to optimalit y took 7.28 seconds. Once w e decided to resolv e the minim um w eigh t IIS co v er, our procedure took 7.21 seconds to conclude the iterativ e process of IIS and optimal co v er iden tication. In order to compare our solution timeliness with state of the art IIS iden tication routines, w e performed another 60
PAGE 66
testtoiden tifyasingle IIS.Againusing theRS6000,w eusedthebuiltin CPLEX IISiden tication routines (basedupon thew orkofChinnec k)to iden tify a single IIS. This diagnosis took 86 seconds (after infeasibilit y w as diagnosed), and yielded an IIS ha ving 6 elemen ts. In this example, w ew ereable to ndboth minim umw eigh t and minim umcardinalit y IIS co v ers in less time than the curren t state of the art IIS iden tier found a single IIS. The analysis path used to debug this example has pro v en successful isolating infeasibilit y in sev eralother problems. Suppose a modeler tak es the extra time during model dev elopmen t to generate w eigh ts for eac h constrain t and includes these w eigh ts as an extra column in the LP form ulation. As a practical consideration, when running the model the bounds for this column can be set to zero. Th us thesupplemen tal debugging information is ignored when exercising the LP model. Ifthe model is found to be infeasible, the w eigh ts will be used b ythemin w eigh tIISco v eralgorithm to w eigh ttheobjectiv efunction of the co v ering subproblem in order to help isolate the infeasibilit y As seen in this example, ha ving constrain t w eigh ts a v ailable can greatly increase theeectiv enessofpostinfeasibilit y analysis. W e presen t an example from the NETLIB infeasible library to demonstrate another k ey adv an tage of the min IIS co v er. The W OODINFEproblem is a small net w orkexample with 36 ro ws and 89 columns. AnIISinfeasibilit y isolation fromMINOS(IIS)isasingle functional constrain t(plusnonnegativit yconstrain ts). Ho w ev er,theminIISco v erconsists of 2 functional constrain ts. This problem has t w o disjoin t modeling errors whic h can not both be iden tied b y a single IIS. In infeasibilit y 61
PAGE 67
instanceswithm ultiplemodelingerrorstheco v eringapproac hisespecially po w erful. 5.3 F orm ulation of P the Alternativ e P olyhedron, for General Linear Programming Problems. W e no w turn our atten tion bac k to the problem of iden tifying IISs. Theorem2.6 canbe restatedin amoregeneral setting: Theorem 5.1 (General V ersion of GleesonRy an Theorem) Giv en theinconsisten t system S = f x 2 Q n j A x b ; C x = d; L x U g ; theindicesoftheminimal infeasible subsystemsof S areexactlythesupports of the v ertices of the polyhedron P = f y ; w ; v ; z 2 Q m j y T A + w T C + v z =0 ; y T b + w T d + v T U z T L = 1 ; y ; z ; v 0 ; w unrestricted g Notethatiftheonlyboundson x arenon{negativit yconstrain ts, w ecan simplify theabo v eform ulation: Theorem 5.2 (General V ersion II of GleesonRy an Theorem) Giv en theinconsisten t system S = f x 2 Q n j A x b ; C x = d ; x 0 g ; theindicesoftheminimal infeasible subsystemsof S areexactlythesupportsofthev erticesofthepolyhedron P = f y ; w 2 Q m j y T A + w T C 0 ; y T b + w T d = 1 ; y 0 ; w unrestricted g Inotherw ords,w edonotneedtoexplicitlyhandlenon{negativit y constrain ts, but can simply c hec kthe status of the slac k v ariables of the alternativ e system to determine if non{negativit y of some x i is included 62
PAGE 68
in an IIS. Also, this helps reduce the size of the LP instance w e solv e at eac hstep. If the righ t hand side of the \cone{bounding" constrain t w ere left as 1 for large problems, n umerical instabilit y w ould result. W e observ edonsev eralproblems thatwhenw exedat0those v ariables in the alternativ e systemwhic hareintheco v eringsolution, w eobtained anIIS iden ticaltotheonejustpreviouslygenerated. Butthismeansthatintrying tondan IISnot co v eredb ythecurren tsolution, w eha v egenerated one that is co v eredb ythe curren tsolution. Examinewhat can happen if P has man ycolumns. Assumethatw eha v ethefollo wingsystemfor P : y T A 0,where eac h a ij 0for i =1 ;:::;m and j =1 ;:::;n ,and y T b = 1,where b = 1 ( 1 isthe m v ectorof1's). Alsoassumethatthezerotolerancecutois 1.0E07, soallv alues equaltoorlessthan1.0E07 areconsideredtobe0. Then, y =1 : 0 E 07satises therstconstrain t,andif m =10 ; 000 ; 000, then P m 1 (1 : 0 E 07)( 1)= 1,so thesecond constrain t is also satised. No weac h y i iswithin epsilonof0andsoshouldbeconsidered0. Instead, w eha v eallo w edasolution whic his\n umerically"feasibletobeiden tied b ytheoptimizer. Ho w ev er, since the v alues of the basic v ariables are belo w the soft w areimposedtolerance,theyshouldbeconsidered0,andsow eshould ha v ethat P m i =1 ( y i k i )=0for an yk ;whic hmeansthatthesolutiontothe alternativ esystemis not basicfeasible. Whenthis\solution" isiden tied asbeingfeasible,thenw eiden tifysubsystemswhic hare not IISs. Inthis example, w e can alleviate this problem b y setting the righ t hand side of 63
PAGE 69
the second (or cone{binding) constrain t to be equal to P i b i = m (the negativ e of the n um ber of v ariables in the problem). This will eliminate theproblemfortolerancesgreaterthanorequalto1 =m fortheconditions outlined abo v ewhic hare notnecessarily w orst case. F or the general case described in Theorem 5.1, w e extend the logic used abo v eto determinethata cone{binding constrain t eliminating suc hproblems could be: y T b + w T d + v T U z T L = (( X k j b k j )+( X k j d k j )+( X j j U j j + j L j j )) : T oseewh yabsolutev aluesareincludedonthesum,considerthefollo wing modication to the previous example. Assume that there is a 10 ; 001 st constrain t, ha ving a righ t hand side v alue of 10 ; 000. Then, P i b i = 0, whic hdoesnoteliminatethesolution y =0. W eha v enoty etencoun tered a problem forwhic h this normalization fails toeliminate theproblem. 5.4 Finding IISs Tw o sligh tly dieren t approac hes ma y be used to iden tify IISs of S First, w e consider using the simplex algorithm to nd extreme poin ts of P By bounding the objectiv e function y T b of the alternativ e system and including it in the constrain t set of P w e free ourselv es to usea\surrogate" objectiv efunctiontoheuristically guideoursearc h. W e ha v e experimen ted with using 1 as the objectiv e w eigh t. This should tend to nd small cardinalit y IISs, although to nd the true minim um cardinalit yIISw em ustsolv eaxed{c hargein tegerprogrammingproblem (as demonstrated b y Green berg and Murph y [26]). Additionally these w eigh ts can be modied at eac h step b y incremen ting the w eigh t of eac h 64
PAGE 70
v ariable appearing in the curren t IIS. In this w a y w e heuristically tend to nd IISswhic ho v erlapin thefew estn um berof elemen ts. This should help in the iden tication an optimal co v er to the full MWIC problem b y iden tifying setsof nono v erlapping IISs. W e ha v e also considered ignoring the objectiv e function when looking forextremepoin tsof P andusingtherstfeasiblesolutionfound. Since ev eryextremepoin t corresponds to an IIS,w estill iden tify anIIS. As expected, this tak es few er piv ots to nd an IIS than solving to optimalit ywiththesurrogateobjectiv edescribedabo v e. Ho w ev er,thesa vings in IISiden tication timema ybeoset b ythet ypically larger cardinalit y IISs found and the increased n um ber of co v ering subproblems needed to solv e. Ratherthangenerating IISsindividually w ecangenerateman y b y solving a single LP if w e instead searc h for extreme ra ys on the cone P 0 ,as suggested b yGreen berg[21]. W econsider thefollo wing linear programming instance basedupon ourdenition of P 0 : min y T b subjectto y T A =0 y 0 Since S is infeasible, Theorem 2.1 implies that P 0 is feasible and hence un bounded. Therefore, w e m ust be able to nd at least one non basic v ariableofnonoptimalsignatterminationofournewLP .Ifthisnon basic v ariable is not bloc k ed, then the v ariable and all basic v ariables whic h correspond to non{zero tableau column en tries for the non basic form the 65
PAGE 71
support set of an IIS. In other w ords, the supports of the extreme ra ys of P 0 are IISs in the original infeasible system, S In general, w e will ha v emorethanasingle suc hnon basic v ariable,sow ecanndman yIISs from one LP solution. By piv oting w e can nd all IISs of S b y suc h a procedure. In general, w e will ha v e to perform sev eral piv ots before iden tifying un boundedness due to the degeneracy of the 0 solution. In practice, this method can reduce the n um ber of iterations to solv e the minim um w eigh t IIS co v er. F or example, let an IIS of S be iden tied as f 1,2,3,4,5,8,10,15 g andsupposethatconstrain t15isin ev ery IIS(andso is the minim um IIS co v er). If f 1 g is iden tied as the co v er, there could existanotherIISoftheform f 2,3,4,5,6,8,10,15 g andsoforth. Therecould bepoten tial toiden tify man y IISsbeforetheminIISco v eris solv edoptimally If a conical solution yields m ultiple IISs, the total n um ber of co v ering subproblems (and hence IIS iden tication problems) can be reduced. This becomes importan t for large infeasible problems whic h can ha v e a single constrain t as the optimal min IIS co v er, while ha ving IISs with h undredsofelemen tsin them. Sincesolving ontheconeofthealternativ e systemallo ws usthe poten tial toiden tifym ultipleIISsfromasinglebasis andingeneraltak es few er piv ots to solv e, the idea is to use this as a \jump{start" for the algorithm, and then to use the extreme poin t method to nd IISs with specic c haracteristics. W e can illustrate eac h of these methods using the follo wing examplefrom[13]usingLINDO.Supposew earegiv entheinfeasiblesystem 66
PAGE 72
S denedas: 1 : 0 : 5 x 1 + x 2 0 : 5 2 : 2 x 1 x 2 3 : 0 3 : 3 x 1 + x 2 6 : 0 4 : x 5 2 : 0 5 : 3 x 4 x 5 2 : 0 6 : x 4 5 : 0 7 : x 1 + x 5 10 : 0 8 : x 1 + 2 x 2 + x 4 14 : 0 9 : x 2 + x 4 1 : 0 with all x i 0 If w esolv e to optimalit y using objectiv ew eigh ts 1 for all v ariables of the alternativ esystem,after6piv ots,w end f 4,5,6 g asanIIS.Ifw esolv eto feasibilit yonly(ignoretheobjectiv ew eigh ts),w endtheIIS f 1,2,3 g after 5 piv ots. Solving on the cone w e nd 3 IISs after only 4 piv ots: f 4,5,6 g f 1,2,3 g and f 1,2,5,6,7 g The min IIS co v er is f 1,5 g so b y solving on the cone, w e initialize our procedure with enough IISs to solv e the co v er problem only once. 5.5 Heuristic Solution of Co v ering Problems Theco v eringproblemscanbesolv edheuristicallyatin termediate steps. W ecandetermineif thesesuboptimal co v ersaretrueco v ersof the min w eigh t co v ering problem just as w e did when solving this problem optimally in Step 3 of our algorithm. If a true optimal co v er is desired, theco v eringproblem m ustbesolv ed optimally beforeterminating. The greedy heuristic [14] can be used at in termediate steps. 67
PAGE 73
When no IIS is found that is not co v ered b y the greedy solution, w e solv e theco v eringproblem optimally Iftheco v eris thesame cardinalit y asthatfoundb ythegreedyheuristic,w earedone. Otherwise,w endan IIS not co v eredb y thecurren tsolution and con tin ue thealgorithm. The greedy algorithm will not guaran tee an optimal co v er; ho w ev er, it seems to w orkw ell in practice. F or the problems in the infeasible library on NETLIB, w e ha v e foundthatt ypicallyonlyasmallfractionoftotalalgorithm time(usually less than 10%) is spen t solving the co v ering subproblems. This result is based on iden tifying IISs singly b y searc hing for extremepoin t solutions of P ,sotheresultscouldc hangesignican tly withimpro v emen tso v erthe basic form of the algorithm. Itshould be noted that the dicult y of the co v ering problem has been displa y ed on a few relativ ely small problems. F or the NETLIB problem MONDOU2, more than 97% of the CPU time (115 of118 seconds)w as spen tsolving a single instance oftheco v ering subproblem ha ving only 9 constrain ts. This demonstrates a needtoboth learn more about the structure of this special IIS co v ering problem and perhaps explore more fully using the greedy algorithm, or a modication of it,at in termediatesteps. 5.6 Computational Results All comparisons (unless otherwise stated) w ere run on an IBM RS6000 using the IBM OSL object library and F OR TRANcode written b ytheauthor. Allrunsw eremadewithappro ximatelythesamecomputer load {only asingle userw asonthesystem. W eexperimen tedwith three v ersions of our algorithm. All three solv e the co v ering subproblem to 68
PAGE 74
optimalit yateac hstepusingtheOSLEKKMSSLsubroutine. W eha v enot y etcompletedimplemen tationofav ersionwhic hwillsolv eonthecone,so all threev ersionspresen tedheresearc hforextremepoin tsolutions onthe boundedalternativ esystem. W edistinguish eac hv ersionb ytheobjectiv e function used in solving the alternativ e system. The baseline algorithm, IIS CO V 1, w eigh ts the coecien ts of the objectiv efunction to all 1's in an attemptto nd small cardinalit y IISs. V ersion 2, IIS CO V 2, w eigh ts the coecien t of eac h v ariable according to ho w man y generated IISs it already appears in. In tuitiv ely this will tend to nd IISs whic h o v erlap as little as possible. Finally v ersion 3, IIS CO V 3, ignores the objectiv e function,and therstextremepoin tfoundis thesolution. This will tend to iden tify IISs faster, though perhaps at the trade o of nding larger cardinalit y IISs. Note that IIS CO V 2 will dier from IIS CO V 1 only when more than 1 IIS is found to optimally solv e the co v ering problem. Therefore, w e did not run IIS CO V 2 if w e found that only 1 IIS w as neededto ndtheoptimal co v er. Thetestbedofproblemsconsists oftheinfeasible LPlibrary on NETLIB,originallysetupb yJohnChinnec k. Asummaryoftheproblems is giv enin T able 5.1. In order to facilitate the analysis of results, w e partitioned the problems in to 3setsaccording to theirsize. W econsidered\small" problemstobethoseha vingfew erthan100ro wsand100columns. \Medium" problems are those with bet w een 100 and 1000 ro ws and 100 to 1000 columns. The remainderare\large" problems. T able 5.2 presen ts the results of our 3 approac hes on the small 69
PAGE 75
Problem OriginalProblem Alternativ eSystem Constrain ts V ariables Nonzeros Constrain ts V ariables Nonzeros BGDBG1 348 407 1440 408 390 1737 BGET AM 400 688 2409 689 689 2957 BGIND Y 2671 10116 65502 10117 2671 67589 BGPR TR 20 34 64 35 20 76 BO X1 231 261 651 262 492 1173 CERIA3D 3576 824 17602 825 3576 17851 CHEMCOM 288 720 1566 721 625 2180 CPLEX1 3005 3221 8944 3222 3223 10883 EX72A 197 215 467 216 412 897 EX73A 193 211 457 212 404 879 F OREST6 66 95 210 96 71 226 GALENET 8 8 16 9 16 38 GOSH 3792 10733 97231 10734 3792 97433 GREENBEA 2393 5405 30885 5406 2941 31926 ITEST2 9 4 17 5 9 26 ITEST6 11 8 20 9 11 31 KLEIN1 54 54 696 55 54 700 KLEIN2 477 54 4585 55 477 4600 KLEIN3 994 88 12107 89 994 12115 MEXP 1383 1500 5027 1501 1383 5755 MONDOU2 312 604 1208 605 1520 3088 P ANG 361 460 2652 461 453 2587 PILOT4I 410 1000 5141 1001 717 5860 QUAL 323 464 1646 465 835 2662 REA CTOR 318 637 2420 638 932 3699 REFINER Y 323 464 1626 465 835 2641 V OL1 323 464 1646 465 835 2662 W OODINFE 35 89 140 90 69 208 T able 5.1: Problem T estBed 70
PAGE 76
problems. The measures w e use in comparing the approac hes are total solution time of the co v ering problem (CPU seconds), n um ber of IISs iden tied while solving the co v ering problem optimally ( not the n um ber of IISs in the co v er), n um ber of piv ots to rst IIS, a v erage n um ber of piv otsperIIS,andthesmallestcardinalit y IIS.Inanalyzing infeasibilit y it ma y be useful to measure the size of an IIS in terms of the n um ber of actual constrain ts it con tains, rather than constrain ts and v ariable bounds both nonnegativit y and general upper and lo w er bounds. Note that IIS size refers to the n um ber of constrain ts and v ariable bounds exclusiv e of non{negativit y bounds Information on non{negativit y bounds is a v ailable with the solution approac h, w e ha v e c hosen to not include it in the IIS reporting. The columns for a v erage IIS size and smallest cardinalit y IIS are th us subdivided in to IIS size and n um ber of actual constrain ts. On most problems, v ery little time is spen t in solving the min w eigh tco v eringsubproblem,andfrom50%to95%ofthetimeisspen tin iden tifying IISs { solving the alternativ e system LP Therefore, another reasonable measureofho ww elleac halgorithm performsisthen um berof simplex piv ots requiredto ndan IIS. Therstfewpiv otsmadeb yOSLduringPhase1willberandom. This is done initially to speed up the simplex algorithm, and later other pricing sc hemes are used. This means that when rerunning a problem with the same algorithm w e will ha v ev ariance in our solution times. On the problems w e look ed at, this v ariance w as t ypically 5% or less. F or this reason, w e will consider time dierences bet w een algorithms to be 71
PAGE 77
Problem Algorithm Co v er #IISs Piv ots Avg.IIS SmallestIIS Time Generated IIS1 Avg. Size Ro ws Size Ro ws BGPR TR IIS CO V 1 0.19 1 18 10.0 7.0 7.0 7 7 BGPR TR IIS CO V 3 0.20 1 14 8.0 14.0 14.0 14 14 F OREST6 IIS CO V 1 0.73 2 124 50.3 64.0 59.0 64 59 F OREST6 IIS CO V 2 0.71 2 124 51.0 64.0 59.0 64 59 F OREST6 IIS CO V 3 0.61 2 81 29.3 69.5 64.5 69 64 GALENET IIS CO V 1 0.19 1 7 3.5 6.0 3.0 6 3 GALENET IIS CO V 3 0.20 1 5 3.0 6.0 3.0 6 3 ITEST2 IIS CO V 1 0.38 3 4 2.0 3.7 3.7 3 3 ITEST2 IIS CO V 2 0.35 3 4 2.0 3.7 3.7 3 3 ITEST2 IIS CO V 3 0.36 3 4 1.8 3.7 3.7 3 3 ITEST6 IIS CO V 1 0.65 3 6 2.8 3.3 3.3 3 3 ITEST6 IIS CO V 2 0.69 3 9 4.0 3.3 3.7 3 3 ITEST6 IIS CO V 3 0.65 6 3 1.7 3.7 3.7 3 3 KLEIN1 IIS CO V 1 0.89 1 162 81.5 51.0 51.0 51 51 KLEIN1 IIS CO V 3 0.82 1 116 71.5 51.0 51.0 51 51 W OODINFE IIS CO V 1 0.46 2 24 12.6 2.0 1.0 2 1 W OODINFE IIS CO V 2 0.41 2 24 12.6 2.0 1.0 2 1 W OODINFE IIS CO V 3 0.48 2 9 11.0 2.0 1.0 2 1 T able 5.2: Results for Small Problems 72
PAGE 78
signican t only if they are greater than 10%. In this ligh t, no signican t timedierenceisfoundbet w eenthealgorithms onthesmallproblemtest bed. On the4 problems whereall 3 algorithms w ererun,IIS CO V 2 w as fasteron2,IIS CO V 3andIIS CO V 1w erefasteron1eac h,withallthree indistinguishable onone. Ifw etrytov erifyourassumptions onstrengths of eac halgorithm, w esee that IIS CO V 3 tak esfew erpiv ots both to nd the rst IIS and on a v erage; but requires more IISs to solv e the co v er problem only on ITEST6. IIS CO V 1 does nd smaller IISs on a v erage than the other algorithms. Not m uc hmore performance information can be obtained from thesmall problems. Algorithmic comparisons for the \mid{sized" problems are presen tedin T able 5.3. W eha v esev eralin teresting problems in termsof the size of the min w eigh t IIS co v ering problem solv ed. With these harder problems, w e see a n um ber of in teresting trends. In 10 of the 12 problems, IIS CO V 3 tak es few er piv ots to nd an initial IIS as expected. Ho w ev er,this algorithm has the lo w est a v erage n um berof piv ots per IIS in only 7 of the 12 problems. What w e see is that both IIS CO V 1 and IIS CO V 2t ypicallytak emorepiv otstondaninitial solution. Ho w ev er, only afewpiv ots,t ypically few erthan25,areneededtondIISssatisfying optimalit y conditions forthealternativ e systemaftertheinitial basic feasible solution is found. Th us some of the adv an tage of IIS CO V 3 is lostwhenndingman yIISs. Infact,onthoseproblemswhereIIS CO V 3 took few er piv ots to nd its initial IIS but had a higher a v erage piv ot v alue, an algorithm needing to nd a larger n um ber of IISs to solv e the co v eringproblemhadthelo w esta v eragepiv otv alue. Th usthemoreIISs 73
PAGE 79
oneneedstond,thelessimportan ttheinitial n um berofpiv otsbecomes in termsof solution time. Additionally ,w eseethatIIS CO V 3solv estheco v eringproblem faster on 8 of the 9 problems with time distinctions. W e also note that it nds thesmallest a v erageIISon 3 ofthe9problems wheredistinction is made,and ndsmoreIISsin solving theco v erononly 4problems and ndstheleastIISsinsolvingtheco v er5times(excludingties). Thisseems tocon tradictthein tuitionthatw ew ouldndIISsfaster,butrequiremore IISsto solv etheco v ering problem. Asw elook at theresults for thelarge problems (seeT able 5.4), w e see that an undirected searc h for IISs is faster. IIS CO V 3 again dominates, being thefastestalgorithm on8ofthe9problems,taking the few est piv ots to the rst IIS on all problems, and taking few est a v erage n um berofpiv otson6of9problems. Italsondsthesmallesta v erageIIS on 4 of6 problems wheredistinction is made. W e also compare (T able 5.5) the information pro vided b y the IISco v ertothatobtainedfromIISisolation viaMINOS(IIS)(from[11]). Man yoftheproblemsinthistestbedw erecreatedb ytakingafeasibleLP instanceandmodifyingasingleboundorconstrain tun tiltheproblemw as infeasible. F our of the problems in the test bed w ekno w to be infeasible in original form { BGDBG1, BGPR TR, GREENBEA, and MONDOU2. Of these problems, only BGPR TR has an IIS co v er of 1 (and requires a single IISto solv e theco v er). Th us although therearea large n um berof problemsinthetestbedha vingsingletonIIS co v ersandrequiringonlya singleIIStondtheirco v er,thisma ybeanartifactoftheirconstruction. 74
PAGE 80
Problem Algorithm Co v er #IISs Piv ots Avg.IIS SmallestIIS Time Generated IIS1 Avg. Size Ro ws Size Ro ws BGDBG1 IIS CO V 1 8.05 33 112 12.4 8.1 7.4 2 2 BGDBG1 IIS CO V 2 6.15 24 112 14.6 7.0 6.5 2 2 BGDBG1 IIS CO V 3 7.74 36 34 8.6 6.9 6.1 2 2 BGET AM IIS CO V 1 10.42 5 242 206.8 68.0 62.2 8 7 BGET AM IIS CO V 2 11.79 6 150 145.4 59.5 51.7 13 12 BGET AM IIS CO V 3 9.24 7 20 89.1 173.1 140.7 18 17 BO X1 IIS CO V 1 1.46 2 13 36.0 53.5 52.5 10 9 BO X1 IIS CO V 3 1.46 2 12 34.3 54.5 53.5 10 9 CHEMCOM IIS CO V 1 3.74 2 177 136.0 26.0 16.0 25 15 CHEMCOM IIS CO V 2 3.73 2 177 142.0 24.0 14.0 23 13 CHEMCOM IIS CO V 3 3.63 1 137 204.5 27.0 15.0 27 15 EX72A IIS CO V 1 1.35 3 104 27.0 69.0 68.0 59 58 EX72A IIS CO V 2 1.66 3 104 39.5 70.3 69.3 61 60 EX72A IIS CO V 3 1.22 2 108 36.0 66.5 65.5 59 58 EX73A IIS CO V 1 0.92 1 88 44.0 28.0 27.0 28 27 EX73A IIS CO V 3 0.97 1 79 42.5 26.0 25.0 26 25 KLEIN2 IIS CO V 1 8.03 13 597 85.4 53.2 53.2 53 53 KLEIN2 IIS CO V 2 5.46 4 574 173.8 54.0 54.0 53 53 KLEIN2 IIS CO V 3 5.38 6 476 113.9 55.2 55.2 53 53 P ANG IIS CO V 1 3.21 1 392 204.5 16.0 13.0 16 13 P ANG IIS CO V 2 2.59 1 250 127.5 16.0 13.0 16 13 P ANG IIS CO V 3 2.65 2 183 76.3 19.5 16.0 18 15 QUAL IIS CO V 1 8.05 5 707 149.3 185.4 124.0 142 92 QUAL IIS CO V 2 12.12 5 707 223.2 184.8 103.6 143 82 QUAL IIS CO V 3 7.40 6 558 107.9 180.6 124.0 134 90 REA CTOR IIS CO V 1 5.58 2 152 192.0 5.0 1.0 5 1 REA CTOR IIS CO V 2 4.44 2 152 125.7 5.0 1.0 5 1 REA CTOR IIS CO V 3 3.89 2 100 119.3 5.0 1.0 5 1 REFINER Y IIS CO V 1 22.26 38 665 42.5 135.2 91.2 92 61 REFINER Y IIS CO V 2 19.99 31 665 48.1 134.0 89.0 93 63 REFINER Y IIS CO V 3 16.51 23 577 72.6 145.7 93.4 97 62 V OL1 IIS CO V 1 13.45 13 699 83.3 180.8 121.7 137 91 V OL1 IIS CO V 2 20.70 10 699 278.5 180.3 121.6 137 91 V OL1 IIS CO V 3 10.75 8 715 138.6 182.6 120.9 160 104 T able 5.3: Results for Mid{sized Problems 75
PAGE 81
Problem Algorithm Co v er #IISs Piv ots Avg.IIS SmallestIIS Time Generated IIS1 Avg. Size Ro ws Size Ro ws BGIND Y IIS CO V 1 139.19 1 1908 1140.0 3.0 3.0 3 3 BGIND Y IIS CO V 3 126.34 1 219 1114.0 3.0 3.0 3 3 CERIA3D IIS CO V 1 56.32 3 1905 758.0 123.3 123.3 73 73 CERIA3D IIS CO V 2 66.46 3 2406 921.0 141.3 141.3 74 74 CERIA3D IIS CO V 3 26.45 8 538 99.0 144.8 144.8 73 73 CPLEX1 IIS CO V 1 38.50 1 1473 1214.5 5.0 5.0 5 5 CPLEX1 IIS CO V 3 33.83 1 212 1058.5 5.0 5.0 5 5 GOSH IIS CO V 1 563.91 1 6009 3305.5 49.0 49.0 49 49 GOSH IIS CO V 3 637.34 2 1885 2350.0 72.0 72.0 68 68 GREENBEA IIS CO V 1 410.50 3 2983 1955.8 9.0 6.3 4 2 GREENBEA IIS CO V 2 359.95 4 2983 1319.6 17.8 15.0 4 2 GREENBEA IIS CO V 3 322.34 3 10 1442.8 8.3 5.3 4 1 KLEIN3 IIS CO V 1 97.16 29 1571 506.0 101.7 101.7 95 95 KLEIN3 IIS CO V 2 49.77 12 1560 538.8 87.4 87.4 86 86 KLEIN3 IIS CO V 3 36.34 21 1137 205.6 85.8 85.8 84 84 MEXP IIS CO V 1 12.37 2 377 157.0 8.0 8.0 7 7 MEXP IIS CO V 3 8.76 1 176 237.5 6.0 6.0 6 6 MONDOU2 IIS CO V 1 17.69 14 503 60.8 163.5 146.6 22 17 MONDOU2 IIS CO V 2 118.63 13 503 58.1 182.3 163.8 22 17 MONDOU2 IIS CO V 3 17.11 9 460 62.6 146.9 128.9 22 17 PILOT4I IIS CO V 1 28.82 1 659 930.0 1.0 1.0 1 1 PILOT4I IIS CO V 2 18.05 1 1010 629.0 1.0 1.0 1 1 PILOT4I IIS CO V 3 7.20 1 86 202.5 1.0 1.0 1 1 T able 5.4: Results forLarge Problems 76
PAGE 82
W efeelthattheminw eigh tIISco v erwillbeav aluabletoolindebugging LPs atthemodel dev elopmen tand in tegration stage. In order to gain a perspectiv e on the solution time to solv e the MCIC problem exactly w e mak e a comparison with the heuristic approac h of Chinnec k [12] on a subset of the NETLIB infeasible library Chinnec k's runs w ere made using a modied v ersion of MINOS(IIS) on anIBMcompatible66MHz80486D X2microcomputer. Chinnec k'sresults arepresen tedin[12]intermsofatimeratio: theco v eringtimedividedb y the Phase 1 solution time. W econ v ertour results in to thesame form,so the comparison is as fair as possible (considering that w e use a dieren t optimization pac k age). These results arepresen tedin T able 5.6. Itis in teresting to note that Chinnec k's heuristic nds the minim um cardinalit y co v erin all instances; ho w ev er,as demonstrated previously ,itwillnot guaran tee aminimalco v erupontermination. Thetimes presen ted are particularly in triguing since the time ratio to solv e exactly is smaller on 6 of the 14 problems! W e should also note that in solving exactlyalargesetofIISsis determined. Using Chinnec k'salgorithm, no IISsareiden tied. In[12],anextensionisgiv enfordoingso,buttheCPU times presen ted arefor co v eriden tication only Th us, moreinformation is giv en in less time on a substan tial portion of the test bed b y solving optimally! 77
PAGE 83
Problem MINOS(IIS) MinIISCo v er SmallestIIS Ro ws Cardinalit y IISsF ound Size Ro ws BGDBG1 2 12 38 2 2 BGET AM 7 1 5 8 7 BGIND Y 1 1 3 3 BGPR TR 5 1 1 7 7 BO X1 8 1 2 10 9 CERIA3D 73 1 3 73 73 CHEMCOM 7 1 2 23 13 CPLEX1 5 1 1 5 5 EX72A 58 1 3 59 58 EX73A 24 1 1 26 25 F OREST6 55 1 2 64 59 GALENET 2 1 1 6 3 GOSH 1 1 49 49 GREENBEA 1 2 3 4 1 ITEST2 3 2 3 3 3 ITEST6 2 2 3 3 3 KLEIN1 50 1 1 51 51 KLEIN2 51 1 4 53 53 KLEIN3 74 1 21 84 84 MEXP 5 1 1 6 6 MONDOU2 15 3 9 22 17 P ANG 11 1 1 16 13 PILOT4I 1 1 1 1 1 QUAL 76 1 6 134 90 REA CTOR 1 1 2 5 1 REFINER Y 47 1 38 92 61 V OL1 80 1 10 137 91 W OODINFE 1 2 2 2 1 T able 5.5: Min IISCo v erand MINOS(IIS)IISIsolation Comparison 78
PAGE 84
Finally w e compare this approac h with the xed c harge form ulation presen tedin Section 2.4: min P m i =1 z i subjectto A x + s s 0 = b s 0 M z forconstan t Msucien tlylarge x ; s 0 z binary Thexedc hargeIPform ulationsw eresolv edontheRS6000computer using v ersion 3.0 of the CPLEX optimization library Results for thiscomparisonaregiv eninT able5.7. Thetimegiv enisCPUsecondsto completely solv e the problems. The Min IIS Co v er results presen ted are for thev arian t IIS CO V 3. The test bed consists of a subset of problems from the NETLIB infeasible library F or small problems (W OODINFE, ITEST2,andITEST6),thexedc hargeapproac houtperformstheMWIC approac h. Ho w ev er,thelargestoftheseproblemsisW OODINFEwith35 constrain ts and 89 v ariables. As w emo v etolarger problems, w eseethat the xedc harge form ulation becomes increasingly moredicult to solv e. CPLEXw asunabletopro v etheoptimalit yofthein tegersolution forthe BGDBG1 problem, whic h has 348 constrain ts and 407 v ariables, giv en a maxim um of 20,000 nodes for the branc h and bound tree. The time to solv e this problem is th us greater than the 825 seconds tak en to ev aluate 20,000 nodes. IIS CO V 3 solv es the largest problem in this test bed, MONDOU2 (312 constrain ts and 604 v ariables), in appro ximately 6% of 79
PAGE 85
the time the xed c harge form ulation tak es. Th us, as problem size increases,theMWICform ulation becomesthepreferredalgorithm. 80
PAGE 86
Problem MINOS(IIS) MinIISCo v er Cardinalit y TimeRatio Cardinalit y TimeRatio BGDBG1 12 55.5 12 24.6 BGIND Y 1 0.2 1 3.4 BGPR TR 1 1.0 1 1.5 CHEMCOM 1 0.6 1 4.3 CPLEX1 1 1.3 1 1.2 GREENBEA 2 2.1 2 3.1 ITEST2 2 1.0 2 35.0 ITEST6 2 2.2 2 16.3 KLEIN2 1 1.7 1 1.4 KLEIN3 1 6.0 1 3.1 MONDOU2 3 69.3 3 26.3 REA CTOR 1 7.1 1 1.9 REFINER Y 1 7.1 1 10.6 W OODINFE 2 2.5 2 6.8 T able 5.6: Min IISCo v erand MINOS(IIS)IISCo v erComparison Problem FixedCharge Min IISCo v er Time Time BGDBG1 > 825.00 7.74 ITEST2 0.18 0.36 ITEST6 0.30 0.65 KLEIN2 307.50 5.38 MONDOU2 297.21 17.11 W OODINFE 0.24 0.48 T able 5.7: MinIISCo v erand FixedCharge IISCo v erComparison 81
PAGE 87
6. Extensions to Solving the Linear Discriminan t Problem W e no w consider the problem of nding a linear separator, or separating h yperplane for t w o sets of data. Giv en t w o poin t sets A 1 and A 2 (where the coordinates of a poin t correspond to a ro w of the appropriatematrix),w ewishtoiden tifyah yperplane H = f j h = b g suc h that h > b if 2 A 1 and h < b if 2 A 2 If suc h a h yperplane H exists,w esa ythatthesets A 1 and A 2 are linearlyseparable Inthecase where the sets are not linearly separable, for an y h and b there exists a poin t(WLOG) 2 A 1 suc hthat h b andw esa ythat ismisclassied for this h and b Th us, if the sets are not linearly separable, w e wish to obtain the h yperplane that minimizes some measure of misclassication of poin ts. This classication problem has a v ariet y of applications across a large spectrum of disciplines including pattern recognition and neural net w orks. Figure6.1demonstratesalinearseparablesystemwithanoptimalseparatingh yperplane(left)andanonlinearly separablesystemwith a h yperplane minimizing then um berof misclassications (righ t). t t t t tt ddd dd d t t t t td n n n n n n n n ddt dd d Figure 6.1: Linearly Separable (left)and NonSeparable (righ t) Sets W ecanform ulatetheproblemofndingalineardiscriminan tas
PAGE 88
thefollo wing feasibilit y problem: 1 : h b forall 2 A 1 2 : h b 0 forall 2 A 2 h ;b free Note that an y feasible solution h and b to the linear program will dene a h yperplane separating the sets A 1 and A 2 W e force a true separation of the sets b y restricting the poin ts of A 1 to be distance at least fromtheh yperplane. Thisalsoeliminatesthetrivialsolution h = 0 b =0. W eneednotforcethepoin tsofset A 2 oof h = b ,sinceour\true" separator is the h yperplane h = b +( = 2). Also note that the c hoice of objectiv eisarbitrary atthispoin tifthesetsareseparable,w ecareonly to nd a separating h yperplane. There are man y modications w e can mak e to this form ulation in order to \bias" the h yperplane to w ards one setortheother(forexample,seeGlo v er[20]orBennettandMangasarian [5]). This linear programming form ulation is infeasible if there is no separating h yperplane. Ifw endtheminim umw eigh tIISco v er,w eha v e found theminim umw eigh t subsetofpoin ts whic hm ustberemo v edfrom thesysteminorderforafeasiblesolution tobefound. Inotherw ords,w e willndtheminim umw eigh tsubsetofpoin tswhic hm ustbemisclassied in order thata separator be found fortheremaining poin ts. Using Theorem 5.1, w e obtain the follo wing alternativ e system 83
PAGE 89
for thediscriminan t problem: 1 : y T A 1 + z T A 2 =0 2 : y T z T =0 3 : y T = 1 y 0 ; z 0 Since the problem of minimizing the n um ber or w eigh t of misclassied poin ts is NP hard, researc h eorts ha v e focused on iden tifying linearprogrammingform ulationswhic hminimizedieren tmeasuresofthe misclassication and on heuristic approac hes to appro ximating the true minim um cardinalit y/w eigh t setof misclassied poin ts. W ecancomparetheperformanceofthis exactform ulation with a linear programming form ulation due to Bennett and Mangasarian [5]. Let us assume that there are m poin ts in A 1 and k poin ts in A 2 Then Bennettand Mangasarian solv e thefollo wing: min P m i =1 e i =m + P k i =1 f i =k subjectto h b + e i for all 2 A 1 h b f i 0 for all 2 A 2 e ; f 0 h ;b free The principal propert y that distinguishes this form ulation from otherlinearprogrammingmethodsisthatforthelinearlyinseparablecase thisform ulationwillalw a ysgenerateanon trivialsolutiontothelineardiscriminan t problem and does so without theaddition ofextra constrain ts. Notethesimilarit y bet w eenthisform ulation and astandard Phase 1LP; 84
PAGE 90
thev ectors e and f arethearticial or elastic v ariable v ectorsofa Phase 1form ulation, andtheobjectiv eseekstominimizeanormalization ofthe sum ofinfeasibilities. In[5 ],BennettandMangasariancomparethisform ulationwitha n um berofothersonsamplesconsistingofdatapoin tsfromtheWisconsin BreastCancerDatabase (seethesamearticleforacompletedescription). This data w as collected b y b y Dr. William H. W olberg of Univ ersit y of Wisconsin Hospitals in Madison. The data base consists of malignan t and benign samples collected in a 9dimensional space. Of the form ulations they examined, theirs performed the best in terms of both few est misclassications and computertimeused. This application lends itself to a deeper discussion of the practicalit y of the linear discriminan t problem. What w e are really looking forisasolution, orseparating h yperplane,whic hcanbefoundonasmall sample setofthedata. This sample setiscommonlycalled a training set in theneuralnet w orkcomm unit y Oncew eha v eobtained this separating h yperplane, it can be used to mak e decisions about the category whic h other data poin ts fall in to. So, b y looking at a represen tativ e sample of data poin ts whose classication w ekno w,w ewish toiden tify aclassication strategy and then test the \classier" on expanded data sets. The Wisconsin BreastCancerDatabaseisbeingusedtodev elopanin telligen t tissue analyzer. Inordertoev aluatetheeectiv enessofourMWICalgorithm,w e made a set of comparisons on the same data set. W e used the 353 data poin ts ofGroup1ofthedataset,ofwhic h165aremalignan tand188are 85
PAGE 91
benign. Thedatasetisinseparable,sow eseektominimizethen um berof misclassied poin ts. The main question to be answ ered here is ho w w ell do the curren t state of the art LP form ulations perform in this task and does our exactapproac h solv etheproblem in a timelymanner. Ouralternativ e systemis based upon thepreviously giv enfeasibilit y problem, whic h is iden tical to Bennett and Mangasarian's LP form ulation with theexclusion of theelastic v ariables e and f W e noted the similarit y bet w een the Bennett and Mangasarian form ulation and that of a Phase 1 LP and also decided to seeho w m uc h better a solution they nd o v er a standard Phase 1 LP In our comparisons, w e also included a v ersion of their form ulation without the elastic v ariables e and f UponcompletionofaPhase1LP ,thearticialv ariables correspond todata poin ts whic h ha v ebeenmisclassied. The Phase 1 LP and Bennett and Mangasarian's form ulation w ererun using theCPLEX optimization pac k age. W emodied a v ersion of ourbest performing MWICalgorithm, IIS CO V 3. Thealgorithm w as modied to nd a set of disjoin t IISs prior to solving the co v ering subproblem. The idea behind this modication w as to reduce the amoun t of time needed to solv e the MCIC problem optimally Again, this code is based upon the IBM OSL optimization pac k age object libraries. All comparisons w ere run on an IBM RS6000. The results are presen ted in T able 6.1 IIS CO V 3 BM Phase 1 Misclassied 6 25 25 CPU Time(sec) 739.3 1.3 1.0 T able 6.1: Linear Discriminan t Analysis Comparison 86
PAGE 92
It is in teresting to note that the BennettMangasarian (BM) form ulation misclassies the same n um ber of poin ts as a standard Phase 1 LP .F romthis example,it appears that theextraeort insolving these problems exactlyis w orthit froma solution qualit y viewpoin t. Although theexactsolution took appro ximately 570 timeslonger toreac hthan the BM form ulation, it still took less than 15 min utes of computing time relativ ely small for a problem whic h y ou w ould be in terested in solving only once. Another in teresting result is that all 6 poin ts whic h w ere misclassied b y the MCIC algorithm w ere benign ev en without explicitly w eigh ting misclassications in this direction as being more fa v orable. In con trast,forboththePhase1andBMform ulations,14malignan tand11 benign poin ts w eremisclassied. Ina trueclassication system,it w ould be desirable to err on the side of classifying benign as malignan t rather than therev erse. Itappears that this approac h is a viable meansof solving linear discriminan t problems of fair magnitude. 87
PAGE 93
7. Summary and Areas for F urther Researc h W e ha v e dev eloped an algorithm for nding the MWIC of an infeasible system of linear equations. W e ha v e demonstrated the utilit y ofthisalgorithmforinfeasibilit y analysisoflinearprogrammingproblems andinlineardiscriminan tanalysis wherew ec hoosetominimizethen umber ofmisclassied poin ts. Inaddition tothisalgorithmic dev elopmen t,w eha v enotedthat these co v ering problems ha v e a structure to them whic h seems to mak e themmoretractablethangeneralsetco v eringproblems. W eha v eexplored thefacialstructureoftheseco v eringpolyhedraandiden tiedfacetdening inequalities. W e ha v e also generalized these results to a larger class of co v eringproblems, called polyhedral co v eringproblems. W e ha v e review ed the theory of irreducible inconsisten t subsystems and pro vided a generalization of V an Loon's result. Additionally w eha v eestablished alinkbet w eenthemethodofGleesonandRy anwith V an Loon's. W e ha v e ev aluated a n um ber of protot ypes of our algorithm on theNETLIBinfeasiblelibraryanddemonstratedtheutilit yofthesealgorithmsonafewindustryexamplesofinfeasible LPs. Theproblemsinthe NETLIBinfeasible library in man yinstances are feasible problems whic h ha v ebeenperturbed,perhapsarticially ,in toinfeasibleinstances. A tthis poin t,itw ouldbein terestingtoanalyzeotherinfeasibleindustryproblems to determine on what t ypes of problems the MWIC approac h pro vides a
PAGE 94
useful infeasibilit y isolation. W eha v ealso comparedthisalgorithm withaheuristicproposed b y Chinnec k, and found that on man y problems solving optimally tak es lesstimethansolving heuristically Thisma ybedueinparttothedierences in implemen tation. Our algorithms solv e the alternativ e system of theoriginalinfeasiblesystem,whic hisessen tiallythedualofthatproblem. Chinnec k's method in v olv es solving man y Phase 1 instances of subproblems of the original infeasible system. Suc h factors as co v er size, size of individual IISs, and problem size probably con tribute to making the optimal co v ermoretractable. W e are also in terested in determining the utilit y of iden tifying IISsb ysearc hingforextremera ysofthealternativ esystemdirectly(either in the alternativ e system,or in the original infeasible system). This ma y helpspeedupthealgorithm asmallamoun t. Av ersionofourcodewhic h ndsamaximalsetofdisjoin tIISsbeforesolvingtheco v eringsubproblem alsolooksv erypromisingintermsofreducingthen um berofIISsnecessary to nd theoptimal co v er(and th us reducingtotal CPUtime). W ew ould also be in terestedin determining if inclusion offacets inamodiedbranc handcutalgorithmw ouldbebenecialtoreducingthe time neededin theco v ering subproblem. A tthe otherextreme,w ecould trytominimize theamoun toftimespen tontheco v eringsubproblem b y using a heuristic. 89
PAGE 95
BIBLIOGRAPHY [1] Amaldi E., F rom Finding Maxim um F easible Subsystems of Linear SystemstoF eedforw ardNeuralNet w orkDesign, Ph.D.Dissertation, EcoleP olytec hniqueF ed erale deLausanne, 1994. [2] Amaldi E., and Kann V., The Complexit y and Appro ximabilit y of FindingMaxim umF easibleSubsystemsofLinearRelations,toappear in The or etic alComputerScienc e .(AlsoappearingasT ec hnicalReport OR WP1193, Ecole P olytec hniqueF ed eraledeLausanne, 1993). [3] Amaldi E., and Kann V., On the Appro ximabilit y of Remo ving the Smallest Num ber of Relations from Linear Systems to Ac hiev eF easibilit y T ec hnicalReportOR WP694, EcoleP olytec hniqueF ed erale deLausanne, 1994. [4] BalasE.,andNgS.,OntheSetCo v eringP olytope: I.AlltheF acets with Coecien ts in f 0, 1, 2 g Mathematic al Pr o gr amming V ol. 43 (1989). [5] Bennett K.P ., and Mangasarian O.L., Robust Linear Programming DiscriminationofTw oLinearlyInseparableSets, OptimizationMetho dsand Softwar e ,V ol.1 (1992), pp.2334. [6] BergeC., Hyp er gr aphs ,NorthHolland, Amsterdam,1989. [7] Boneh A., Iden tication of Redundancy b y a Set Co v ering Equivalence, in Op er ational R ese ar ch 84 edited b y Brans J.P ., Elsevier Science Publishers B. V., Amsterdam, The Netherlands, 1984, pp. 407422. [8] Carv erW.B.,SystemsofLinearInequalities, A nnalsofMathematics V ol.23 (19211922), pp.212220. [9] Chakra v artiN.,SomeResultsConcerningP ostInfeasibilit yAnalysis, Eur op e an Journal of Op er ational R ese ar ch V ol. 73 (1994), pp. 139143.
PAGE 96
[10] Chinnec kJ.,FindingMinimalInfeasibleSetsofConstrain ts inInfeasible Mathematical Programs, T ec hnical Report SCE9301, Departmen t of Systems and Computer Engineering, Carleton Univ ersit y Otta w a,Canada, 1993. [11] Chinnec kJ.,FindingtheMostUsefulSubsetofConstrain tsforAnalysis in an Infeasible Linear Program, T ec hnical Report SCE9307, Departmen t of Systems and Computer Engineering, Carleton Univ ersit y ,Otta w a,Canada, 1993. [12] Chinnec k J.,An Eectiv eP olynomial Time Algorithm for the Minim umCardinalit y IIS Set Co v ering Problem, T ec hnical Report SCE9502, Departmen t of Systems and Computer Engineering, Carleton Univ ersit y ,Otta w a,Canada, 1995. [13] Chinnec k J., and Dra vnieks E., Locating Minimal Infeasible Constrain t Sets in Linear Programs, ORSA Journal on Computing V ol. 3(1991), pp.157168. [14] Ch v atalV.,AGreedyHeuristicfortheSetCo v eringProblem, Mathematics of Op er ations R ese ar ch ,V ol. 4(1979), pp.233235. [15] Debrosse C., and W esterberg A., A F easibleP oin t Algorithm for Structured Design Systems in Chemical Engineering, A meric an Institute of Chemic al Engine ers Journal ,V ol. 19 (1973), pp.251258. [16] Dy er,M., The Complexit y of V ertexEn umeration Methods, Mathematics of Op er ations R ese ar ch ,V ol.8 (1983), pp.381402. [17] F anK.,OnSystemsofLinearInequalities,in A nnalsofMathematic al Studies Numb er 38: Line ar Ine qualities and R elate d Systems edited b yKuhnH.W.andT uc k erA.W.,PrincetonUniv ersit yPress,Princeton,NJ,1956, pp.99156. [18] GaryM.,and Johnson D., Computers and Intr actability W.H.F reeman,NewY ork,1979. [19] GleesonJ.,andRy anJ.,Iden tifyingMinimallyInfeasibleSubsystems of Inequalities, ORSA Journal on Computing V ol. 2 (1990), pp. 6163. [20] Glo v er F., Impro v ed Linear and In teger Programming Models for Discriminan t Analysis, in Cr e ative and Innovative Appr o achesto the 91
PAGE 97
Scienc eofManagement ,editedb yIjiriY.,QuorumBooks,W estport, CT,1993. [21] Green bergH.J.,Consistency ,Redundancy ,andImpliedEqualities in Linear Systems, UCD/CCM Report No. 14, Mathematics Departmen t,Univ ersit yof Colorado at Den v er,1993. [22] Green berg H.J., Diagnosing Infeasibilit y in Mincost Net w ork Flo w Problems P art II:Primal Infeasibilit y IMA Journal of Mathematics Applie d in Business and Industry ,V ol.2(1988/9), pp.3950. [23] Green berg H.J., Diagnosing Infeasibilit y in Mincost Net w ork Flo w Problems P art I:Dual Infeasibilit y IMA Journal of Mathematics in Management V ol.1 (1987), pp.99109. [24] Green berg H.J.,An Empirical Analysis of Infeasibilit y Diagnosis for Instances of Linear Programming Blending Models, IMA Journal of Mathematics Applie d in Business and Industry V ol. 4 (1992), pp. 163210. [25] Green bergH.J.,Ho wtoAnalyzetheResultsofLinearProgramsP art 3: Infeasibilit y Diagnosis, Interfac es ,V ol. 23,No.6 (1993). [26] Green bergH.J.,and Murph yF.H.,Approac hesto Diagnosing Infeasibile Linear Programs, ORSA Journal on Computing V ol. 3, No. 3 (1991), pp.253261. [27] Motzkin T.S., Con tributions to the Theory of Linear Inequalities, Doctoral Dissertation, Univ ersit y of Basel, 1933, translated b y D.R. F ulk erson,in The o dor eS.Motzkin: Sele cte dPap ers ,editedb yCan tor D.,Gordon B.,and Rothsc hild B.,Birkhauser,1983. [28] Murt yK., Line ar Pr o gr amming ,John Wiley and Sons, 1983. [29] NemhauserG.,andW olsey L., Inte ger and Combinatorial Optimization ,John Wiley and Sons,1988. [30] Pulleyblank W.,P ersonal Comm unication to J.Ry an. [31] Roodman G., P ostInfeasibilit y Analysis in Linear Programming, Management Scienc e V ol. 25 (1979), pp.916922. [32] Ry anJ.,T ransv ersalsofIISHypergraphs, Congr essusNumer antium V ol.81 (1991), pp.1722. 92
PAGE 98
[33] Ry anJ.,IIS{Hypergraphs, preprin t,1993. [34] Sank aran J.K., A Note on Resolving Infeasiblit y in Linear Programs b y Constrain t Relaxation, Op er ations R ese ar ch L etters V ol. 13 (1993), pp.1920. [35] Sc hrijv er,A., The oryofLine arandInte gerPr o gr amming ,JohnWiley and Sons,1986. [36] V anLoon J.,IrreduciblyInconsisten tSystemsofLinear Inequalities, Eur op e anJournalofOp er ationsR ese ar ch ,V ol.8(1981),pp.283288. 93

