Name¶

fel - Project an H-representation or V-representation onto a subset of columns.

Synopsis¶

fel [input-file] [output-file]

mpirun -np [procs] mplrs -fel [input-file] [output-file] [option...]

Description¶

fel is an alias of lrs which can also perform these functions via the eliminate and project options.

H-representation.
The input is projected onto a given set of columns using Fourier-Motzkin elimination. An H-representation is output after each iteration. mplrs -fel is a fully parallel version that performs one iteration only, see mplrs(1).
V-representation.
The specified columns are extracted and redundant rows are removed. The output can be can be piped directly into lrs. Not implemented in mplrs.

Options¶

These options are placed after the end statement.

eliminate k i_1 i_2 ... i_k (new in v7.2)
(H-representation) Eliminates k variables in an H-representation corresponding to cols i_1 .. i_k by projection onto the remaining variables using the Fourier-Motzkin method. Variables are eliminated in the order given and redundancy is removed after each iteration.
(V-representation) Delete the k given columns from the input matrix and remove redundancies (cf. extract where redundancies are not removed).
Column indices are between 1 and n-1 and column zero cannot be eliminated. The output is a valid lrs input file.

project k i_1 i_2 ... i_k (new in v7.2)
(H-representation) Project the polyhedron onto the k variables corresponding to cols i_1 .. i_k using the Fourier-Motzkin method. Column indices are between 1 and n-1 and column zero is automatically retained. Variables not contained in the list are eliminated using a heuristic which chooses the column which minimizes the product of the number of positive and negative entries. Redundancy is removed after each iteration using linear programming.
(V-representation) Extract the k given columns from the input matrix and remove redundancies. Column indices are between 1 and n-1 and column zero is automatically extracted (cf. extract where redundancies are not removed).
The output as a valid lrs input file.

See also extract in lrs(1).

verbose

For an H-representation give, for each iteration, statistics on how many new inequaties were created and how many of these were redundant. See Example below.

Example¶

(1) Project onto columns 1 and 3 in an H-representation

% cat cube.ine
cube.ine
H-representation
begin
6 4 rational
1 1 0 0
1 0 1 0
1 0 0 1
1 -1 0 0
1 0 0 -1
1 0 -1 0
end
project 2 1 3
verbose

% fel cube.ine
fel:lrslib_v.7.3_2024.1.10(64bit,lrslong.h,hybrid_arithmetic)
*Input taken from cube.ine
cube

*switching to fel mode
*project 2 1 3
*after removing column 2
*checking for redundant rows only
H-representation
begin
4 3 rational
0 1 0
1 -1 0
1 0 -1
-1 0 1
end
*number of number after number of remaining column
*inequalties removing col redundancies rows removed
* 7 6 2 4 2
--------------------------------------------------------------------

*original vars remaining: 1 3

(2) Eliminate columns 1,2,3 from a V-representation

% cat cp4.ext
V-representation
begin
8 7 rational
1 0 0 0 0 0 0
1 0 1 1 1 1 0
1 1 1 0 0 1 1
1 1 0 0 1 1 0
1 0 0 1 0 1 1
1 1 1 1 0 0 0
1 0 1 0 1 0 1
1 1 0 1 1 0 1
end
eliminate 3 1 2 3

% lrs cp4.ext
lrs:lrslib_v.7.3_2024.1.12(64bit,lrslong.h,hybrid_arithmetic)
*Input taken from cp4.ext
cp4

*switching to fel mode
*eliminate 3 1 2 3
*checking for redundant rows only
V-representation
begin
4 4 rational
1 1 1 0
1 0 1 1
1 0 0 0
1 1 0 1
end
*columns retained: 0 4 5 6

Notes¶

1.

FAQ page

2.

User's guide for lrslib

Author¶

David Avis <avis at cs dot mcgill dot ca >

See also¶

lrs(1), mplrs(1), lrslib(5),