User manual

Preface

0ptX enables business operations to be organized, coordinated and optimized. To this end, the processes involved are translated into a mathematical model that can be represented by a mixed-integer system of (linear) equations, inequalities and suitable objective functions (mixed-integer linear system).

You must carry out this (one-time) modeling process yourself or have it done by a mathematician you trust. But do not worry - this guide will introduce you to this discipline through various practical examples.

0ptX determines (optimal) solutions for this modeled system. The solutions can be transformed back into the original processes and ultimately provide optimized strategies for carrying them out.

For this task, 0ptX

uses a lattice-based approach and implements methods originating in the dissertation Gitterbasenreduktion mit Random Sampling und heuristischen Methoden.

The following sections introduce various problems that result in mixed-integer linear systems and provide a brief introduction to mathematical modeling. After this excursion, you will learn about the many options offered by 0ptX and acquire the knowledge required to use it through simple tutorials.

Problems

The following (illustrative) problems are intended to demonstrate how you can translate your actual processes into a form that can be solved using 0ptX . If you find a problem in the list below that corresponds (more or less) to your process, use it as a basis for formulating your own scenario.

Composition problems

Loading problem

Let there be n objects with utility values c1,c2,,cn and respective weights g1,g2,,gn. Objects are to be packed into a container with capacity K such that the total utility value of all packed objects is maximized without exceeding the container's capacity.

The mathematical formulation is as follows:

Maximize

n
∑	cixi
i=1

such that

n
∑	gixi≤K
i=1

and xi0,1 for i=1,2,,n

The i-th object is placed in the container if and only if the i-th component of the solution vector is 1; if it is 0, the object is not selected.

In the literature, the loading problem is also known as the knapsack problem, since this question arises in particular when packing a backpack or suitcase..

Blending problem

The blending problem arises in applications involving the composition of building materials, diet plans or animal feed.

Consider the following example:

A feed manufacturer has several nutrient supplements available for formulating a new type of specialized feed. The feed must provide specified minimum quantities of nutrients while being as inexpensive as possible.

The composition of the nutrient supplements and the required minimum levels for the feed are shown in the following table:

	Carbohydrates	Proteins	Vitamins	Cost

Concentrated feed	20	15	5	12 €
Plant material	10	3	10	7 €
Grain supplement	12	2	3	9 €
Fattening feed	30	15	5	18 €

Minimum quantity	50	30	40

The task is to decide which supplements should be used to produce the specialized feed in order to meet requirements at minimum cost.

The answer is again provided by a linear equation system. Its solution vector (x1,x2,x3,x4) contains the proportions of concentrated feed, plant material, grain supplements and fattening feed that ensure minimum-cost production of the feed mix while satisfying the minimum quantity requirements.

In this form, the system does not yet require the solution vector to be integral. However, to account for the fact that, for example, fattening feed may be processed only in whole units, a mixed-integer system is essential:

Minimize 12x17x29x318x4

such that 20x110x212x330x4≤50,
15x13x22x315x4≤30,
5x110x23x35x4≤40,

0≤x1≤K1, 0≤x2≤K2,
0≤x3≤K3, 0≤x4≤K4

and x1,x2,x3, x4

( Ki denotes the available stock of nutrient supplement i=1,2,3,4 )

Purchasing problems

Bundle problem

To manufacture electrical appliances, a company needs a certain number of capacitors, resistors and circuit boards every day. These materials can only be purchased from wholesalers in specified quantities (bundles). The company's goal is to combine the available offers so that demand is met without spending more money than necessary.

The wholesalers' bundle offers:

	Capacitors	Resistors	Circuit boards	Price

Wholesaler A	20000	15000	5000	1000 €
Wholesaler B	16000	3000	10000	800 €
Wholesaler C	16000	10000	8000	750 €
Wholesaler A	20000	0	0	450 €
Wholesaler B	10000	0	4000	300 €
Wholesaler C	0	3000	0	200 €
Wholesaler C	0	0	4000	100 €

Minimum demand	40000	30000	20000

This yields the following mathematical formulation:

Minimize 1000x1800x2750x3450x4300x5200x6100x7

such that 20000x116000x216000x320000x410000x5≥40000,
15000x13000x210000x33000x6≥30000,
5000x110000x28000x34000x54000x7≥20000,

0≤x1≤4, 0≤x2≤10,
0≤x3≤3, 0≤x4≤2, 0≤x5≤5,
0≤x6≤10, 0≤x7≤5,

xi for i=1,2,,7

Even in this simple example, 261360 different combinations would have to be checked to identify the cheapest combination with absolute certainty.

