Generation of extreme points of P(B)

GenExPo: Generation of extreme points of P(B)

by A. Galluccio, C. Gentile, P. Ventura (2007).

Here we describe the procedure used to generate the extreme points (β_B, y) of the polytope P(B), that are associated with inequalities (β_V\B, β_B, β₀). As all the considered inequalities have full support on V_B, all their possible roots must be maximal in V_B. In this figure we show the 24 possible configurations for maximal solutions in V_B. Each configuration R_i produces a linear system of inequalities L_i on β_B by simply considering the maximality conditions.

L₁:

β_c + β_a ≤ β_h₁

β_b₁ + β_h₂ ≤ β_h₁

β_d₁ + β_h₂ ≤ β_h₁

β_b₁ + β_a ≤ β_h₁

β_d₁ + β_c ≤ β_h₁

L₂:

β_c + β_a ≤ β_h₁

β_h₂ ≤ β_h₁

L₃:

β_c + β_a ≤ β_h₂

β_b₂ + β_h₁ ≤ β_h₂

β_d₂ + β_h₁ ≤ β_h₂

β_b₂ + β_a ≤ β_h₂

β_d₂ + β_c ≤ β_h₂

L₄:

β_c + β_a ≤ β_h₂

β_h₁ ≤ β_h₂

L₅:

β_d₁ + β_d₂ ≤ β_a

β_b₁ + β_b₂ ≤ β_c

β_b₂ + β_h₁ ≤ β_a + β_c

β_d₂ + β_h₁ ≤ β_a + β_c

β_d₁ + β_h₂ ≤ β_a+ β_c

β_b₁ + β_h₂ ≤ β_a+ β_c

β_b₁ + β_d₂ ≤ β_a+ β_c

β_d₁ + β_b₂ ≤ β_a+ β_c

L₆:

β_d₂ ≤ β_a

β_b₂ ≤ β_c

β_h₁ + β_b₂ ≤ β_a+ β_c

β_h₁ + β_d₂ ≤ β_a + β_c

β_h₂ ≤ β_a + β_c

L₇:

β_d₁ ≤ β_a

β_b₁ ≤ β_c

β_h₂ + β_d₁ ≤ β_a+ β_c

β_h₂ + β_b₁ ≤ β_a + β_c

β_h₁ ≤ β_a + β_c

L₈:

β_h₁ ≤ β_a+ β_c

β_h₂ ≤ β_a + β_c

L₉:

β_d₂ ≤ β_b₂

β_d₁ ≤ β_h₁

β_a + β_b₁ ≤ β_h₁

β_a + β_c ≤ β_h₁ + β_b₂

β_d₁ + β_h₂ ≤ β_h₁ + β_b₂

β_b₁ + β_h₂ ≤ β_h₁ + β_b₂

β_b₁ + β_d₂ ≤ β_h₁ + β_b₂

β_c + β_d₁ + β_d₂ ≤ β_h₁ + β_b₂

L₁₀:

β_d₂ ≤ β_b₂

β_a ≤ β_h₁

β_a + β_c ≤ β_h₁ + β_b₂

β_c + β_d₂ ≤ β_h₁ + β_b₂

β_h₂ ≤ β_h₁ + β_b₂

L₁₁:

β_b₂ ≤ β_d₂

β_b₁ ≤ β_h₁

β_c + β_d₁ ≤ β_h₁

β_a + β_c ≤ β_h₁ + β_d₂

β_b₁ + β_h₂ ≤ β_h₁ + β_d₂

β_d₁ + β_h₂ ≤ β_h₁ + β_d₂

β_d₁ + β_b₂ ≤ β_h₁ + β_d₂

β_a + β_b₁ + β_b₂ ≤ β_h₁ + β_d₂

L₁₂:

β_b₂ ≤ β_d₂

β_c ≤ β_h₁

β_a + β_c ≤ β_h₁ + β_d₂

β_a + β_b₂ ≤ β_h₁ + β_d₂

β_h₂ ≤ β_h₁ + β_d₂

L₁₃:

β_b₁ ≤ β_d₁

β_b₂ ≤ β_h₂

β_c + β_d₂ ≤ β_h₂

β_a + β_c ≤ β_h₂ + β_d₁

β_b₂ + β_h₁ ≤ β_h₂ + β_d₁

β_d₂ + β_h₁ ≤ β_h₂ + β_d₁

β_d₂ + β_b₁ ≤ β_h₂ + β_d₁

β_a + β_b₁ + β_b₂ ≤ β_h₂ + β_d₁

