Sponsor:

Your company here — click to reach over 10,000 unique daily visitors

fel - Man Page

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
    https://inf.ethz.ch/personal/fukudak/polyfaq/polyfaq.html
  2. User's guide for lrslib
    http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html

Author

David Avis <avis at cs dot mcgill dot ca >

See also

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

Referenced By

lrs(1), lrslib(5), lrsscripts(5).

2024.1.10 January 2024 lrslib 7.3