inner - a MultiObjective Linear Program (MOLP) solver

A MOLP is a linear program with more than one objective functions. The linear constraints are arranged in a matrix form with c columns and r rows. Columns correspond to variables x₁, x₂, . . . , x_c, which are subject to the restrictions

Li ≤ xi ≤ Ui

where 1 ≤ i ≤ c

The lower bound L_i can be -∞ and the upper bound can be +∞.

For each row 1 ≤ j ≤ r the j-th constraint is

bj = a1,j x1 + a2,j x2 + . . . + ac,j xc

lj ≤ bj ≤ uj

where 1 ≤ j ≤ r

A feasible solution is a tuple x = <x₁, x₂, . . . , x_c> which satisfies all constraints.

There are m ≥ 1 objectives, which are given as

yk = o1,k x1 + o2,k x2 + . . . + oc,k xc

where 1 ≤ k ≤ m.

The m-dimensional objective vector y = <y₁, . . ., y_m> is achievable if there is a feasible solution x which yields exactly these objective values.

The solution of a MOLP is the list of all extremal objective vectors. For a minimizing (maximizing) MOLP the objective vector y is extremal if there is no other achievable objective vector y' which would be coordinatewise ≤ y (or ≥ when maximizing).

The task of MOLP solver is to find the collection of all extremal objective vectors. These extremal vectors are called vertices as they form the vertices of an (unbounded) convex m-dimensional polytope.

This MOLP solver finds the extremal vectors by iterations. In each step one more extremal vector is added to the final list. The time required for an iteration varies widely from a couple of microseconds to several days. After each iteration the solver checks if the process has been interrupted by a SIGUSR1 signal. If it has, it switches to a quick and dirty method which might find further extremal vectors (but not necessarily all of them).

RESTRICTIONS

The linear constraints must have a feasible solution. Moreover, in a minimizing MOLP all objectives must be bounded from below, and in a maximizing MOLP all objectives must be bounded from above.

ALGORITHM

The algorithm is described in details in the paper Inner approximation algorithm for solving linear multiobjective optimization problems, Optimization (2021), 70:7, 1487-1511, DOI: 10.1080/02331934.2020.1737692

USAGE

The program is invoked as

inner [options] <vlp-file>

The only obligatory argument is the file name which contains the description of the problem in vlp format. Accepted options are

Option	meaning
-h	display a short help and quit
--help	display all options
--help=<topic>	help on one of the following topics: input, output, exit, signal, checkpoint, resume, boot, vlp
--help=output	describe the output format
--version	version and copyright information
--dump	dump the default config file and quit
--config=<config-file> or -c <config-file>	read configuration from the given file use --dump to show the default config file
-o <file>	save results (both vertices and facets) to <file>
-ov <file>	save vertices to <file>
-of <file>	save facets to <file>
-oc <stub>	file stub for checkpoint files
--name=NAME or -n NAME	specify the problem name
--boot=<vertex-list>	start the algorithm with these vertices
--resume=<chk-file>	resume computation from a checkpoint file
-m[0..3]	set message level: 0: none, 1: errors, 2: all, 3: verbose
-q	quiet, same as -m0. Implies --PrintStatistics=0
-p T	progress report in every T seconds (default: T=5)
-p 0	no progress report
-y+	report extremal solutions (vertices) immediately when generated (default)
-y-	do not report extremal solutions when generated
--KEYWORD=value	change value of a config keyword

CONFIGURATION PARAMETERS

Fine tuning the algorithm and the underlying scalar LP solver, and specifying the amount and type of information saved is done by giving values of several keywords. Each keyword has a default value, which is overwritten by the values in the config file (if specified), and those values are overwritten by the --KEYWORD=value command line options. Change tolerances with great care.