Inventory management problem

A retailer needs n different goods and has a maximum storage capacity for each good. The required goods can be purchased from m wholesalers, each of whom supplies the goods subject to minimum and maximum quantities (mi,j, Mi,j) and at a specified price pi,j. The retailer's objective is to meet demand bj for each good, stay within the respective storage capacity lj, and minimize the total cost of the goods purchased.

Minimize

n	m
∑	∑	xi,jpi,j
i=1	j=1

such that bi≤

m
∑	xi,j
j=1

≤li for i=1,2,,n
mi,j≤xi,j≤Mi,j for i=1,2,,n or j=1,2,,m

and xi,j for i=1,2,,n or j=1,2,,m

The variable xi,j represents the quantity of good i that the retailer should purchase from wholesaler j in order to minimize costs.

Sales problem

A company that manufactures electrical appliances wants to sell its products profitably on the open market. It has received various offers from different consumer electronics retailers. Which offers should be fulfilled with the available quantity of appliances in order to achieve the maximum possible sales profit?

The offers from the retailers:

	Computers	Televisions	Tablet PCs	Purchase offer

Retailer A	200	150	50	100000 €
Retailer B	160	30	100	80000 €
Retailer C	160	100	80	75000 €
Retailer A	200	0	0	45000 €
Retailer B	100	0	40	30000 €
Retailer C	0	30	0	20000 €
Retailer C	0	0	40	10000 €

Production quantity	400	300	200

The mathematical model is as follows:

Maximize 100000x180000x275000x345000x430000x520000x610000x7

such that 200x1160x2160x3200x4100x5≤400,
150x130x2100x330x6≤300,
50x1100x280x340x540x7≤200,

0≤x1≤2, 0≤x2≤2,
0≤x3≤2, 0≤x4≤2, 0≤x5≤4,
0≤x6≤10, 0≤x7≤5,

xi for i=1,2,,7

Capacity utilization problem

Ein Betrieb setzt m Maschinen zur Herstellung von n verschiedenen Bauteilen Bj ein. Die Maschinen sind für die Herstellung der Bauteile unterschiedlich gut geeignet, was sich in der Herstellungszeit ti,j niederschlägt, die von der i-ten Maschine benötigt wird, um das j-te Bauteil zu produzieren. Es soll nun von jedem Bauteil Bj eine vorgegebene Anzahl bj produziert werden, und zwar derart, dass die Zeit, die für die Produktion aller Bauteile benötigt wird, minimiert wird - was mit einer optimalen Auslastung der Maschinen einhergeht.

Es wird also eine Matrix xmn gesucht, die nachstehendes Problem löst:

Minimize

m	n
∑	∑	xi,jti,j
i=1	j=1

such that

m
∑	xi,j=bj
i=1

for j=1,2,,n

and 0≤xi,j≤bj for 1≤i≤m or 1≤j≤n

If the i-th machine is not suitable for manufacturing the j-th component, the corresponding variable xi,j in the model must be replaced by 0.

The following table lists, by way of example, the manufacturing times for several components on different machines. The actual demand is shown at the end of the table:

	Wheel bearing (B1)	Gear (B2)	Frame component (B3)	Crankshaft (B4)	Cylinder (B5)

Milling machine M1	45	15	30	35	90
Milling machine M2	20	10	15	40	-
Milling machine M3	-	5	20	-	45
Milling machine M4	20	-	-	30	-
Milling machine M5	-	10	40	-	-
Milling machine M6	30	20	60	45	120

Demand	40	100	20	50	30

In this particular case, the result is:

Minimize 45x1,115x1,230x1,335x1,490x1,520x2,110x2,215x2,340x2,45x3,220x3,345x3,520x4,130x4,410x5,240x5,330x6,120x6,260x6,345x6,4120x6,5

such that x1,1x2,1x4,1x6,1=40,
x1,2x2,2x3,2x5,2x6,2=100,
x1,3x2,3x3,3x5,3x6,3=20,
x1,4x2,4x4,4x6,4=50,
x1,5x3,5x6,5=30,

x2,5=0, x3,1=0, x3,4=0, x4,2=0, x4,3=0, x4,5=0, x5,1=0, x5,4=0, x5,5=0,

0≤xi,1≤40, 0≤xi,2≤100, 0≤xi,3≤20, 0≤xi,4≤50, 0≤xi,5≤30 for i=1,2,,6

xi,j for 1≤i≤6 and 1≤j≤5

Production problem