L₁₄:

β_b₁ ≤ β_d₁

β_c ≤ β_h₂

β_a + β_c ≤ β_h₂ + β_d₁

β_a + β_b₁ ≤ β_h₂ + β_d₁

β_h₁ ≤ β_h₂ + β_d₁

L₁₅:

β_d₁ ≤ β_b₁

β_d₂ ≤ β_h₂

β_a + β_b₂ ≤ β_h₂

β_a + β_c ≤ β_h₂ + β_b₁

β_d₂ + β_h₁ ≤ β_h₂ + β_b₁

β_b₂ + β_h₁ ≤ β_h₂ + β_b₁

β_b₂ + β_d₁ ≤ β_h₂ + β_b₁

β_c + β_d₁ + β_d₂ ≤ β_h₂ + β_b₁

L₁₆:

β_d₁ ≤ β_b₁

β_a ≤ β_h₂

β_a + β_c ≤ β_h₂ + β_b₁

β_c + β_d₁ ≤ β_h₂ + β_b₁

β_h₁ ≤ β_h₂ + β_b₁

L₁₇:

β_h₂ ≤ β_a

β_c ≤ β_b₁

β_d₁ + β_c ≤ β_b₁ + β_a

β_d₁ + β_h₂ ≤ β_b₁ + β_a

β_h₁ ≤ β_b₁ + β_a

L₁₈:

β_h₂ ≤ β_c

β_a ≤ β_d₁

β_b₁ + β_a ≤ β_d₁ + β_c

β_b₁ + β_h₂ ≤ β_d₁ + β_c

β_h₁ ≤ β_d₁ + β_c

L₁₉:

β_h₁ ≤ β_c

β_a ≤ β_d₂

β_b₂ + β_a ≤ β_d₂ + β_c

β_b₂ + β_h₁ ≤ β_d₂ + β_c

β_h₂ ≤ β_d₂ + β_c

L₂₀:

β_h₁ ≤ β_a

β_c ≤ β_b₂

β_d₂ + β_c ≤ β_b₂ + β_a

β_d₂ + β_h₁ ≤ β_b₂ + β_a

β_h₂ ≤ β_b₂ + β_a

L₂₁:

β_d₁ + β_c ≤ β_b₁

β_h₁ ≤ β_b₁

β_h₂ ≤ β_d₂

β_b₂ + β_a ≤ β_d₂

β_d₁ + β_b₂ ≤ β_d₂ + β_b₁

β_d₁ + β_h₂ ≤ β_d₂ + β_b₁

β_h₁ + β_b₂ ≤ β_d₂ + β_b₁

β_a + β_c ≤ β_d₂ + β_b₁

L₂₂:

β_d₂ + β_c ≤ β_b₂

β_h₂ ≤ β_b₂

β_h₁ ≤ β_d₁

β_b₁ + β_a ≤ β_d₁

β_d₂ + β_b₁ ≤ β_d₁ + β_b₂

β_d₂ + β_h₁ ≤ β_d₁ + β_b₂

β_h₂ + β_b₁ ≤ β_d₁ + β_b₂

β_a + β_c ≤ β_d₁ + β_b₂

L₂₃:

β_a ≤ β_d₁+ β_d₂

β_b₂ ≤ β_c + β_d₂

β_h₂ ≤ β_c + β_d₂

β_b₁ ≤ β_c + β_d₁

β_h₁ ≤ β_c + β_d₁

β_a + β_b₁ + β_b₂ ≤ β_c + β_d₁ + β_d₂

β_b₁ + β_h₂ ≤ β_c + β_d₁ + β_d₂

β_h₁ + β_b₂ ≤ β_c + β_d₁ + β_d₂

L₂₄:

β_c ≤ β_b₁+ β_b₂

β_d₂ ≤ β_a + β_b₂

β_h₂ ≤ β_a + β_b₂

β_d₁ ≤ β_a + β_b₁

β_h₁ ≤ β_a + β_b₁

β_c + β_d₁ + β_d₂ ≤ β_a + β_b₁ + β_b₂

β_d₁ + β_h₂ ≤ β_a + β_b₁ + β_b₂

β_h₁ + β_d₂ ≤ β_a + β_b₁ + β_b₂

Each system L_i describes a cone, in fact the solution represents the coefficients β_B of an inequality (β_V\B, β_B, β₀), and any multiplication by a scalar yields an equivalent inequality. We add the following normalization condition:

β_u ≤ 1 for each u є V_B.

