disjointlp computes k vertex disjoint monotone paths from source to sink of a linear program. A complete description is available here:  AK2005_preprint.ps. As input, the program requires a linear program whose inequalities define a full-dimensional bounded d-polytope. The user also specifies an integer k, the number of disjoint paths to compute. The program outputs k vertex-disjoint LP paths from source to sink of the input linear program. The source vertex is the vertex that minimizes the objective function, and the sink vertex maximizes the linear program. Vertices are represented by their lex-min basis, namely by the indices of the cobasic variables that define the lex-min basis of a vertex. A cobasis {1,5,7,9} represents the vertex that lies at the intersection of the (facet-defining) inequalities 1,5,7 and 9 of the input.

disjointlp is an extension of  lrs. lrs is based on the reverse search algorithm of Avis and Fukuda(1992) , modified to use lexicographic pivoting  and implemented in rational arithmetic. See Avis(1998a) for a technical description, and Avis(1998b) for some computational experience. The input files are in Polyhedra format , developed by Avis and Fukuda.  All functions of lrs are available with the disjoinlp package, however the author of disjointlp, Bohdan Kaluzny, takes full responsibility for all functionality of any routines executed by code of the disjoinlp package.

The input inequalities need to define a polytope that is full dimensional.  disjointlp accepts either integer or rational input, and produces integer or rational output. All computations are done exactly using either extended precision arithmetic or fixed long integer arithmetic. In the latter case no overflow checking is performed, and the user is advised to check results using the extended precision version. Since it is a pivot based method, disjointlp can be very slow for degenerate inputs. A discussion of various vertex enumeration/convex hull methods and the types of polyhedra that cause them to behave badly is contained in Avis, Bremner and Seidel (1997).

Download 

---

Installation 

• Unpack with:
     % gunzip disjointlp.tar.gz
     % tar xvf disjointlp.tar
• Go to the new directory
  % cd lrslib-041
   
•  make binaries lrs and redund  by typing
     % make all               (most 32 bit unix machines)
   
• If you have GNU MP installed you can obtain binaries glrs and gredund using this library by typing
    % make gmp
  It may be necessary to edit makefile to set the paths to the gmp library
   
   
• Test the program by typing:
  lrs  test.ine
  This will convert the H-representation of a cube given cube by 6 the six inequalities -1 <= x_i <= 1 , i=1,2,3 given by the input:
  H-representation
  begin
  6 4 rational
  2 2 -2 -1
  3 0 -1 -1
  9 -2 -1 -3
  2 -1 2 -3/2
  -4 2 4 -1
  0 0 0 1
  end
  disjoint 3
  maximize 0 -1 0 0
  printpaths
   

  The output should contain (along with other comment lines)

*Input taken from file test.ine
H-representation
*Computing 3 Disjoint Paths
*maximize 0 -1 0 0

------------------------------------------------------
Computing Path #1
Computing Path #2
Computing Path #3

Disjoint Paths Computed:
Path 1: [3 4 6 ]-->[4 5 6 ]-->[1 5 6 ]
Path 2: [3 4 6 ]-->[3 4 5 ]-->[1 5 6 ]
Path 3: [3 4 6 ]-->[2 3 6 ]-->[1 2 6 ]-->[1 5 6 ]

Disjoint path statistics:
Longest path length = 4
Shortest path length = 3
# of path vertices = 6


------------------------------------------------------
 

Example files can be found in the directory ine that comes in the standard distribution. File formats were developed by David Avis and Komei Fukuda and are compatible with cdd and lrs .

The input for disjointlp is a H-representation of a polytope, an objective function, and the number of disjoint paths to compute . This file has the following format:

---


name
H-representation
begin
n m rational

{list of inequalities }

end
disjoint k    /* OR  dd_disjoint k to break dual degeneracy */
maximize c₀ c₁ ... c_d-1

{options}

---


name is a user supplied name for the polytope.  The input coefficients are read in free format, and are not checked for type. Coefficients are separated by white space. Normally this file would be saved with filename suffix .ine but this not required.  Comments may appear before the begin or after the end, and to avoid interpretation as an option, should begin with a special character such as "*" or "#".
The integer  n is the number of inequalities,  and the integer m is the dimension of the input +1 = d+1.
A list of inequalities contains the coefficients of inequalities of the form

a₀ + a₁ x₁ + ... + a_d-1 x_d-1 >=  0.

This inequality is input as the line

a₀ a₁ ... a_d-1
 

The coefficients can be entered as integers or rationals in the format x/y.
For example, the square centered at the origin with side length two has inequalities

1 + x₁ >= 0      1+ x₂ >=0         1-x ₁ >= 0           1-x₂ >=0

and would be represented by the input file