A manufacturer produces m different products. Manufacturing a product Pi requires various components Bj (1≤j≤n). Which products, and in what quantities, should be manufactured from the available stock of components in order to maximize profit, satisfy minimum and maximum production quantities, and avoid violating any resource constraints?

The selling price of Pi is denoted by pi, and its manufacturing cost by hi. The available stock of components of type Bj is denoted by bj, the maximum production quantity of a product by ui, and the minimum production quantity by li. A component Bj costs cj, and the number of components Bj required to manufacture Pi is denoted by bi,j.

Accordingly, a vector xm is sought that solves the following problem:

Maximize

m		n
∑	xipihi	∑	bi,jcj
i=1		j=1

such that 0≤

m
∑	xibi,j
i=1

≤bj for j=1,2,,n
and li≤xi≤ui for i=1,2,,m

This simple and flexible model makes it possible to respond in real time to changes in component prices or manufacturing costs.

Transportation problem

The classical transportation problem is also known as the "travelling salesperson problem" and is formulated as follows:

Starting from a specified city, a traveler wishes to complete a tour through <mm>n</mm> cities such that the total distance traveled is minimized.

A tour means that the journey ends in the same city in which it began.

If di,j denotes the distance between the i-th and j-th cities, the problem can be formulated mathematically as follows:

Minimize

n	n
∑	∑	di,jxi,j
i=1	j=1,j≠i

such that

n
∑	xi,j=1
i=1,j≠i

for j=1,2,,n

n
∑	xi,j=1
j=1,i≠j

for i=1,2,,n
uiuj(n1)xi,j≤n2 for 2≤ij≤n

and xi,j0,1 for i,j=1,2,,n
and ui2,3,,n for i=2,3,,n

The variable xi,j is equal to 1 if the tour goes directly from the i-th city to the j-th city, and equal to 0 otherwise. The additional variable ui indicates the position of the i-th city in the tour.

The first two systems of equations for xi,j ensure that the required tour enters and leaves each city exactly once. The inequalities involving ui ensure that the tour is connected. A more detailed explanation of the mathematical background can be found here:

https://en.wikipedia.org/wiki/Travelling_salesman_problem

Logistics problem

A frequently encountered variant of the transportation problem in logistics takes into account the cargo weight of the goods being transported as an additional parameter:

A truck is loaded with n goods and starts from a specified city. Each item is destined for a particular city i and has a cargo weight of gi kilograms. The objective is to find a tour that minimizes the truck's fuel consumption.

The constant L represents the fuel consumption of the unloaded truck per 100 km. The additional fuel consumption per tonne of cargo per 100 km is represented by the constant T.

The problem can now be formulated in a manner similar to the "travelling salesperson problem". However, additional variables yi,j are introduced to represent the number of kilograms of cargo transported from city i to city j.

Minimize

n	n
∑	∑	di,jL/100(xi,jyi,jT/1000)
i=1	j=1,j≠i

such that

n
∑	xi,j=1
i=1,j≠i

for j=1,2,,n

n
∑	xi,j=1
j=1,i≠j

for i=1,2,,n
uiuj(n1)xi,j≤n2 for 2≤ij≤n

n
∑	yj,i
j=1,j≠i

n
∑	yi,j
j=1,j≠i

=gifor i=1,2,,n
0≤yi,j≤xi,jG for 1≤ij≤n
such that G:=

n
∑	gi
i=2

and xi,j0,1 for i,j=1,2,,n
ui2,3,,n for i=2,3,,n yi,j0,1,2,,G for i,j=1,2,,n

In the literature, a logistics problem of this type is also referred to as Green Vehicle Routing Problem.

Market allocation problem

Market allocation problems arise when a company has offices in several countries and, due to differing tax rates, wants to distribute its sales activities so that a larger sales volume is allocated to countries with a lower tax burden.

A company consists of two divisions, D1 and D2, which supply several sales partners with different products. The market allocation problem consists of assigning each sales partner to exactly one division (i.e. either D1 or D2) so that D1 controls a p fraction of the market for each company product and D2 controls the remaining 100(1p) percent.

Let m denote the number of sales partners, n the number of different products, and ai,j the demand of sales partner i for product j. The mathematical formulation is then:

Minimize

m
∑	si
i=1

such that

m
∑	ai,jxjsi=bi
j=1

for i=1,2,,m
xj0,1 for j=1,2,,n
and si for i=1,2,,m.

The right-hand side

bi=p

m
∑	ai,j
j=1

i=1,2,,m

is determined by the desired market split between D1 and D2.

The components of the (binary) solution vector x assign each sales partner to one of the two divisions. A value of 0 denotes division D1, and a value of 1 denotes division D2.