An inequality (β,β₀) is facet defining if and only if it is satisfied as an equality by |V_G| affinely independent points. Therefore, we introduce a variable y_i є {0,1} for i = 1,...,24 such that y_i = 1 if and only if a solution corresponding to configuration R_i is selected among the |V_G| affinely independent solutions. If y_i = 1, then β_B must satisfy the system L_i, otherwise the system L_i may be violated. Let A_i β_B ≤ 0 be the system L_i, then we introduce a big-M representation of the above condition: A_i β_B ≤ M_i (1 - y_i), where M_i is a vector and (M_i)_j is equal to the number of variables in the j-th inequality of system L_i having positive coefficients in (A_i)_j.
As we know that G contains a gear, we can relax the condition that there exist |V_G| affinely independent solutions for (β,β₀) with the conditions (i)-(iv) described in Section 3.2 of the paper. So, we define the set Y of points y satisfying the following linear constraints:

Σ	y_i ≥ 1
i : u є R_i

for all u є V_B

Σ	y_i ≥ 1
i : R_i ∩ K=Ø

for all K clique of V_B^*

Σ	y_i ≥ 1
i : h_j ∉ R_i and
\| R_i ∩ C_j \|<2

for each W_j=(h_j : C_j), j=1,2

Σ	y_i ≥ 10
i = 1,...,24

The linear mixed integer formulation of P(B) is thus the following:

A_i β_B ≤ M_i ( 1 - y_i ) i = 1,...,24

β_B ≤ 1

y є Y

(1)

The system of inequalities (1) has been given in input to the code PORTA. This software is able to find the extreme points of the polyhedron described by a system of linear inequalities. As the variables y_i are constrained to be 0-1, all the mixed-integer feasible solutions of (1) are extreme points of the associated polyhedron. Since PORTA takes too long to find the extreme points of (1), we subdivided the problem in 2¹⁶ subproblems by fixing y_i to zero or to one for i = 9,...,24, and then we considered the union of the resulting solutions. As a final step, we eliminate all the points with fractional value of the variables y_i for i = 1,...,8 or such that rank(x^R_i | y_i=1) < 10. This check has been made with the free software Octave. The resulting list of points are the extreme points of P(B).

Here we give the detailed instructions to repeat the proof of the theorems 7 and 8:

Install PORTA FORTE on your computer.
Create folder ``Proof´´
Download in folder ``Proof´´ the file proof.c and the file cleanfrac.c
Compile proof.c and cleanfrac.c with default options creating executables ``proof´´ and ``cleanfrac´´, respectively.
Run ``proof <PORTA FORTE folder> ´´ specifying the folder where you installed PORTA FORTE. This code perform the following actions:
1. creates subfolders ``in´´, ``ieq´´, ``inf´´, ``out´´, ``poi´´;
2. writes in subfolder ``ieq´´ the 2¹⁶ systems of linear inequalities obtained from system (1) by fixing the variables y_i for i = 9,...24 to zero or to one; these systems are written in format ``.ieq´´ for PORTA FORTE; in the case the resulting system is infeasible the associated file .ieq is moved to the subfolder ``inf´´; the name of the files .ieq is proof_<number>.ieq, where <number> is the decimal representation of the assignment given to variables y_i for i = 9,...,24;
3. writes in subfolder ``in´´ the command files in_<number> to execute PORTA FORTE on the corresponding feasible system in file proof_<number>.ieq;
4. executes PORTA FORTE for all the feasible proof_<number>.ieq files producing files proof_<number>.poi in subfolder ``poi´´;
5. writes in subfolder ``out´´ the output of each execution of PORTA FORTE (out_<number>).
Run ``cleanfrac´´. This code reads each file proof_<number>.poi and performs the following operations:
1. reads each point (β_B, y_{1,...,8}) in the file;
2. checks if y_i є {0,1} for i = 1,...,8;
3. if yes, then
  - writes the point in a new file cleanfrac.poi;
  - if β_B is full support, writes ``full support´´ at the end of the line in cleanfrac.poi;
  - verifies if this y_{1,...,8} was equal to a previous written point, and if yes, it checks if rank(x^R_i | y_i = 1, i = 1,...,24) = 10 using Octave; if the check is passed, a ``warning´´ is written in file cleanfrac.poi, indicating the index of the row with the same value for y;
4. the results of Theorem 3 are then indicated by rows of cleanfrac.poi labelled ``full support´´;
5. the results of Theorem 4 are then indicated by rows of cleanfrac.poi labelled ``warning´´.