Man page - fel(1)

Packages contains this manual

Package: lrslib
apt-get install lrslib

Manuals in package:

Documentations in package:

lrslib

Manual

fel

Name
Synopsis
Description
Options
Example
Notes
Author
See also

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.

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

FAQ page

https://inf.ethz.ch/personal/fukudak/polyfaq/polyfaq.html

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 >