square
*centred square of side 2
H-representation
begin
4 3 rational
1 1 0
1 0 1
1 -1 0
1 0 -1
end
 

Options

disjointlp is implemented within lrs which has many options to allow various functions to be performed. Almost all options are placed after the end statement. We mention a few options that may prove useful fro disjointlp.

debug  0 0

Print out cryptic but detailed trace, dictionaries etc.

printpaths

Print out each path as the sequence of lex-max cobases uniquely representing vertices

n is the maximum number of decimal digits to be used. If this is exceeded the program terminates with a message (it can  usually be restarted).   The default is set to about 100 digits. At the end of a run a message is given informing the user of the maximum integer size encountered. This may be used to optimize memory usage and speed on subsequent runs (if doing estimation for example). The output:
*Max digits= 45/100
indicates that the maximum integer encountered had 45 decimal digits, and the program allowed up to 100 digit integers.

Arithmetic Packages                      (provided by lrs Version 4.0)

   lrsmp     Extended precision arithmetic used in previous releases

   lrslong   Fixed length long integer arithmetic. No overflow checking
                    but 5-10 times faster than lrsmp.

   lrsgmp   An interface to GNU MP  which must be installed first.
                    Runs 1-6 times faster than lrsmp on typical problems.

  The standard make gives binaries  lrs/redund with lrsmp, and lrs1/redund1 with lrslong. The fixed integer package is particularly useful with 64 bit machines, and fairly large combinatorial problems (15-20 dimensions) have been correctly solved. It may be useful for doing empirical work, eg. searching for polyhedra with certain properties. Final results should always be checked using lrsmp. If you have GNU MP installed, "make gmp" will produce binaries glrs/gredund using this library. It may be necessary to edit the makefile to specify the path to gmp.
 

Error Messages and Troubleshooting

lrs does not handle floating point data, change to integer or rational input.

The digits option was specified, but the number of  decimal digits is too large (the values shown here is for 64 bit machines). MAX_DIGITS  (default 255) is the maximum number of array locations used for extended precision arithmetic. This value should be increased  and lrs recompiled.

Input file does not contain a begin line.

The input file is incorrect, please check

The input is an H-representation of an infeasible system.

The input is an H-representation of an unbounded system. disjointlp requires a bounded full-dimensional polytope as input.

Redundancy vs Degeneracy

Even with redundant input removed a polyhedron may be highly degenerate. In directory ine/metric there are many highly degenerate combinatorial polytopes. These are difficult problems for all vertex enumeration/convex hull programs that use pivoting, such as lrs.  For example, the file ccc7.ine is a cone with 63 facets in 21 dimensions. It has 38,780 extreme rays, but computing these required the evaluation of 247,271,659 bases!

Dual Degeneracy

The input linear program is dual degenerate if adjacent vertices have the same objective value. disjointlp can break dual degeneracy by ordering these vertices lexicographically with respect to the lex-min bases that represent the vertices. To break dual degeneracy specify the dd_disjoint option.

Memory considerations

I would like to thank David Avis for helping with this implementation project, as disjointlp would not be possible without the existence of lrs.  That being said, only am I to be held fully responsible for any bugs or errors that may occur when running the code!

D. Avis, B. Kaluzny, Computing Disjoint Paths in Linear Programs, AK2005_preprint.ps GERAD Technical Report G-2005-26, March 2005.

D. Avis, lrs: A Revised Implementation of the Reverse Search Vertex Enumeration Algorithm, http://cgm.cs.mcgill.ca/~avis/doc/avis/Av98a.ps May 1998.

D. Avis, "Computational Experience with the Reverse Search Vertex Enumeration Algorithm," Optimization Methods and Software, (1998 (to appear)). http://cgm.cs.mcgill.ca/~avis/doc/avis/Av98b.ps

D. Avis, D. Bremner, and R. Seidel, "How Good are Convex Hull Algorithms?," Computational Geometry: Theory and Applications, Vol 7,pp.265-301(1997). http://cgm.cs.mcgill.ca/~avis/doc/avis/ABS96a.ps

D. Avis and K. Fukuda, "A Pivoting Algorithm for Convex Hulls and Vertex Enumeration of Arrangements and Polyhedra," Discrete and Computational Geometry, Vol. 8, pp. 295-313 (1992).  http://cgm.cs.mcgill.ca/~avis/doc/avis/AF92b.ps

L. Ford and D. Fulkerson, Maximal flow through a network, Canad. J. Math. 8 (1956), 1142-1146.

F. Holt and V. Klee, A Proof of the Strict Monotone 4-step Conjecture, Contemporary Mathematics 223 (1999) 201--216.

G. Adelson-Velskii and E. Landis, An Algorithm for the Organization of Information, Doklady Akademii Nauk SSSR, 146:263-266, 1962 (Russian).