This is an example for the occurrence of generalized antiweb facets.

We give a very short overview of the terms necessary to understand the examples. For details see the references.

Given an infeasible inequality system S: Ax <= b, consider the
*feasible subsystems polytope* P_{FS}, which is the
convex hull of the incidence vectors of all feasible subsystems. An
*irreducible inconsistent subsystem* (IIS) of this infeasible
system is a subsystem, such that each proper subsystem of it is
feasible. Clearly, the feasible subsystems of S form an independence
system. The IISs are the circuits of this independence system.

Laurent [2] introduced generalized antiwebs and investigated under which circumstances facets of the corresponding independence system polytope arise from these structures.

Let m, t, q be integers such that 1 <= q <= t <= m, let
E={0, ... , m-1} be a finite set, and define for each i in M:={0,
... , m-1} the subset E_{i}={i, ..., i+t-1} (calculated modulo
m), formed by t consecutive elements of E. A (m,t,q)-*generalized
antiweb* on E is the independence system having the following
family of subsets of E as circuits:

AW(m,t,q) = {C : C is a subset of E_{i}for some i in M, |C| = q}.

Amaldi, Pfetsch, Trotter [1] investigate for which parameters m,t,q the independence system arising from AW(m,t,q) is the independence system of feasible subsystems of an infeasible linear inequality system Ax <= b. Furthermore the cases where facets arise from generalized antiwebs as induced substructures are discussed. The following propositions are obtained:

Proposition:The sets in AW(m,t,q) correspond to the IISs of an infeasible linear inequality system Ax <= b with m inequalities if and only if

- t=q and

- t = m-2 or
- t = m

Proposition:Let S: Ax <= b be an infeasible linear inequality system with m inequalities. Let AW(m,t,q) correspond to the IISs of S. The inequality x_{1}+x_{2}+ ... +x_{m}<= floor(m(q-1)/t) defines a facet for P_{FS}if and only if

- t=q and

- t=m or
- t = m-2 and t not equal to 2.

The example aw.4.2 is the case m=4, t=q=2. The infeasible inequality
system in file `aw.4.2.lp`

(in lp-format) has AW(4,2,2) as
IISs. The file `aw.4.2.eps`

contains a picture in postscript. The
corresponding polytope P_{FS} is contained in the file
`aw.4.2.poly`

(in polymake-format), including the list of
facets. You can see that no facet like above arises.

The example
aw.5.2 is the case m=5, t=q=3. Again the example in file
`aw.5.3.lp`

has AW(5,3,3) as its IISs and a picture is given in
`aw.5.3.eps`

. The IISs are given in different colors. The colored
triangles mark the triangles involved in each IIS. The file
`aw.5.3.poly`

gives P_{FS} and its facets.

Model produced with: Polymake 1.4

Keywords
| feasible subsystems; circuits; facets; generalized antiwebs | |

MSC-2000 Classification
| 90C57 (52B11) | |

Zentralblatt No.
| 01682990 |

- Edoardo Amaldi, Marc E. Pfetsch, Leslie E. Trotter, Jr.:
*On the Maximum Feasible Subsystem Problem, IISs and IIS-hypergraphs*, preprint. - Monique Laurent:
*A generalization of antiwebs to independence systems and their canonical facets*, Math. Prog.**45**(1989), 97 -- 108.

- Master File: aw.4.2.poly
- Master File: aw.5.3.poly
- Preview: aw.4.2.gif
- Preview: aw.5.3.gif
- Other: aw.4.2.lp
- Other: aw.5.3.lp
- Other: aw.4.2.eps
- Other: aw.5.3.eps

Submitted: Sun Sep 10 07:10:24 CET 2000.

Accepted: Mon Nov 20 17:06:57 CET 2000.

Technische Universität Berlin

Fachbereich Mathematik, MA 7-1

Straße des 17. Juni 136

10623 Berlin, Germany

pfetsch@math.tu-berlin.de

http://www.math.tu-berlin.de/~pfetsch