Algorithm parameters
RandomFacet=1	0 = no, 1 = yes pick a random facet which is then passed to the oracle.
ExactFacetEq=0	0 = no, 1 = yes when a facet is created, recompute its equation immediately from the set of adjacent vertices.
RecalculateFacets=100	non-negative integer after this many iterations recalculate all facet equations from the set of its adjacent vertices. The number should be zero (meaning never), or at least 5.
CheckConsistency=0	non-negative integer after this many iterations check the consistency of the data structure against numerical errors. The number should be zero (meaning never), or at least 5.
ExtractAfterBreak=1	0 = no, 1 = yes when the program receives a SIGUSR1 signal or reaches the memory limit, continue extracting new vertices by asking the oracle about every facet of the actual approximating polyhedron. Second signal aborts this post-processing.
MemoryLimit=0	non-negative integer upper limit for memory allocation in Mbytes. When reaching this limit, stop processing as if received a SIGUSR1 signal. Zero means no limit, otherwise it must be at least 100.
TimeLimit=0	non-negative integer upper limit for running time in seconds. When reaching this limit, stop processing as if received a SIGUSR1 signal. Zero means no limit, otherwise it must be at least 60 seconds.
VertexPoolSize=0	non-negative integer size of the vertex pool: add the vertex to the approximation which discards the largest number of existing facets. Should be zero (don't use it), or at least 5. Using vertex pool adds more oracle calls, but can simplify the approximating polytope.
CheckPoint=10000	positive integer frequency (in seconds) for creating checkpoint files when the option -oc <filestub> is given. The filename is got from the stub by appending NNN.chk where NNN starts with 000 and increases. The computation can be resumed from a checkpoint file by calling inner with --resume=<checkpoint> The value should be more than 500.
OracleCallLimit=1	non-negative integer the maximal number of unsuccessful oracle calls during an iteration when filling the vertex pool. Zero means no limit; otherwise should be less than 100.
Threads=0	non-negative integer number of threads to use; should be less than 64. Zero means use as many threads as are available; 1 means don't use threads.
Oracle parameters
OracleMessage=1	0 = quiet, 1 = error, 2 = on, 3 = verbose oracle (glpk) message level.
OracleMethod=0	0 = primal, 1 = dual the LP method used by the oracle.
Oracle#=1	0 = standard, 1 = steepest edge the LP # method.
OracleRatioTest=1	0 = standard, 1 = Harris' two pass the LP ratio test.
OracleTimeLimit=20	non-negative integer time limit for each oracle call in seconds; 0 means unlimited.
OracleItLimit=10000	non-negative integer iteration limit for each oracle call; 0 means unlimited.
OracleScale=1	0 = no, 1 = yes scale the constraint matrix; helps numerical stability.
ShuffleMatrix=1	0 = no, 1 = yes shuffle rows and columns of the constraint matrix randomly.
RoundVertices=1	0 = no, 1 = yes when the oracle reports a result vertex, round its coordinates to the nearest rational number with small denominator.
Reporting
MessageLevel=2	0 = quiet, 1 = error, 2 = on, 3 = verbose report level; quiet means no messages at all. The command line option -m[0..3] overrides this value.
Progressreport=5	non-negative integer minimum time between two progress reports in seconds. Should be zero for no progress reports, or at least 5. The command line option -p T overrides this value.
VertexReport=1	0 = no, 1 = yes report each vertex (extremal solution) immediately when it is found. The command line option -y- (no) or -y+ (yes) overrides the value defined here.
FacetReport=0	0 = no, 1 = yes report each final facet immediately when it is found.
MemoryReport=0	0 = no, 1 = at the end, 2 = always report the size and location, whenever they change, of the memory blocks storing the combinatorial data structure.
VertexAsFraction=1	0 = no, 1 = yes if possible, print (and save) vertex coordinates as fractions with small denominators rather than floating point numerals.
PrintStatistics=1	0 = no, 1 = yes print resources used (number of iterations, ridge tests, etc.) when the program stops.
PrintParams=1	0 = no, 1 = yes print algorithm parameters which are not equal to their default values.
PrintVertices=2	0 = no, 1 = on normal exit only, 2 = always print (again) all known vertices when the program terminates.
PrintFacets=0	0 = no, 1 = on normal exit only, 2 = always print all known (relevant) facets when the program terminates.
SaveVertices=2	0 = no, 1 = on normal exit only, 2 = always when the program terminates, save known vertices to the file specified after command line option -o. For file specified after -ov both 0 and 1 means "save on normal exit only".
SaveFacets=1	0 = no, 1 = on normal exit only, 2 = always when the program terminates, save known (relevant) facets to the file specified after the command line option -o. For the file specified after -of both 0 and 1 means "save on normal exit only".
Tolerances	Change these values with care
PolytopeEps=1.3e-8	positive real number a facet and a vertex are considered adjacent if their distance is smaller than this value.
ScaleEps=3e-9	positive real number coefficients in the scaled facet equation are rounded to the nearest integer if they are closer to it than this value.
LineqEps=8e-8	positive real number when solving a system of linear equations for a facet equation, a coefficient smaller than this is considered to be zero.
RoundEps=1e-9	positive real number if the oracle reports vertices with rounded coordinates (RoundVertices=1), this is the tolerance in the rounding algorithm.
FacetRecalcEps=1e-6	positive real number when recalculating facet equation, report numerical instability if the new and old coordinates differ at least this much.

EXIT STATUS

When the program terminates, the exit status is zero when the problem has been solved successfully; otherwise it indicates the failure condition:

Exit value
0	problem solved
1	error before starting the algorithm, such as missing argument, wrong or missing data file, out of memory, etc.
2	there is no feasible solution for the MOLP problem
3	the solution space is unbounded in some objective direction
4	error while executing the algorithm (oracle failure, numerical error, etc)
5	program execution was interrupted by a SIGUSR1 signal

SIGNALS

When the program receives a SIGUSR1 signal, it stops the main cycle of iterations, and switches to a "quick and dirty" method to generate additional extremal solutions. (Actually, the oracle is asked about all facets of the actual approximation; it returns an extremal solution on or beyond that facet.) The method might miss extremal solutions, so the result is not known (can not) be complete. A second SIGUSR1 signal aborts this post-processing.

When receiving a SIGUSR2 signal (since version 2.8), the program creates a snapshot file containing the vertices and facets of the actual approximation. Similarly to checkpoint files, the snapshot file can be used to resume the computation from that point.

The name of the snapshot file is created as follows. If a checkpoint stub is provided after the -oc option, then 000.dmp is appended to the stub. If no -oc option is provided but there is a -o output file, then the extension of that filename is replaced by dmp. If neither -oc nor -o option is present, then no snapshot is created. When receiving a second SIGUSR2 signal, the same filename is used: the previous content is silently overwritten.

Signals are checked only when an iteration step has been completed, that is a new vertex has been added to the approximation. (These are the points when the data is guaranteed to be consistent.) Depending on the complexity of the problem and the number of intermediate vertices and facets, the time between these points vary from milliseconds to several days.

USING MULTIPLE CORES

The threaded version of inner can use all available cores on the computer to speed up the computation. Multiple cores can help in the combinatorial part, when the work is distributed approximately uniformly among them. The LP part (oracle calls) is inherently single-threaded and cannot be speed up this way. Thus LP intensive problems (large number of columns and rows and only a few objectives) will not gain too much from multiple threads. Specifying more cores than available comes with a significant performance penalty.

COMPILATION

The program uses a patched version of glpk, the GNU Linear Program Kit. First, glpk should be compiled after the patch has been applied. Unpack the glpk source. In the glpk-X.Y directory execute the command

patch -p1 < ../src/patch-X.Y.txt

assuming you have unpacked glpk in the root of this repository. Still in the glpk-X.Y directory run 'configure' and 'make' as follows:

./configure
make CFLAGS='-O3 -DCSL'

You must define CSL as all patches to glpk are encapsulated in #ifdef CSL blocks.

Changing to the directory INNER/src, the following command compiles inner linking the patched glpk routines statically:

gcc -O3 -W -I ../glpk-X.Y/src -o inner *.c ../glpk-X.Y/src/.libs/libglpk.a -lm

The threaded version requires defining USETHREADS and adding the flag -pthread:

gcc -O3 -W -I ../glpk-X.Y/src -o innerth -DUSETHREADS -pthread *.c ../glpk-X.Y/src/.libs/libglpk.a -lm

EXAMPLES

The 'examples' directory contains vlp files describing different MOLPs. File names contain three numbers separated by dashes: the number of objectives, the number of rows, and the number of columns. Each file starts with some comment lines.

Solutions are in the 'solution' directory. The same file name with the extension .res contains the list of vertices and facets. .out files contain progress reports, statistics, and parameter settings.

AUTHOR

Laszlo Csirmaz, csirmaz@ceu.edu