-
Notifications
You must be signed in to change notification settings - Fork 0
/
1-soplex.Rmd
164 lines (126 loc) · 5.87 KB
/
1-soplex.Rmd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
# Using an LP solver
Linear programming problems are rarely solved by hand.
Problems from industrial applications often
have thousands (and sometimes millions) of variables and constraints.
Fortunately, there exist a number of commercial as well as open-source
solvers that can handle such large-scale problem. In this chapter,
we will take a look at one of them.
Before we do so, we introduce the CPLEX LP format which allows us
to specify linear programming problems in a way close to how we write them.
## CPLEX LP file format
A description of the CPLEX LP file format can be found
<a href="https://www.ibm.com/support/knowledgecenter/SS9UKU_12.5.0/com.ibm.cplex.zos.help/GettingStarted/topics/tutorials/InteractiveOptimizer/usingLPformat.html">here</a>.
However, it is perhaps easiest to illustrate with some examples.
Consider
\[\begin{array}{rrcrcrcrcl}
\min & x_1 & - & 2x_2 & +& x_3 & & & \\
\mbox{s.t.}
& x_1 & - & 2x_2 & + & x_3 & - & x_4 & \geq & 1 \\
& x_1 & + & x_2 & + & 2x_3 & - & 2x_4 & = & 3 \\
& & - & x_2 & + & 3 x_3 & - & 5x_4 & \leq & 7 \\
& & & & & x_3 & , & x_4 & \geq & 0.
\end{array}\]
The problem can be specified in LP format as follows:
min x_1 - 2x_2 + x_3
st
x_1 - 2x_2 + x_3 - x_4 >= 1
x_1 + x_2 + 2x_3 - 2x_4 = 3
- x_2 + 3x_3 - 5x_4 <= 7
bounds
x_1 free
x_2 free
end
Any variable that does not appear in the `bounds` section
is automatically assumed to be nonnegative.
## SoPlex
[SoPlex](http://soplex.zib.de/) is an open-source
linear programming solver. It is free for noncommercial use.
Binaries for Mac OS X and Windows are readily available for
[download](http://soplex.zib.de/#download).
One great feature of SoPlex is that it can return exact
rational solutions whereas most other solvers only return
solutions as floating-point numbers.
Suppose that the problem for the example at the beginning
is saved in LP format in an ASCII file named `eg.lp`.
The following is the output of running SoPlex in a macOS
command-line terminal:
bash-3.2$ ./soplex-2.2.1.darwin.x86_64.gnu.opt -X --solvemode=2 -f=0 -o=0 eg.lp
SoPlex version 2.2.1 [mode: optimized] [precision: 8 byte] [rational: GMP 6.0.0] [githash: 267a44a]
Copyright (c) 1996-2016 Konrad-Zuse-Zentrum fuer Informationstechnik Berlin (ZIB)
int:solvemode = 2
real:feastol = 0
real:opttol = 0
Reading (real) LP file <eg.lp> . . .
Reading took 0.00 seconds.
LP has 3 rows 4 columns and 11 nonzeros.
Initial floating-point solve . . .
Simplifier removed 0 rows, 0 columns, 0 nonzeros, 0 col bounds, 0 row bounds
Reduced LP has 3 rows 4 columns 11 nonzeros
Equilibrium scaling LP
type | time | iters | facts | shift |violation | value
L | 0.0 | 0 | 1 | 4.00e+00 | 2.00e+00 | 0.00000000e+00
E | 0.0 | 1 | 2 | 0.00e+00 | 4.00e+00 | 3.00000000e+00
E | 0.0 | 2 | 3 | 0.00e+00 | 0.00e+00 | 1.00000000e+00
Floating-point optimal.
Max. bound violation = 0
Max. row violation = 1/4503599627370496
Max. reduced cost violation = 0
Max. dual violation = 0
Performing rational reconstruction . . .
Tolerances reached.
Solved to optimality.
SoPlex status : problem is solved [optimal]
Solving time (sec) : 0.00
Iterations : 2
Objective value : 1.00000000e+00
Primal solution (name, value):
x_1 7/3
x_2 2/3
All other variables are zero.
bash-3.2$
The option `-X` asks the solver to display the primal rational
solution.
The options `--solvemode=2` invokes iterative refinement for
solving for a rational solution. The options `-f=0 -o=0`
set the primal feasibility and dual feasibility tolerances to 0. Without
these options, one might get only approximate solutions to the problem.
If we remove the last three options and replace `-X`
with `-x`, we obtain the following instead:
bash-3.2$ ./soplex-2.2.1.darwin.x86_64.gnu.opt -x eg.lp
SoPlex version 2.2.1 [mode: optimized] [precision: 8 byte] [rational: GMP 6.0.0] [githash: 267a44a]
Copyright (c) 1996-2016 Konrad-Zuse-Zentrum fuer Informationstechnik Berlin (ZIB)
Reading (real) LP file <eg.lp> . . .
Reading took 0.00 seconds.
LP has 3 rows 4 columns and 11 nonzeros.
Simplifier removed 0 rows, 0 columns, 0 nonzeros, 0 col bounds, 0 row bounds
Reduced LP has 3 rows 4 columns 11 nonzeros
Equilibrium scaling LP
type | time | iters | facts | shift |violation | value
L | 0.0 | 0 | 1 | 4.00e+00 | 2.00e+00 | 0.00000000e+00
E | 0.0 | 1 | 2 | 0.00e+00 | 4.00e+00 | 3.00000000e+00
E | 0.0 | 2 | 3 | 0.00e+00 | 0.00e+00 | 1.00000000e+00
--- transforming basis into original space
L | 0.0 | 0 | 1 | 0.00e+00 | 0.00e+00 | 1.00000000e+00
L | 0.0 | 0 | 1 | 0.00e+00 | 0.00e+00 | 1.00000000e+00
SoPlex status : problem is solved [optimal]
Solving time (sec) : 0.00
Iterations : 2
Objective value : 1.00000000e+00
Primal solution (name, value):
x_1 2.333333333
x_2 0.666666667
All other variables are zero (within 1.0e-16).
bash-3.2$
There are many solver options that one can specify.
To view the list of all the options,
simply run the solver without options and arguments.
## NEOS server for optimization
If one does not want to download and install SoPlex,
one can use the [NEOS server for optimization][Neos].
In addition to SoPlex, there are many other solvers to choose
from.
To solve a linear programming problem using
SoPlex on the NEOS server, one can submit a file in CPLEX LP format
[here][NeosSoPlex].
[Neos]: https://neos-server.org/neos/solvers/index.html
[NeosSoPlex]: https://neos-server.org/neos/solvers/lp:SoPlex80bit/LP.html