Sponsor:

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

mplrs - Man Page

Name

mplrs - Convert between representations of convex polyhedra, remove redundant inequalities, do Fourier-Motzkin elimination (parallel version).

Synopsis

mpirun -np num_proc mplrs infile [outfile] [option...]

Description

A polyhedron can be described by a list of inequalities (H-representation) or by a list of its vertices and extreme rays (V-representation). mplrs is a parallel version of lrs, and converts an H-representation of a polyhedron to its V-representation, and vice versa.  These problems are known respectively as the vertex enumeration and convex hull problems. With lrs options redund or redund_list in the input file it  will do parallel execution of minrep (computing a minimum representation), see redund(1). With lrs options project or eliminate in the input file it will do parallel execution of fel (Fourier-Motkin elimination).

Usage

The number of processors num_proc specified to mpirun should be 4 or higher. Some lrs input file options are not supported by  mplrs.

Options

mplrs supports the following options, where default values are given in brackets.

-checkp <checkpoint file> if mplrs is terminated by -stop or -time then it can be restarted using this <checkpoint file> and -restart
-countonly don't output vertices/rays/facets, just count them
-freq <file> store frequency data in <file> for use by gnuplot, see below
-hist <file>store parallelization data in <file> for use by gnuplot, see below
-id <initial depth> [2] the depth of the original tree search to populate the job list L
-lmax <int>[lmin] if job list |L|>np*lmax then then maxc is replaced by maxc*scale
-lmin <int>[3] if job list |L|<np*lmin then the maxd parameter is set for all producers
-maxbuf <n>[500] controls maximum size of worker output buffers
-maxc <maxcobases>[50 (*scale)] a producer stops and returns all subtrees that are not leaves to L after generating  maxc nodes   
-maxd <depth>[0] a producer returns all subtrees that are not leaves at depth maxd. Zero if not used
-minheight jobs are scheduled in increasing order by height in the search tree (default is LIFO)
-queue jobs are scheduled in FIFO order (default is LIFO)
-restart <checkpoint file> restart mplrs using previously created <checkpoint file>. If used with -checkp file names should be different!
-scale <int>[100] used by lmax
-stop <stopfile> terminate mplrs if a file with name <stopfile> is created in the current directory
-stopafter <n> exit after approximately <n> cobases have been computed (no guarantee about how many vertices/rays/facets computed)
-temp <prefix>[/tmp/] store a temporary file for each process. Should be specified if /tmp not writeable. Using " -temp  ./ " will write temporary files to the current directory
-time <seconds> terminate mplrs after <seconds> of elapsed time

redund/fel options

-j <int>[1] if non-zero splits the run into <int> jobs per worker, over-riding rows and lastrows
-lastp <int>[10] the percentage of jobs to use lastrows
-lastrows <int>[10] the number of rows for the last lastp jobs
-minrep removes redundant inequalities, finds hidden linearities and outputs a minimum representation of the input file. This ignores any project or eliminate option present in the input file
-rows <int>[60] the number of rows per job

-hist file format

Example line:

  54.118141 94 279 94 0 0 373

  time since execution began in seconds (54.118141 here)
  number of busy workers (94 here)
  current size of job list (279 here)
  number of workers that may return unfinished jobs (94 here)
  unused (0 here)
  unused (0 here)
  total number of jobs that have been in the job list (373 here)

The second and fourth entries are similar and can differ due to latencies.

-freq file format

One integer per line corresponding to the size of a subtree explored by a worker.

Example

Input file mp5.ine is run with 8 processors.  This produced 378 subtrees that were enumerated in parallel using 6 producer cores,  1 core controlling the run and 1 core collecting the output.

      mai20% mpirun -np 8 mplrs mp5.ine mp5.mplrs
      *mplrs:lrslib v.6.0 2015.7.13(lrsgmp.h)8 processes
      *Copyright (C) 1995,2015, David Avis   avis@cs.mcgill.ca
      *Input taken from mp5.ine
      *Output written to: mp5.mplrs
      *Starting depth of 2 maxcobases=50 maxdepth=0 lmin=3 lmax=3 scale=100
      *Phase 1 time: 0 seconds.
      *Total number of jobs: 378, L became empty 4 times
      *Totals: vertices=32 rays=0 bases=9041 integer-vertices=16
      *Elapsed time: 1 seconds.
      2.285u 0.137s 0:01.86 129.5%    0+0k 0+9976io 36pf+0w

Author

Charles Jordan <skip at res dot otaru-uc dot ac dot jp >

See also

lrs(1), lrslib(5)

Referenced By

fel(1), lrs(1), lrslib(5), lrsscripts(5), redund(1), xref(1).

2024.2.5 February 2024 mplrs 7.3