The value of si reflects the extent to which the market split could be achieved for the i-th product. If si=0, the exact split was possible.

If an exact split is not possible, the minimization function included in the formulation ensures that a solution with the smallest possible deviation is sought.

Mathematical description

An abstract mathematical description encompassing all these mixed-integer linear systems can be formulated as follows:

Let the linear objective functions be represented by an objective function matrix Ctn and a vector d∞,∞t⋃t. The rows of C contain the coefficients of the objective functions, while the entries of d define the objective function values..

Furthermore, let A be a matrix gn and b be a vector g. They represent the linear equation system that a solution must satisfy.. Let the system of inequalities be described by a matrix Hrn and vectors v,wr, whose entries define intervals within which the inequality results of an optimal solution must lie.

Two additional vectors l and u contain the interval bounds within which the components of a vector xn must lie in order to qualify as a solution..

The resulting general linear optimization problem (mixed-integer linear system) is then:

Find a xn such that

Ax=b, v≤Hx≤w and l≤x≤u 🔍

such that for y:=Cx the objective function sum


∑	yi
di=


∑	yi
di=


∑	yidi
di

is minimized.

The partial sum


∑	yidi
di

is also referred to as the slack deviation..

A system of this type can be solved to optimality in polynomial time. However, if individual components of the solution vector x are required to be integers, an exponential number of computational steps is necessary.

The need for an integrality constraint arises from practical considerations, for example because only whole units can be produced or, in decision-making processes, only two states are permitted.

To represent such integrality requirements, let there also be a vector p0n whose components specify the maximum number of decimal places for the corresponding components of x..

This yields the final constraint on the number of decimal places f of x:

f:n→0n,x↦f(x)≤p

Software package

In addition to the main program, the package contains various auxiliary tools and can be used on computers with Intel processors running FreeBSD, Linux, macOS or Windows. The programs are operated from the command line and therefore require some user knowledge of Windows consoles or UNIX shells. A graphical user interface (operable through a browser) is still under development.

The package contains the following program files:

0ptX	(Main program)
opt2lp, lp2opt	(Converter)
sol	(Verifier)

Sample problem files in lp or opt format are located in appropriately named subdirectories.

Brief description

The main program 0ptX reads files in opt format containing the equation systems to be solved and initially converts this data into an equivalent lattice problem, which is stored temporarily in a file with the extension lat.

When the main program is called multiple times with the same opt file, it starts directly from the easier-to-process lat file, resulting in improved performance.

To compare 0ptX with the competing product IBM ILOG CPLEX, its lp format must be converted to opt format. This is handled by lp2opt. The reverse conversion is performed by opt2lp.

After the main program has been started, a file with the extension sol is created in the directory containing the corresponding opt or lat file. It stores all solution vectors and (heuristically) shortest lattice vectors found so far.

The sol files are stored in encrypted form. Decryption and conversion into corresponding solutions of the original system are performed by the auxiliary program sol, which you can use in conjunction with a decryption quota.

To give you a comprehensive impression of 0ptX

even without a decryption quota, solutions to problems with dimension n≤10 are not encrypted and can therefore be reviewed without restriction.

Input formats

The opt format

The opt format serves as the standard format for storing a general linear optimization problem, as presented in the second chapter.

A vector v is represented by listing its entries, separated by spaces and enclosed in square brackets:

[v1v2vn]

A matrix A=(ai,j) can be represented in the same way:

[
[a1,1a1,2a1,n]
[a2,1a2,2a2,n]
⋮
[am,1am,2am,n]
]

The problem data are therefore stored in an opt-format file as follows:

		/* Objective function section: d, C */
		
[d1d2dt]
[
[c1,1c1,2c1,n]
[c2,1c2,2c2,n]
⋮
[ct,1ct,2ct,n]
]	
		
/* Equation section: A, b */
		
[
[a1,1a1,2a1,n]
[a2,1a2,2a2,n]
⋮
[ag,1ag,2ag,n]
]
[b1b2bg]
[q1q2qg]	
		
/* Inequality section: H, v, w */
		
[
[h1,1h1,2h1,n]
[h2,1h2,2h2,n]
⋮
[hr,1hr,2hr,n]
]
[v1v2vr]
[w1w2wr]	
		
/* Solution vector section: p, l, u */
		
[p1p2pn]
[l1l2ln]
[u1u2un]

If the modulo vector q is not required, at least one empty pair of [] brackets must be specified. The same convention is used for other data that are not required.

The following illustrative examples demonstrate the practical use of the file format:

Example (without an objective function)

Find a x4 such that (1,0,0,1)T≤;x≤(2,3,4,5)T,
such that: 2x24x3=16, 3x17x4=31,
0≤x15x4≤21, 2≤x2x3≤7

This yields:

C =

, d =

,
A =

0	2	4	0
3	0	0	7

, b =

, q =

,
H =

1	0	0	5
0	1	1	0

, v =

w =

,
p =

T, l =

T, u =

Accordingly, the corresponding file "example.opt" has the following contents:

		[ ]
		
[
		
]
		
[
		
[ 0 2 4 0 ]
		
[ 3 0 0 7 ]
		
]
		
[ 16 31 ]
		
[ ]
		
[
		
[ 1 0 0 5 ]
		
[ 0 1 1 0 ]
		
]
		
[ 0 2 ]
		
[ 21 7 ]
		
[ 0 0 0 0 ]
		
[ 1 0 0 1 ]
		
[ 2 3 4 5 ]

Example (with one objective function)

Find ax4such that
(1,0,0,1)T≤x≤(2,3,4,5)T,

such that: 2x24x3=16, 3x17x4=31
0≤x15x4≤21, 2≤x2x3≤7

where5x1x22x36x4 is maximized.

This gives:

C =

, d =

,
A =

0	2	4	0
3	0	0	7

, b =

, q =

,
H =

1	0	0	5
0	1	1	0

, v =

, w =

,
p =

T, l =

T, r =

The corresponding opt file therefore contains:

		[ inf ]
		
[
		
[ 5 1 -2 6 ]
		
]
		
[
		
[ 0 2 4 0 ]
		
[ 3 0 0 7 ]
		
]
		
[ 16 31 ]
		
[ ]
		
[
		
[ 1 0 0 5 ]
		
[ 0 1 1 0 ]
		
]
		
[ 0 2 ]
		
[ 21 7 ]
		
[ 0 0 0 0 ]
		
[ 1 0 0 1 ]
		
[ 2 3 4 5 ]

Example (with two objective functions)

Find a x4
such that (1,0,0,1)T≤x≤(2,3,4,5)T,

such that: 2x24x3=16, 3x17x4=31
0≤x15x4≤21, 2≤x2x3≤7

where x13x2x3x4 minimized,
and 5x1x22x36x4 is maximized.

The resulting data are:

C =

1	3	1	1
5	1	2	6

, d =

,
A =

0	2	4	0
3	0	0	7

, b =

, q =

,
H =

1	0	0	5
0	1	1	0

, v =

, w =

,
p =

T, l =

T, u =

And the corresponding opt file contains:

		[ -inf inf ]
		
[
		
[ 1 -3 1 1 ]
		
[ 5 1 -2 6 ]
		
]
		
[
		
[ 0 2 4 0 ]
		
[ 3 0 0 7 ]
		
]
		
[ 16 31 ]
		
[ ]
		
[
		
[ 1 0 0 5 ]
		
[ 0 1 1 0 ]
		
]
		
[ 0 2 ]
		
[ 21 7 ]
		
[ 0 0 0 0 ]
		
[ 1 0 0 1 ]
		
[ 2 3 4 5 ]

Example (with three objective functions)

Find a x4
such that(1,0,0,1)T≤x≤(2,3,4,5)T,

such that: 2x24x3=16, 3x17x4=31
0≤x15x4≤21, 2≤x2x3≤7

where x13x2x3x4 minimized
5x1x22x36x4 maximized,
and 9x1x22x38x410 is minimized.

This yields:

C =

1	3	1	1
5	1	2	6
9	1	2	8

, d =

,
A =

0	2	4	0
3	0	0	7

, b =

, q =

,
H =

1	0	0	5
0	1	1	0

, v =

, w =

,
p =

T, l =

T, u =

And in the form of an opt file:

		[ -inf inf 10 ]
		
[
		
[ 1 -3 1 1 ]
		
[ 5 1 -2 6 ]
		
[ 9 -1 2 -8 ]
		
]
		
[
		
[ 0 2 4 0 ]
		
[ 3 0 0 7 ]
		
]
		
[ 16 31 ]
		
[ ]
		
[
		
[ 1 0 0 5 ]
		
[ 0 1 1 0 ]
		
]
		
[ 0 2 ]
		
[ 21 7 ]
		
[ 0 0 0 0 ]
		
[ 1 0 0 1 ]
		
[ 2 3 4 5 ]

The final example below makes use of all the features of the opt file format. In particular, some components of the solution vector are not required to be integers; in that case, the maximum number of decimal places must be specified.

