fel(1)

  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),