1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 package org.apache.commons.math.optimization.linear;
19
20 import static org.junit.Assert.assertEquals;
21
22 import java.util.ArrayList;
23 import java.util.Collection;
24
25 import org.apache.commons.math.linear.RealVector;
26 import org.apache.commons.math.linear.ArrayRealVector;
27 import org.apache.commons.math.optimization.GoalType;
28 import org.apache.commons.math.optimization.OptimizationException;
29 import org.apache.commons.math.optimization.RealPointValuePair;
30 import org.junit.Test;
31
32 public class SimplexSolverTest {
33
34 @Test
35 public void testMath272() throws OptimizationException {
36 LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 2, 2, 1 }, 0);
37 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
38 constraints.add(new LinearConstraint(new double[] { 1, 1, 0 }, Relationship.GEQ, 1));
39 constraints.add(new LinearConstraint(new double[] { 1, 0, 1 }, Relationship.GEQ, 1));
40 constraints.add(new LinearConstraint(new double[] { 0, 1, 0 }, Relationship.GEQ, 1));
41
42 SimplexSolver solver = new SimplexSolver();
43 RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MINIMIZE, true);
44
45 assertEquals(0.0, solution.getPoint()[0], .0000001);
46 assertEquals(1.0, solution.getPoint()[1], .0000001);
47 assertEquals(1.0, solution.getPoint()[2], .0000001);
48 assertEquals(3.0, solution.getValue(), .0000001);
49 }
50
51 @Test
52 public void testSimplexSolver() throws OptimizationException {
53 LinearObjectiveFunction f =
54 new LinearObjectiveFunction(new double[] { 15, 10 }, 7);
55 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
56 constraints.add(new LinearConstraint(new double[] { 1, 0 }, Relationship.LEQ, 2));
57 constraints.add(new LinearConstraint(new double[] { 0, 1 }, Relationship.LEQ, 3));
58 constraints.add(new LinearConstraint(new double[] { 1, 1 }, Relationship.EQ, 4));
59
60 SimplexSolver solver = new SimplexSolver();
61 RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
62 assertEquals(2.0, solution.getPoint()[0], 0.0);
63 assertEquals(2.0, solution.getPoint()[1], 0.0);
64 assertEquals(57.0, solution.getValue(), 0.0);
65 }
66
67 @Test
68 public void testSingleVariableAndConstraint() throws OptimizationException {
69 LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 3 }, 0);
70 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
71 constraints.add(new LinearConstraint(new double[] { 1 }, Relationship.LEQ, 10));
72
73 SimplexSolver solver = new SimplexSolver();
74 RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
75 assertEquals(10.0, solution.getPoint()[0], 0.0);
76 assertEquals(30.0, solution.getValue(), 0.0);
77 }
78
79
80
81
82
83 @Test
84 public void testModelWithNoArtificialVars() throws OptimizationException {
85 LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 15, 10 }, 0);
86 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
87 constraints.add(new LinearConstraint(new double[] { 1, 0 }, Relationship.LEQ, 2));
88 constraints.add(new LinearConstraint(new double[] { 0, 1 }, Relationship.LEQ, 3));
89 constraints.add(new LinearConstraint(new double[] { 1, 1 }, Relationship.LEQ, 4));
90
91 SimplexSolver solver = new SimplexSolver();
92 RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
93 assertEquals(2.0, solution.getPoint()[0], 0.0);
94 assertEquals(2.0, solution.getPoint()[1], 0.0);
95 assertEquals(50.0, solution.getValue(), 0.0);
96 }
97
98 @Test
99 public void testMinimization() throws OptimizationException {
100 LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { -2, 1 }, -5);
101 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
102 constraints.add(new LinearConstraint(new double[] { 1, 2 }, Relationship.LEQ, 6));
103 constraints.add(new LinearConstraint(new double[] { 3, 2 }, Relationship.LEQ, 12));
104 constraints.add(new LinearConstraint(new double[] { 0, 1 }, Relationship.GEQ, 0));
105
106 SimplexSolver solver = new SimplexSolver();
107 RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MINIMIZE, false);
108 assertEquals(4.0, solution.getPoint()[0], 0.0);
109 assertEquals(0.0, solution.getPoint()[1], 0.0);
110 assertEquals(-13.0, solution.getValue(), 0.0);
111 }
112
113 @Test
114 public void testSolutionWithNegativeDecisionVariable() throws OptimizationException {
115 LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { -2, 1 }, 0);
116 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
117 constraints.add(new LinearConstraint(new double[] { 1, 1 }, Relationship.GEQ, 6));
118 constraints.add(new LinearConstraint(new double[] { 1, 2 }, Relationship.LEQ, 14));
119
120 SimplexSolver solver = new SimplexSolver();
121 RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
122 assertEquals(-2.0, solution.getPoint()[0], 0.0);
123 assertEquals(8.0, solution.getPoint()[1], 0.0);
124 assertEquals(12.0, solution.getValue(), 0.0);
125 }
126
127 @Test(expected = NoFeasibleSolutionException.class)
128 public void testInfeasibleSolution() throws OptimizationException {
129 LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 15 }, 0);
130 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
131 constraints.add(new LinearConstraint(new double[] { 1 }, Relationship.LEQ, 1));
132 constraints.add(new LinearConstraint(new double[] { 1 }, Relationship.GEQ, 3));
133
134 SimplexSolver solver = new SimplexSolver();
135 solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
136 }
137
138 @Test(expected = UnboundedSolutionException.class)
139 public void testUnboundedSolution() throws OptimizationException {
140 LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 15, 10 }, 0);
141 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
142 constraints.add(new LinearConstraint(new double[] { 1, 0 }, Relationship.EQ, 2));
143
144 SimplexSolver solver = new SimplexSolver();
145 solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
146 }
147
148 @Test
149 public void testRestrictVariablesToNonNegative() throws OptimizationException {
150 LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 409, 523, 70, 204, 339 }, 0);
151 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
152 constraints.add(new LinearConstraint(new double[] { 43, 56, 345, 56, 5 }, Relationship.LEQ, 4567456));
153 constraints.add(new LinearConstraint(new double[] { 12, 45, 7, 56, 23 }, Relationship.LEQ, 56454));
154 constraints.add(new LinearConstraint(new double[] { 8, 768, 0, 34, 7456 }, Relationship.LEQ, 1923421));
155 constraints.add(new LinearConstraint(new double[] { 12342, 2342, 34, 678, 2342 }, Relationship.GEQ, 4356));
156 constraints.add(new LinearConstraint(new double[] { 45, 678, 76, 52, 23 }, Relationship.EQ, 456356));
157
158 SimplexSolver solver = new SimplexSolver();
159 RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, true);
160 assertEquals(2902.92783505155, solution.getPoint()[0], .0000001);
161 assertEquals(480.419243986254, solution.getPoint()[1], .0000001);
162 assertEquals(0.0, solution.getPoint()[2], .0000001);
163 assertEquals(0.0, solution.getPoint()[3], .0000001);
164 assertEquals(0.0, solution.getPoint()[4], .0000001);
165 assertEquals(1438556.7491409, solution.getValue(), .0000001);
166 }
167
168 @Test
169 public void testEpsilon() throws OptimizationException {
170 LinearObjectiveFunction f =
171 new LinearObjectiveFunction(new double[] { 10, 5, 1 }, 0);
172 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
173 constraints.add(new LinearConstraint(new double[] { 9, 8, 0 }, Relationship.EQ, 17));
174 constraints.add(new LinearConstraint(new double[] { 0, 7, 8 }, Relationship.LEQ, 7));
175 constraints.add(new LinearConstraint(new double[] { 10, 0, 2 }, Relationship.LEQ, 10));
176
177 SimplexSolver solver = new SimplexSolver();
178 RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
179 assertEquals(1.0, solution.getPoint()[0], 0.0);
180 assertEquals(1.0, solution.getPoint()[1], 0.0);
181 assertEquals(0.0, solution.getPoint()[2], 0.0);
182 assertEquals(15.0, solution.getValue(), 0.0);
183 }
184
185 @Test
186 public void testTrivialModel() throws OptimizationException {
187 LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 1, 1 }, 0);
188 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
189 constraints.add(new LinearConstraint(new double[] { 1, 1 }, Relationship.EQ, 0));
190
191 SimplexSolver solver = new SimplexSolver();
192 RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, true);
193 assertEquals(0, solution.getValue(), .0000001);
194 }
195
196 @Test
197 public void testLargeModel() throws OptimizationException {
198 double[] objective = new double[] {
199 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
200 1, 1, 12, 1, 1, 1, 1, 1, 1, 1,
201 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
202 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
203 12, 1, 1, 1, 1, 1, 1, 1, 1, 1,
204 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
205 1, 1, 1, 1, 1, 1, 1, 1, 12, 1,
206 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
207 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
208 1, 1, 1, 1, 1, 1, 12, 1, 1, 1,
209 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
210 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
211 1, 1, 1, 1, 12, 1, 1, 1, 1, 1,
212 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
213 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
214 1, 1, 12, 1, 1, 1, 1, 1, 1, 1,
215 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
216 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
217 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
218 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
219 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
220 1, 1, 1, 1, 1, 1};
221
222 LinearObjectiveFunction f = new LinearObjectiveFunction(objective, 0);
223 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
224 constraints.add(equationFromString(objective.length, "x0 + x1 + x2 + x3 - x12 = 0"));
225 constraints.add(equationFromString(objective.length, "x4 + x5 + x6 + x7 + x8 + x9 + x10 + x11 - x13 = 0"));
226 constraints.add(equationFromString(objective.length, "x4 + x5 + x6 + x7 + x8 + x9 + x10 + x11 >= 49"));
227 constraints.add(equationFromString(objective.length, "x0 + x1 + x2 + x3 >= 42"));
228 constraints.add(equationFromString(objective.length, "x14 + x15 + x16 + x17 - x26 = 0"));
229 constraints.add(equationFromString(objective.length, "x18 + x19 + x20 + x21 + x22 + x23 + x24 + x25 - x27 = 0"));
230 constraints.add(equationFromString(objective.length, "x14 + x15 + x16 + x17 - x12 = 0"));
231 constraints.add(equationFromString(objective.length, "x18 + x19 + x20 + x21 + x22 + x23 + x24 + x25 - x13 = 0"));
232 constraints.add(equationFromString(objective.length, "x28 + x29 + x30 + x31 - x40 = 0"));
233 constraints.add(equationFromString(objective.length, "x32 + x33 + x34 + x35 + x36 + x37 + x38 + x39 - x41 = 0"));
234 constraints.add(equationFromString(objective.length, "x32 + x33 + x34 + x35 + x36 + x37 + x38 + x39 >= 49"));
235 constraints.add(equationFromString(objective.length, "x28 + x29 + x30 + x31 >= 42"));
236 constraints.add(equationFromString(objective.length, "x42 + x43 + x44 + x45 - x54 = 0"));
237 constraints.add(equationFromString(objective.length, "x46 + x47 + x48 + x49 + x50 + x51 + x52 + x53 - x55 = 0"));
238 constraints.add(equationFromString(objective.length, "x42 + x43 + x44 + x45 - x40 = 0"));
239 constraints.add(equationFromString(objective.length, "x46 + x47 + x48 + x49 + x50 + x51 + x52 + x53 - x41 = 0"));
240 constraints.add(equationFromString(objective.length, "x56 + x57 + x58 + x59 - x68 = 0"));
241 constraints.add(equationFromString(objective.length, "x60 + x61 + x62 + x63 + x64 + x65 + x66 + x67 - x69 = 0"));
242 constraints.add(equationFromString(objective.length, "x60 + x61 + x62 + x63 + x64 + x65 + x66 + x67 >= 51"));
243 constraints.add(equationFromString(objective.length, "x56 + x57 + x58 + x59 >= 44"));
244 constraints.add(equationFromString(objective.length, "x70 + x71 + x72 + x73 - x82 = 0"));
245 constraints.add(equationFromString(objective.length, "x74 + x75 + x76 + x77 + x78 + x79 + x80 + x81 - x83 = 0"));
246 constraints.add(equationFromString(objective.length, "x70 + x71 + x72 + x73 - x68 = 0"));
247 constraints.add(equationFromString(objective.length, "x74 + x75 + x76 + x77 + x78 + x79 + x80 + x81 - x69 = 0"));
248 constraints.add(equationFromString(objective.length, "x84 + x85 + x86 + x87 - x96 = 0"));
249 constraints.add(equationFromString(objective.length, "x88 + x89 + x90 + x91 + x92 + x93 + x94 + x95 - x97 = 0"));
250 constraints.add(equationFromString(objective.length, "x88 + x89 + x90 + x91 + x92 + x93 + x94 + x95 >= 51"));
251 constraints.add(equationFromString(objective.length, "x84 + x85 + x86 + x87 >= 44"));
252 constraints.add(equationFromString(objective.length, "x98 + x99 + x100 + x101 - x110 = 0"));
253 constraints.add(equationFromString(objective.length, "x102 + x103 + x104 + x105 + x106 + x107 + x108 + x109 - x111 = 0"));
254 constraints.add(equationFromString(objective.length, "x98 + x99 + x100 + x101 - x96 = 0"));
255 constraints.add(equationFromString(objective.length, "x102 + x103 + x104 + x105 + x106 + x107 + x108 + x109 - x97 = 0"));
256 constraints.add(equationFromString(objective.length, "x112 + x113 + x114 + x115 - x124 = 0"));
257 constraints.add(equationFromString(objective.length, "x116 + x117 + x118 + x119 + x120 + x121 + x122 + x123 - x125 = 0"));
258 constraints.add(equationFromString(objective.length, "x116 + x117 + x118 + x119 + x120 + x121 + x122 + x123 >= 49"));
259 constraints.add(equationFromString(objective.length, "x112 + x113 + x114 + x115 >= 42"));
260 constraints.add(equationFromString(objective.length, "x126 + x127 + x128 + x129 - x138 = 0"));
261 constraints.add(equationFromString(objective.length, "x130 + x131 + x132 + x133 + x134 + x135 + x136 + x137 - x139 = 0"));
262 constraints.add(equationFromString(objective.length, "x126 + x127 + x128 + x129 - x124 = 0"));
263 constraints.add(equationFromString(objective.length, "x130 + x131 + x132 + x133 + x134 + x135 + x136 + x137 - x125 = 0"));
264 constraints.add(equationFromString(objective.length, "x140 + x141 + x142 + x143 - x152 = 0"));
265 constraints.add(equationFromString(objective.length, "x144 + x145 + x146 + x147 + x148 + x149 + x150 + x151 - x153 = 0"));
266 constraints.add(equationFromString(objective.length, "x144 + x145 + x146 + x147 + x148 + x149 + x150 + x151 >= 59"));
267 constraints.add(equationFromString(objective.length, "x140 + x141 + x142 + x143 >= 42"));
268 constraints.add(equationFromString(objective.length, "x154 + x155 + x156 + x157 - x166 = 0"));
269 constraints.add(equationFromString(objective.length, "x158 + x159 + x160 + x161 + x162 + x163 + x164 + x165 - x167 = 0"));
270 constraints.add(equationFromString(objective.length, "x154 + x155 + x156 + x157 - x152 = 0"));
271 constraints.add(equationFromString(objective.length, "x158 + x159 + x160 + x161 + x162 + x163 + x164 + x165 - x153 = 0"));
272 constraints.add(equationFromString(objective.length, "x83 + x82 - x168 = 0"));
273 constraints.add(equationFromString(objective.length, "x111 + x110 - x169 = 0"));
274 constraints.add(equationFromString(objective.length, "x170 - x182 = 0"));
275 constraints.add(equationFromString(objective.length, "x171 - x183 = 0"));
276 constraints.add(equationFromString(objective.length, "x172 - x184 = 0"));
277 constraints.add(equationFromString(objective.length, "x173 - x185 = 0"));
278 constraints.add(equationFromString(objective.length, "x174 - x186 = 0"));
279 constraints.add(equationFromString(objective.length, "x175 + x176 - x187 = 0"));
280 constraints.add(equationFromString(objective.length, "x177 - x188 = 0"));
281 constraints.add(equationFromString(objective.length, "x178 - x189 = 0"));
282 constraints.add(equationFromString(objective.length, "x179 - x190 = 0"));
283 constraints.add(equationFromString(objective.length, "x180 - x191 = 0"));
284 constraints.add(equationFromString(objective.length, "x181 - x192 = 0"));
285 constraints.add(equationFromString(objective.length, "x170 - x26 = 0"));
286 constraints.add(equationFromString(objective.length, "x171 - x27 = 0"));
287 constraints.add(equationFromString(objective.length, "x172 - x54 = 0"));
288 constraints.add(equationFromString(objective.length, "x173 - x55 = 0"));
289 constraints.add(equationFromString(objective.length, "x174 - x168 = 0"));
290 constraints.add(equationFromString(objective.length, "x177 - x169 = 0"));
291 constraints.add(equationFromString(objective.length, "x178 - x138 = 0"));
292 constraints.add(equationFromString(objective.length, "x179 - x139 = 0"));
293 constraints.add(equationFromString(objective.length, "x180 - x166 = 0"));
294 constraints.add(equationFromString(objective.length, "x181 - x167 = 0"));
295 constraints.add(equationFromString(objective.length, "x193 - x205 = 0"));
296 constraints.add(equationFromString(objective.length, "x194 - x206 = 0"));
297 constraints.add(equationFromString(objective.length, "x195 - x207 = 0"));
298 constraints.add(equationFromString(objective.length, "x196 - x208 = 0"));
299 constraints.add(equationFromString(objective.length, "x197 - x209 = 0"));
300 constraints.add(equationFromString(objective.length, "x198 + x199 - x210 = 0"));
301 constraints.add(equationFromString(objective.length, "x200 - x211 = 0"));
302 constraints.add(equationFromString(objective.length, "x201 - x212 = 0"));
303 constraints.add(equationFromString(objective.length, "x202 - x213 = 0"));
304 constraints.add(equationFromString(objective.length, "x203 - x214 = 0"));
305 constraints.add(equationFromString(objective.length, "x204 - x215 = 0"));
306 constraints.add(equationFromString(objective.length, "x193 - x182 = 0"));
307 constraints.add(equationFromString(objective.length, "x194 - x183 = 0"));
308 constraints.add(equationFromString(objective.length, "x195 - x184 = 0"));
309 constraints.add(equationFromString(objective.length, "x196 - x185 = 0"));
310 constraints.add(equationFromString(objective.length, "x197 - x186 = 0"));
311 constraints.add(equationFromString(objective.length, "x198 + x199 - x187 = 0"));
312 constraints.add(equationFromString(objective.length, "x200 - x188 = 0"));
313 constraints.add(equationFromString(objective.length, "x201 - x189 = 0"));
314 constraints.add(equationFromString(objective.length, "x202 - x190 = 0"));
315 constraints.add(equationFromString(objective.length, "x203 - x191 = 0"));
316 constraints.add(equationFromString(objective.length, "x204 - x192 = 0"));
317
318 SimplexSolver solver = new SimplexSolver();
319 RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MINIMIZE, true);
320 assertEquals(7518.0, solution.getValue(), .0000001);
321 }
322
323
324
325
326
327 private LinearConstraint equationFromString(int numCoefficients, String s) {
328 Relationship relationship;
329 if (s.contains(">=")) {
330 relationship = Relationship.GEQ;
331 } else if (s.contains("<=")) {
332 relationship = Relationship.LEQ;
333 } else if (s.contains("=")) {
334 relationship = Relationship.EQ;
335 } else {
336 throw new IllegalArgumentException();
337 }
338
339 String[] equationParts = s.split("[>|<]?=");
340 double rhs = Double.parseDouble(equationParts[1].trim());
341
342 RealVector lhs = new ArrayRealVector(numCoefficients);
343 String left = equationParts[0].replaceAll(" ?x", "");
344 String[] coefficients = left.split(" ");
345 for (String coefficient : coefficients) {
346 double value = coefficient.charAt(0) == '-' ? -1 : 1;
347 int index = Integer.parseInt(coefficient.replaceFirst("[+|-]", "").trim());
348 lhs.setEntry(index, value);
349 }
350 return new LinearConstraint(lhs, relationship, rhs);
351 }
352
353 }