Example (with mixed-integer solutions)

Finde ein x
mit (1,0,0,1)T≤x≤(2,3,4,5)T,

und höchstens 4 bzw. 1 Nachkommastelle(n)
in der zweiten bzw. dritten Komponente,

so dass: 2x24x3=16, 3x17x4=31
0≤x15x4≤21, 2≤x2x3≤7

wobei x13x2x3x4 minimal,
5x1x22x36x4 maximal
und 9x1x22x38x410 minimiert wird.

		[ -inf inf 10 ]
		
[
		
[ 1 -3 1 1 ]
		
[ 5 1 -2 6 ]
		
[ 9 -1 2 -8 ]
		
]
		
[
		
[ 0 2 4 0 ]
		
[ 3 0 0 7 ]
		
]
		
[ 16 31 ]
		
[ ]
		
[
		
[ 1 0 0 5 ]
		
[ 0 1 1 0 ]
		
]
		
[ 0 2 ]
		
[ 21 7 ]
		
[ 0 4 1 0 ]
		
[ 1 0 0 1 ]
		
[ 2 3 4 5 ]

lp → opt

To read a linear problem in CPLEX lp format, you need the lp2opt program, which converts the problem to opt format.

The input file "example.lp" has the following contents:

		Minimize
		
 obj: 2x1 - 4x2 + 5x3
		
Subject To
		
 1x1 + 5x4 <= 21
		
 1x1 + 5x4 >= 0
		
 2x2 + 4x3 = 16
		
 3x1 + 7x4 = 31
		
Bounds
		
 0 <= x1 <= 2
		
 0 <= x2 <= 3
		
 0 <= x3 <= 4
		
 0 <= x4 <= 5
		
General
		
 x1 x2 x3 x4
		
End

The following command converts the file to opt format and saves it under the name "exanple.opt":

# ./lp2opt example.lp

The resulting file "example.opt" contains:

		[ -inf ]
		
[
		
[ 2 -4 5 0 ]
		
]
		
[
		
[ 0 2 4 0 ]
		
[ 3 0 0 7 ]
		
]
		
[ 16 31 ]
		
[ ]
		
[
		
[ 1 0 0 5 ]
		
]
		
[ 0 ]
		
[ 21 ]
		
[ 0 0 0 0 ]
		
[ 0 0 0 0 ]
		
[ 2 3 4 5 ]

If you want to perform the reverse conversion, i.e. from opt format to CPLEX lp format, use the auxiliary program opt2lp.

The lp2opt converter will work well in most cases. However, it fails if not all variables in the lp file are named x. You should therefore ensure this condition is met if you want to use the converter. Nevertheless, we recommend using the opt format directly, as it offers more options for formulating problems.

Program invocation

Usage

Once the actual problem is available as an opt file, it can be solved by invoking 0ptX . The following examples illustrate some typical ways of using the program.

In the first variant, the program is started with the default options. Specifying --verb=2 instructs it to output as many status messages as possible to the console:

# ./0ptX --verb=2 example.opt

The next command line increases the enumeration block size to 25 and enables a scaling procedure. The program terminates as soon as 4 distinct solutions have been found:

# ./0ptX --beta=25 --scale=1 --sol=4 example.opt

The snorm and tnorm parameters can be used to specify the extent to which the requirements of the objective function system must be satisfied. In addition to satisfying the equation and inequality components of the linear system, the resulting solutions also meet the specified objective function requirements.

# ./0ptX --tnorm=13 --sol=1 example.opt

With this command line, program execution is terminated as soon as a solution x is found for which:


∑	yi
di=


∑	yi
di=


∑	yidi
di

≤13

If the termination condition is to take into account only objective functions with objective values di, use the snorm parameter instead. In this case, only the value of the third sum is taken into account.

If the optimization problem's objective functions have only finite target values, the snorm and tnorm parameters have the same effect, since the first two sums are then equal to 0.

The usefulness of snorm becomes clear in the following example: The linear equation system

1	2	3
4	5	6
7	8	9

x =

such that

T ≤x≤

T
and x3

is to be solved.

The resulting opt file therefore contains:

		[ ]
		
[
		
]
		
[
		
[ 1 2 3 ]
		
[ 4 5 6 ]
		
[ 7 8 9 ]
		
]
		
[ 10 20 30 ]
		
[ ]
		
[
		
]
		
[ ]
		
[ ]
		
[ 0 0 0 ]
		
[ 0 0 0 ]
		
[ 40 50 60 ]

If 0ptX does not find a solution now, there is a simple reason: the system is unsolvable. Nevertheless, you may be interested in finding a solution that satisfies the equation system "almost".

To achieve this, the equation system must be formulated as a system of objective functions with specified target values:

Minimize

Tx - 10

Tx - 20

Tx - 30

where

T ≤x≤

T
and x3

The corresponding opt file therefore looks as follows:

		[ 10 20 30 ]
		
[
		
[ 1 2 3 ]
		
[ 4 5 6 ]
		
[ 7 8 9 ]
		
]
		
[
		
]
		
[ ]
		
[ ]
		
[
		
]
		
[ ]
		
[ ]
		
[ 0 0 0 ]
		
[ 0 0 0 ]
		
[ 40 50 60 ]

The next invocation searches for a solution with a total target deviation of 4. Execution is therefore terminated as soon as a solution x is found for which:


∑	yidi
di

≤4

Such an "almost" solution is also referred to as a solution with slack.

The following invocation then produces this output:

# ./0ptX --snorm=4 opt/showcases/simple.opt

<< 0ptX v2.1.3 +++ (c) BirdWorX Solutions 2023 +++ PID: 3648 >> [ Registered standard license for: xxx@yyy.zz ] Got signal: Terminated: 15 ************************** Terminated ************************** T(bestTarget) = 4, S(bestTarget) = 4 -- { 0 sec(s) } { The first solution/s was/were found after: 0 sec(s) } The following file contains the results: opt/showcases/simple.sol Total iterations: 11 Total running time: 0 sec(s) -- Program end

The solutions found (with slack) can be decrypted and displayed using the auxiliary program sol:

# ./sol opt/showcases/simple.sol

x = [ 2 0 2 ] Target values: [ 8→10 20→20 32→30 ] Target Norm: 4 Slack Norm: 4 Found after: 1 sec(s) --- x = [ 1 2 1 ] Target values: [ 8→10 20→20 32→30 ] Target Norm: 4 Slack Norm: 4 Found after: 1 sec(s) --- x = [ 0 4 0 ] Target values: [ 8→10 20→20 32→30 ] Target Norm: 4 Slack Norm: 4 Found after: 3 sec(s)

Command-line parameters

This section provides an overview of the command-line parameters of 0ptX . They allow you to control termination behavior and enable or disable various algorithms to facilitate the search for solutions.

The following list specifies each parameter's name, type, possible values, default value and effect:

help	integer	0, 1	0
Lists all command-line parameters and describes their effects.

verb	integer	0, 1, 2	0
Normally, no status messages are displayed at runtime. To obtain statistical information after each main-loop iteration, set this option to 1. To display information that also reflects the status of the various program functions, set the value to 2.

The next setting can be used to prevent program termination caused by numerical accuracy issues:

consistency	integer	0, 1	0
At various points in the program, this checks whether the current lattice agrees with the transformation of the original lattice. If calculation or precision errors occur, it is advisable to set this parameter to 1. This allows inconsistencies in the calculation process to be detected and eliminated at an early stage. However, since these checks also affect runtime, they are disabled by default.

The core method for finding short lattice vectors is an enumeration procedure that operates on blocks of basis vectors to identify the shortest lattice vectors within them. The following parameters allow you to control this enumeration method.

eenum	integer	0, 1	1
Enumeration is enabled by default to find short lattice vectors. You should normally not disable it. If you want to influence the runtime of the enumeration step, experiment with the next four parameters instead.

beta	integer	≥ 2	20
This sets the block size used by the enumeration procedure.

eprune	integer	1, 2, 3	3
If further improvements are unlikely during the subsequent enumeration, this parameter determines how aggressively enumeration trees are pruned. The higher the value, the more frequently and extensively pruning is performed.

btime	integer	≥ 0	0
This parameter determines the maximum number of seconds allowed for enumerating a block. Once the time limit is reached, enumeration is terminated and a final LLL reduction is performed. The program itself is not terminated; only the runtime allocated to enumeration is controlled.

deep	integer	≥ 0	0
A value of 0 means that the LLL variant with deep insertions is used. The value of deep specifies how many vectors the Lovász step is extended to.

In addition to the enumeration procedure, which can implicitly search only for short lattice vectors, heuristic procedures are also used to represent the actual requirements for a solution more accurately.

collectLimit	integer	≥ 0	1000
During execution, lattice vectors with good heuristic scores are collected. This parameter determines the size of this collection. The following heuristic methods then select vectors from this collection as part of their selection processes.

pair	integer	0, 1	1
Enables a routine that combines pairs of lattice vectors with good heuristic scores and checks whether the resulting vector has a better score than either of the input vectors. If so, the result is added to the collection of heuristically well-rated lattice vectors. Pairwise reductions are always performed by default and can be disabled by setting the value to 0.

pairLimit	integer	≥ 0	10
This sets the maximum number of vectors selected from the pairwise reduction collection of heuristically well-rated lattice vectors for recombination during each call.

sieve	integer	0, 1	0
To find lattice vectors with good heuristic scores, the collection of heuristically well-rated lattice vectors is subjected to a sieve procedure. The result is then merged with the collection, which is subsequently reduced to the maximum permitted size. Set the value to 1 to enable this procedure.

The next two parameters control a mechanism for generating lattice vectors at random.

sample	integer	0, 1	0
Enables a sampling procedure that generates randomly distributed lattice vectors and, where appropriate, adds them to the collection of heuristically well-rated lattice vectors. This procedure is disabled by default.

sampleLimit	integer	≥ 0	1000
The maximum number of vectors generated per sampling call.

The following two parameters facilitate finding feasible lattice vectors. However, this also reduces the likelihood of improving the current objective function sum. On the other hand, they can increase the effectiveness of pairwise reduction and the heuristic sieve procedure. These parameters are unset by default.

scale	integer	0, 1	0
If this parameter is set, the components of lattice vectors that have the greatest impact on the feasibility condition are scaled.

translate	integer	0, 1	0
If this parameter is set, the entire lattice is shifted in such a way that the components of lattice vectors that violate the feasibility condition most strongly are preferentially reduced.

In practice, the routines presented so far may become stuck after a while and fail to escape local minima. It is therefore occasionally necessary to introduce some variation. The following parameters are enabled by default but can be disabled by setting their value to 0.

reinsert	integer	0, 1	1
After each iteration, this routine inserts the best lattice vectors found so far into the lattice basis.

variate	integer	0, 1	1
This routine is activated if the objective function sum has not improved after a certain number of iterations. The basis vectors are then sorted in ascending order of size and randomly shuffled. The number of shuffling operations depends on the number of unsuccessful iterations: the more unsuccessful iterations, the more shuffling operations are performed.

The next three parameters are relevant to the termination behavior of 0ptX .

rtime	integer	≥ 0	0
This specifies the runtime in seconds after which the program is terminated. The parameter is initialized to 0 by default, which corresponds to an unlimited runtime.

iters	integer	≥ 0	0
This specifies the number of iterations after which the program is terminated. No limit is set by default.

sol	integer	≥ 0	1
If you prefer the program to terminate based on the number of solutions found, use this criterion. By default, the program terminates as soon as a solution is found. Set the value to 0 if no limit is desired.

The quality of the solutions found can be specified using the next two parameters.

snorm	real-valued	≥ 0	-1
What is the maximum slack deviation a feasible lattice vector may have in order to be listed as a solution?

tnorm	real-valued	≥ 0	-∞
What is the maximum objective function sum a feasible lattice vector may have in order to be listed as a solution?

The final parameter is intended for benchmarks and runtime comparisons:

bench	integer	0, 1	0
If this parameter is set, any existing lat or sol file is not read. The resulting data can therefore be used to compare the effectiveness of different parameter configurations.

Recommended parameter sets

The section concludes with a list of parameter combinations that have proven effective in practice.

--eenum=1 --sieve=0 --sample=0 --scale=0 --translate=0 (the default setting)
--eenum=1 --sieve=1 --sample=0 --scale=1 --translate=0
--eenum=0 --sieve=0 --sample=1 --scale=1 --translate=0
--eenum=0 --sieve=0 --sample=1 --scale=0 --translate=1
--eenum=1 --sieve=1 --sample=0 --scale=1 --translate=1
--eenum=1 --sieve=0 --sample=0 --scale=1 --translate=1

An AI-assisted parameter recommendation feature is currently under development. It will accept an opt file as input and return the most promising parameter combination for that file.

Videos

Privacy Contact Legal notice

User manual

Preface

Problems

Composition problems

Loading problem

Blending problem

Purchasing problems

Bundle problem

Inventory management problem

Sales problem

Capacity utilization problem

Production problem

Transportation problem

Logistics problem

Market allocation problem

Mathematical description

Software package

Brief description

Input formats

The opt format

Example (without an objective function)

Example (with one objective function)

Example (with two objective functions)

Example (with three objective functions)

Example (with mixed-integer solutions)

lp → opt

Program invocation

Usage

Command-­line parameters

Recommended parameter sets

Videos

Command-line parameters