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 org.junit.Assert;
21
22 import java.util.ArrayList;
23 import java.util.Collection;
24
25 import org.apache.commons.math.optimization.GoalType;
26 import org.apache.commons.math.optimization.RealPointValuePair;
27 import org.apache.commons.math.util.Precision;
28 import org.junit.Test;
29
30 public class SimplexSolverTest {
31
32 @Test
33 public void testMath434NegativeVariable() {
34 LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] {0.0, 0.0, 1.0}, 0.0d);
35 ArrayList<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
36 constraints.add(new LinearConstraint(new double[] {1, 1, 0}, Relationship.EQ, 5));
37 constraints.add(new LinearConstraint(new double[] {0, 0, 1}, Relationship.GEQ, -10));
38
39 double epsilon = 1e-6;
40 SimplexSolver solver = new SimplexSolver();
41 RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MINIMIZE, false);
42
43 Assert.assertEquals(5.0, solution.getPoint()[0] + solution.getPoint()[1], epsilon);
44 Assert.assertEquals(-10.0, solution.getPoint()[2], epsilon);
45 Assert.assertEquals(-10.0, solution.getValue(), epsilon);
46
47 }
48
49 @Test(expected = NoFeasibleSolutionException.class)
50 public void testMath434UnfeasibleSolution() {
51 double epsilon = 1e-6;
52
53 LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] {1.0, 0.0}, 0.0);
54 ArrayList<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
55 constraints.add(new LinearConstraint(new double[] {epsilon/2, 0.5}, Relationship.EQ, 0));
56 constraints.add(new LinearConstraint(new double[] {1e-3, 0.1}, Relationship.EQ, 10));
57
58 SimplexSolver solver = new SimplexSolver();
59
60 solver.optimize(f, constraints, GoalType.MINIMIZE, true);
61 }
62
63 @Test
64 public void testMath434PivotRowSelection() {
65 LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] {1.0}, 0.0);
66
67 double epsilon = 1e-6;
68 ArrayList<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
69 constraints.add(new LinearConstraint(new double[] {200}, Relationship.GEQ, 1));
70 constraints.add(new LinearConstraint(new double[] {100}, Relationship.GEQ, 0.499900001));
71
72 SimplexSolver solver = new SimplexSolver();
73 RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MINIMIZE, false);
74
75 Assert.assertTrue(Precision.compareTo(solution.getPoint()[0] * 200.d, 1.d, epsilon) >= 0);
76 Assert.assertEquals(0.0050, solution.getValue(), epsilon);
77 }
78
79 @Test
80 public void testMath434PivotRowSelection2() {
81 LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] {0.0d, 1.0d, 1.0d, 0.0d, 0.0d, 0.0d, 0.0d}, 0.0d);
82
83 ArrayList<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
84 constraints.add(new LinearConstraint(new double[] {1.0d, -0.1d, 0.0d, 0.0d, 0.0d, 0.0d, 0.0d}, Relationship.EQ, -0.1d));
85 constraints.add(new LinearConstraint(new double[] {1.0d, 0.0d, 0.0d, 0.0d, 0.0d, 0.0d, 0.0d}, Relationship.GEQ, -1e-18d));
86 constraints.add(new LinearConstraint(new double[] {0.0d, 1.0d, 0.0d, 0.0d, 0.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d));
87 constraints.add(new LinearConstraint(new double[] {0.0d, 0.0d, 0.0d, 1.0d, 0.0d, -0.0128588d, 1e-5d}, Relationship.EQ, 0.0d));
88 constraints.add(new LinearConstraint(new double[] {0.0d, 0.0d, 0.0d, 0.0d, 1.0d, 1e-5d, -0.0128586d}, Relationship.EQ, 1e-10d));
89 constraints.add(new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, -1.0d, 0.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d));
90 constraints.add(new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 1.0d, 0.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d));
91 constraints.add(new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 0.0d, -1.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d));
92 constraints.add(new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 0.0d, 1.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d));
93
94 double epsilon = 1e-7;
95 SimplexSolver simplex = new SimplexSolver();
96 RealPointValuePair solution = simplex.optimize(f, constraints, GoalType.MINIMIZE, false);
97
98 Assert.assertTrue(Precision.compareTo(solution.getPoint()[0], -1e-18d, epsilon) >= 0);
99 Assert.assertEquals(1.0d, solution.getPoint()[1], epsilon);
100 Assert.assertEquals(0.0d, solution.getPoint()[2], epsilon);
101 Assert.assertEquals(1.0d, solution.getValue(), epsilon);
102 }
103
104 @Test
105 public void testMath272() {
106 LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 2, 2, 1 }, 0);
107 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
108 constraints.add(new LinearConstraint(new double[] { 1, 1, 0 }, Relationship.GEQ, 1));
109 constraints.add(new LinearConstraint(new double[] { 1, 0, 1 }, Relationship.GEQ, 1));
110 constraints.add(new LinearConstraint(new double[] { 0, 1, 0 }, Relationship.GEQ, 1));
111
112 SimplexSolver solver = new SimplexSolver();
113 RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MINIMIZE, true);
114
115 Assert.assertEquals(0.0, solution.getPoint()[0], .0000001);
116 Assert.assertEquals(1.0, solution.getPoint()[1], .0000001);
117 Assert.assertEquals(1.0, solution.getPoint()[2], .0000001);
118 Assert.assertEquals(3.0, solution.getValue(), .0000001);
119 }
120
121 @Test
122 public void testMath286() {
123 LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 0.8, 0.2, 0.7, 0.3, 0.6, 0.4 }, 0 );
124 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
125 constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0, 1, 0 }, Relationship.EQ, 23.0));
126 constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1, 0, 1 }, Relationship.EQ, 23.0));
127 constraints.add(new LinearConstraint(new double[] { 1, 0, 0, 0, 0, 0 }, Relationship.GEQ, 10.0));
128 constraints.add(new LinearConstraint(new double[] { 0, 0, 1, 0, 0, 0 }, Relationship.GEQ, 8.0));
129 constraints.add(new LinearConstraint(new double[] { 0, 0, 0, 0, 1, 0 }, Relationship.GEQ, 5.0));
130
131 SimplexSolver solver = new SimplexSolver();
132 RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, true);
133
134 Assert.assertEquals(25.8, solution.getValue(), .0000001);
135 Assert.assertEquals(23.0, solution.getPoint()[0] + solution.getPoint()[2] + solution.getPoint()[4], 0.0000001);
136 Assert.assertEquals(23.0, solution.getPoint()[1] + solution.getPoint()[3] + solution.getPoint()[5], 0.0000001);
137 Assert.assertTrue(solution.getPoint()[0] >= 10.0 - 0.0000001);
138 Assert.assertTrue(solution.getPoint()[2] >= 8.0 - 0.0000001);
139 Assert.assertTrue(solution.getPoint()[4] >= 5.0 - 0.0000001);
140 }
141
142 @Test
143 public void testDegeneracy() {
144 LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 0.8, 0.7 }, 0 );
145 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
146 constraints.add(new LinearConstraint(new double[] { 1, 1 }, Relationship.LEQ, 18.0));
147 constraints.add(new LinearConstraint(new double[] { 1, 0 }, Relationship.GEQ, 10.0));
148 constraints.add(new LinearConstraint(new double[] { 0, 1 }, Relationship.GEQ, 8.0));
149
150 SimplexSolver solver = new SimplexSolver();
151 RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, true);
152 Assert.assertEquals(13.6, solution.getValue(), .0000001);
153 }
154
155 @Test
156 public void testMath288() {
157 LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 7, 3, 0, 0 }, 0 );
158 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
159 constraints.add(new LinearConstraint(new double[] { 3, 0, -5, 0 }, Relationship.LEQ, 0.0));
160 constraints.add(new LinearConstraint(new double[] { 2, 0, 0, -5 }, Relationship.LEQ, 0.0));
161 constraints.add(new LinearConstraint(new double[] { 0, 3, 0, -5 }, Relationship.LEQ, 0.0));
162 constraints.add(new LinearConstraint(new double[] { 1, 0, 0, 0 }, Relationship.LEQ, 1.0));
163 constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 0 }, Relationship.LEQ, 1.0));
164
165 SimplexSolver solver = new SimplexSolver();
166 RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, true);
167 Assert.assertEquals(10.0, solution.getValue(), .0000001);
168 }
169
170 @Test
171 public void testMath290GEQ() {
172 LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 1, 5 }, 0 );
173 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
174 constraints.add(new LinearConstraint(new double[] { 2, 0 }, Relationship.GEQ, -1.0));
175 SimplexSolver solver = new SimplexSolver();
176 RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MINIMIZE, true);
177 Assert.assertEquals(0, solution.getValue(), .0000001);
178 Assert.assertEquals(0, solution.getPoint()[0], .0000001);
179 Assert.assertEquals(0, solution.getPoint()[1], .0000001);
180 }
181
182 @Test(expected=NoFeasibleSolutionException.class)
183 public void testMath290LEQ() {
184 LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 1, 5 }, 0 );
185 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
186 constraints.add(new LinearConstraint(new double[] { 2, 0 }, Relationship.LEQ, -1.0));
187 SimplexSolver solver = new SimplexSolver();
188 solver.optimize(f, constraints, GoalType.MINIMIZE, true);
189 }
190
191 @Test
192 public void testMath293() {
193 LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 0.8, 0.2, 0.7, 0.3, 0.4, 0.6}, 0 );
194 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
195 constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0, 1, 0 }, Relationship.EQ, 30.0));
196 constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1, 0, 1 }, Relationship.EQ, 30.0));
197 constraints.add(new LinearConstraint(new double[] { 0.8, 0.2, 0.0, 0.0, 0.0, 0.0 }, Relationship.GEQ, 10.0));
198 constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.7, 0.3, 0.0, 0.0 }, Relationship.GEQ, 10.0));
199 constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.0, 0.0, 0.4, 0.6 }, Relationship.GEQ, 10.0));
200
201 SimplexSolver solver = new SimplexSolver();
202 RealPointValuePair solution1 = solver.optimize(f, constraints, GoalType.MAXIMIZE, true);
203
204 Assert.assertEquals(15.7143, solution1.getPoint()[0], .0001);
205 Assert.assertEquals(0.0, solution1.getPoint()[1], .0001);
206 Assert.assertEquals(14.2857, solution1.getPoint()[2], .0001);
207 Assert.assertEquals(0.0, solution1.getPoint()[3], .0001);
208 Assert.assertEquals(0.0, solution1.getPoint()[4], .0001);
209 Assert.assertEquals(30.0, solution1.getPoint()[5], .0001);
210 Assert.assertEquals(40.57143, solution1.getValue(), .0001);
211
212 double valA = 0.8 * solution1.getPoint()[0] + 0.2 * solution1.getPoint()[1];
213 double valB = 0.7 * solution1.getPoint()[2] + 0.3 * solution1.getPoint()[3];
214 double valC = 0.4 * solution1.getPoint()[4] + 0.6 * solution1.getPoint()[5];
215
216 f = new LinearObjectiveFunction(new double[] { 0.8, 0.2, 0.7, 0.3, 0.4, 0.6}, 0 );
217 constraints = new ArrayList<LinearConstraint>();
218 constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0, 1, 0 }, Relationship.EQ, 30.0));
219 constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1, 0, 1 }, Relationship.EQ, 30.0));
220 constraints.add(new LinearConstraint(new double[] { 0.8, 0.2, 0.0, 0.0, 0.0, 0.0 }, Relationship.GEQ, valA));
221 constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.7, 0.3, 0.0, 0.0 }, Relationship.GEQ, valB));
222 constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.0, 0.0, 0.4, 0.6 }, Relationship.GEQ, valC));
223
224 RealPointValuePair solution2 = solver.optimize(f, constraints, GoalType.MAXIMIZE, true);
225 Assert.assertEquals(40.57143, solution2.getValue(), .0001);
226 }
227
228 @Test
229 public void testSimplexSolver() {
230 LinearObjectiveFunction f =
231 new LinearObjectiveFunction(new double[] { 15, 10 }, 7);
232 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
233 constraints.add(new LinearConstraint(new double[] { 1, 0 }, Relationship.LEQ, 2));
234 constraints.add(new LinearConstraint(new double[] { 0, 1 }, Relationship.LEQ, 3));
235 constraints.add(new LinearConstraint(new double[] { 1, 1 }, Relationship.EQ, 4));
236
237 SimplexSolver solver = new SimplexSolver();
238 RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
239 Assert.assertEquals(2.0, solution.getPoint()[0], 0.0);
240 Assert.assertEquals(2.0, solution.getPoint()[1], 0.0);
241 Assert.assertEquals(57.0, solution.getValue(), 0.0);
242 }
243
244 @Test
245 public void testSingleVariableAndConstraint() {
246 LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 3 }, 0);
247 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
248 constraints.add(new LinearConstraint(new double[] { 1 }, Relationship.LEQ, 10));
249
250 SimplexSolver solver = new SimplexSolver();
251 RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
252 Assert.assertEquals(10.0, solution.getPoint()[0], 0.0);
253 Assert.assertEquals(30.0, solution.getValue(), 0.0);
254 }
255
256
257
258
259
260 @Test
261 public void testModelWithNoArtificialVars() {
262 LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 15, 10 }, 0);
263 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
264 constraints.add(new LinearConstraint(new double[] { 1, 0 }, Relationship.LEQ, 2));
265 constraints.add(new LinearConstraint(new double[] { 0, 1 }, Relationship.LEQ, 3));
266 constraints.add(new LinearConstraint(new double[] { 1, 1 }, Relationship.LEQ, 4));
267
268 SimplexSolver solver = new SimplexSolver();
269 RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
270 Assert.assertEquals(2.0, solution.getPoint()[0], 0.0);
271 Assert.assertEquals(2.0, solution.getPoint()[1], 0.0);
272 Assert.assertEquals(50.0, solution.getValue(), 0.0);
273 }
274
275 @Test
276 public void testMinimization() {
277 LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { -2, 1 }, -5);
278 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
279 constraints.add(new LinearConstraint(new double[] { 1, 2 }, Relationship.LEQ, 6));
280 constraints.add(new LinearConstraint(new double[] { 3, 2 }, Relationship.LEQ, 12));
281 constraints.add(new LinearConstraint(new double[] { 0, 1 }, Relationship.GEQ, 0));
282
283 SimplexSolver solver = new SimplexSolver();
284 RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MINIMIZE, false);
285 Assert.assertEquals(4.0, solution.getPoint()[0], 0.0);
286 Assert.assertEquals(0.0, solution.getPoint()[1], 0.0);
287 Assert.assertEquals(-13.0, solution.getValue(), 0.0);
288 }
289
290 @Test
291 public void testSolutionWithNegativeDecisionVariable() {
292 LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { -2, 1 }, 0);
293 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
294 constraints.add(new LinearConstraint(new double[] { 1, 1 }, Relationship.GEQ, 6));
295 constraints.add(new LinearConstraint(new double[] { 1, 2 }, Relationship.LEQ, 14));
296
297 SimplexSolver solver = new SimplexSolver();
298 RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
299 Assert.assertEquals(-2.0, solution.getPoint()[0], 0.0);
300 Assert.assertEquals(8.0, solution.getPoint()[1], 0.0);
301 Assert.assertEquals(12.0, solution.getValue(), 0.0);
302 }
303
304 @Test(expected = NoFeasibleSolutionException.class)
305 public void testInfeasibleSolution() {
306 LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 15 }, 0);
307 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
308 constraints.add(new LinearConstraint(new double[] { 1 }, Relationship.LEQ, 1));
309 constraints.add(new LinearConstraint(new double[] { 1 }, Relationship.GEQ, 3));
310
311 SimplexSolver solver = new SimplexSolver();
312 solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
313 }
314
315 @Test(expected = UnboundedSolutionException.class)
316 public void testUnboundedSolution() {
317 LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 15, 10 }, 0);
318 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
319 constraints.add(new LinearConstraint(new double[] { 1, 0 }, Relationship.EQ, 2));
320
321 SimplexSolver solver = new SimplexSolver();
322 solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
323 }
324
325 @Test
326 public void testRestrictVariablesToNonNegative() {
327 LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 409, 523, 70, 204, 339 }, 0);
328 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
329 constraints.add(new LinearConstraint(new double[] { 43, 56, 345, 56, 5 }, Relationship.LEQ, 4567456));
330 constraints.add(new LinearConstraint(new double[] { 12, 45, 7, 56, 23 }, Relationship.LEQ, 56454));
331 constraints.add(new LinearConstraint(new double[] { 8, 768, 0, 34, 7456 }, Relationship.LEQ, 1923421));
332 constraints.add(new LinearConstraint(new double[] { 12342, 2342, 34, 678, 2342 }, Relationship.GEQ, 4356));
333 constraints.add(new LinearConstraint(new double[] { 45, 678, 76, 52, 23 }, Relationship.EQ, 456356));
334
335 SimplexSolver solver = new SimplexSolver();
336 RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, true);
337 Assert.assertEquals(2902.92783505155, solution.getPoint()[0], .0000001);
338 Assert.assertEquals(480.419243986254, solution.getPoint()[1], .0000001);
339 Assert.assertEquals(0.0, solution.getPoint()[2], .0000001);
340 Assert.assertEquals(0.0, solution.getPoint()[3], .0000001);
341 Assert.assertEquals(0.0, solution.getPoint()[4], .0000001);
342 Assert.assertEquals(1438556.7491409, solution.getValue(), .0000001);
343 }
344
345 @Test
346 public void testEpsilon() {
347 LinearObjectiveFunction f =
348 new LinearObjectiveFunction(new double[] { 10, 5, 1 }, 0);
349 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
350 constraints.add(new LinearConstraint(new double[] { 9, 8, 0 }, Relationship.EQ, 17));
351 constraints.add(new LinearConstraint(new double[] { 0, 7, 8 }, Relationship.LEQ, 7));
352 constraints.add(new LinearConstraint(new double[] { 10, 0, 2 }, Relationship.LEQ, 10));
353
354 SimplexSolver solver = new SimplexSolver();
355 RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
356 Assert.assertEquals(1.0, solution.getPoint()[0], 0.0);
357 Assert.assertEquals(1.0, solution.getPoint()[1], 0.0);
358 Assert.assertEquals(0.0, solution.getPoint()[2], 0.0);
359 Assert.assertEquals(15.0, solution.getValue(), 0.0);
360 }
361
362 @Test
363 public void testTrivialModel() {
364 LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 1, 1 }, 0);
365 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
366 constraints.add(new LinearConstraint(new double[] { 1, 1 }, Relationship.EQ, 0));
367
368 SimplexSolver solver = new SimplexSolver();
369 RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, true);
370 Assert.assertEquals(0, solution.getValue(), .0000001);
371 }
372
373 @Test
374 public void testLargeModel() {
375 double[] objective = new double[] {
376 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
377 1, 1, 12, 1, 1, 1, 1, 1, 1, 1,
378 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
379 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
380 12, 1, 1, 1, 1, 1, 1, 1, 1, 1,
381 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
382 1, 1, 1, 1, 1, 1, 1, 1, 12, 1,
383 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
384 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
385 1, 1, 1, 1, 1, 1, 12, 1, 1, 1,
386 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
387 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
388 1, 1, 1, 1, 12, 1, 1, 1, 1, 1,
389 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
390 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
391 1, 1, 12, 1, 1, 1, 1, 1, 1, 1,
392 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
393 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
394 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
395 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
396 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
397 1, 1, 1, 1, 1, 1};
398
399 LinearObjectiveFunction f = new LinearObjectiveFunction(objective, 0);
400 Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
401 constraints.add(equationFromString(objective.length, "x0 + x1 + x2 + x3 - x12 = 0"));
402 constraints.add(equationFromString(objective.length, "x4 + x5 + x6 + x7 + x8 + x9 + x10 + x11 - x13 = 0"));
403 constraints.add(equationFromString(objective.length, "x4 + x5 + x6 + x7 + x8 + x9 + x10 + x11 >= 49"));
404 constraints.add(equationFromString(objective.length, "x0 + x1 + x2 + x3 >= 42"));
405 constraints.add(equationFromString(objective.length, "x14 + x15 + x16 + x17 - x26 = 0"));
406 constraints.add(equationFromString(objective.length, "x18 + x19 + x20 + x21 + x22 + x23 + x24 + x25 - x27 = 0"));
407 constraints.add(equationFromString(objective.length, "x14 + x15 + x16 + x17 - x12 = 0"));
408 constraints.add(equationFromString(objective.length, "x18 + x19 + x20 + x21 + x22 + x23 + x24 + x25 - x13 = 0"));
409 constraints.add(equationFromString(objective.length, "x28 + x29 + x30 + x31 - x40 = 0"));
410 constraints.add(equationFromString(objective.length, "x32 + x33 + x34 + x35 + x36 + x37 + x38 + x39 - x41 = 0"));
411 constraints.add(equationFromString(objective.length, "x32 + x33 + x34 + x35 + x36 + x37 + x38 + x39 >= 49"));
412 constraints.add(equationFromString(objective.length, "x28 + x29 + x30 + x31 >= 42"));
413 constraints.add(equationFromString(objective.length, "x42 + x43 + x44 + x45 - x54 = 0"));
414 constraints.add(equationFromString(objective.length, "x46 + x47 + x48 + x49 + x50 + x51 + x52 + x53 - x55 = 0"));
415 constraints.add(equationFromString(objective.length, "x42 + x43 + x44 + x45 - x40 = 0"));
416 constraints.add(equationFromString(objective.length, "x46 + x47 + x48 + x49 + x50 + x51 + x52 + x53 - x41 = 0"));
417 constraints.add(equationFromString(objective.length, "x56 + x57 + x58 + x59 - x68 = 0"));
418 constraints.add(equationFromString(objective.length, "x60 + x61 + x62 + x63 + x64 + x65 + x66 + x67 - x69 = 0"));
419 constraints.add(equationFromString(objective.length, "x60 + x61 + x62 + x63 + x64 + x65 + x66 + x67 >= 51"));
420 constraints.add(equationFromString(objective.length, "x56 + x57 + x58 + x59 >= 44"));
421 constraints.add(equationFromString(objective.length, "x70 + x71 + x72 + x73 - x82 = 0"));
422 constraints.add(equationFromString(objective.length, "x74 + x75 + x76 + x77 + x78 + x79 + x80 + x81 - x83 = 0"));
423 constraints.add(equationFromString(objective.length, "x70 + x71 + x72 + x73 - x68 = 0"));
424 constraints.add(equationFromString(objective.length, "x74 + x75 + x76 + x77 + x78 + x79 + x80 + x81 - x69 = 0"));
425 constraints.add(equationFromString(objective.length, "x84 + x85 + x86 + x87 - x96 = 0"));
426 constraints.add(equationFromString(objective.length, "x88 + x89 + x90 + x91 + x92 + x93 + x94 + x95 - x97 = 0"));
427 constraints.add(equationFromString(objective.length, "x88 + x89 + x90 + x91 + x92 + x93 + x94 + x95 >= 51"));
428 constraints.add(equationFromString(objective.length, "x84 + x85 + x86 + x87 >= 44"));
429 constraints.add(equationFromString(objective.length, "x98 + x99 + x100 + x101 - x110 = 0"));
430 constraints.add(equationFromString(objective.length, "x102 + x103 + x104 + x105 + x106 + x107 + x108 + x109 - x111 = 0"));
431 constraints.add(equationFromString(objective.length, "x98 + x99 + x100 + x101 - x96 = 0"));
432 constraints.add(equationFromString(objective.length, "x102 + x103 + x104 + x105 + x106 + x107 + x108 + x109 - x97 = 0"));
433 constraints.add(equationFromString(objective.length, "x112 + x113 + x114 + x115 - x124 = 0"));
434 constraints.add(equationFromString(objective.length, "x116 + x117 + x118 + x119 + x120 + x121 + x122 + x123 - x125 = 0"));
435 constraints.add(equationFromString(objective.length, "x116 + x117 + x118 + x119 + x120 + x121 + x122 + x123 >= 49"));
436 constraints.add(equationFromString(objective.length, "x112 + x113 + x114 + x115 >= 42"));
437 constraints.add(equationFromString(objective.length, "x126 + x127 + x128 + x129 - x138 = 0"));
438 constraints.add(equationFromString(objective.length, "x130 + x131 + x132 + x133 + x134 + x135 + x136 + x137 - x139 = 0"));
439 constraints.add(equationFromString(objective.length, "x126 + x127 + x128 + x129 - x124 = 0"));
440 constraints.add(equationFromString(objective.length, "x130 + x131 + x132 + x133 + x134 + x135 + x136 + x137 - x125 = 0"));
441 constraints.add(equationFromString(objective.length, "x140 + x141 + x142 + x143 - x152 = 0"));
442 constraints.add(equationFromString(objective.length, "x144 + x145 + x146 + x147 + x148 + x149 + x150 + x151 - x153 = 0"));
443 constraints.add(equationFromString(objective.length, "x144 + x145 + x146 + x147 + x148 + x149 + x150 + x151 >= 59"));
444 constraints.add(equationFromString(objective.length, "x140 + x141 + x142 + x143 >= 42"));
445 constraints.add(equationFromString(objective.length, "x154 + x155 + x156 + x157 - x166 = 0"));
446 constraints.add(equationFromString(objective.length, "x158 + x159 + x160 + x161 + x162 + x163 + x164 + x165 - x167 = 0"));
447 constraints.add(equationFromString(objective.length, "x154 + x155 + x156 + x157 - x152 = 0"));
448 constraints.add(equationFromString(objective.length, "x158 + x159 + x160 + x161 + x162 + x163 + x164 + x165 - x153 = 0"));
449 constraints.add(equationFromString(objective.length, "x83 + x82 - x168 = 0"));
450 constraints.add(equationFromString(objective.length, "x111 + x110 - x169 = 0"));
451 constraints.add(equationFromString(objective.length, "x170 - x182 = 0"));
452 constraints.add(equationFromString(objective.length, "x171 - x183 = 0"));
453 constraints.add(equationFromString(objective.length, "x172 - x184 = 0"));
454 constraints.add(equationFromString(objective.length, "x173 - x185 = 0"));
455 constraints.add(equationFromString(objective.length, "x174 - x186 = 0"));
456 constraints.add(equationFromString(objective.length, "x175 + x176 - x187 = 0"));
457 constraints.add(equationFromString(objective.length, "x177 - x188 = 0"));
458 constraints.add(equationFromString(objective.length, "x178 - x189 = 0"));
459 constraints.add(equationFromString(objective.length, "x179 - x190 = 0"));
460 constraints.add(equationFromString(objective.length, "x180 - x191 = 0"));
461 constraints.add(equationFromString(objective.length, "x181 - x192 = 0"));
462 constraints.add(equationFromString(objective.length, "x170 - x26 = 0"));
463 constraints.add(equationFromString(objective.length, "x171 - x27 = 0"));
464 constraints.add(equationFromString(objective.length, "x172 - x54 = 0"));
465 constraints.add(equationFromString(objective.length, "x173 - x55 = 0"));
466 constraints.add(equationFromString(objective.length, "x174 - x168 = 0"));
467 constraints.add(equationFromString(objective.length, "x177 - x169 = 0"));
468 constraints.add(equationFromString(objective.length, "x178 - x138 = 0"));
469 constraints.add(equationFromString(objective.length, "x179 - x139 = 0"));
470 constraints.add(equationFromString(objective.length, "x180 - x166 = 0"));
471 constraints.add(equationFromString(objective.length, "x181 - x167 = 0"));
472 constraints.add(equationFromString(objective.length, "x193 - x205 = 0"));
473 constraints.add(equationFromString(objective.length, "x194 - x206 = 0"));
474 constraints.add(equationFromString(objective.length, "x195 - x207 = 0"));
475 constraints.add(equationFromString(objective.length, "x196 - x208 = 0"));
476 constraints.add(equationFromString(objective.length, "x197 - x209 = 0"));
477 constraints.add(equationFromString(objective.length, "x198 + x199 - x210 = 0"));
478 constraints.add(equationFromString(objective.length, "x200 - x211 = 0"));
479 constraints.add(equationFromString(objective.length, "x201 - x212 = 0"));
480 constraints.add(equationFromString(objective.length, "x202 - x213 = 0"));
481 constraints.add(equationFromString(objective.length, "x203 - x214 = 0"));
482 constraints.add(equationFromString(objective.length, "x204 - x215 = 0"));
483 constraints.add(equationFromString(objective.length, "x193 - x182 = 0"));
484 constraints.add(equationFromString(objective.length, "x194 - x183 = 0"));
485 constraints.add(equationFromString(objective.length, "x195 - x184 = 0"));
486 constraints.add(equationFromString(objective.length, "x196 - x185 = 0"));
487 constraints.add(equationFromString(objective.length, "x197 - x186 = 0"));
488 constraints.add(equationFromString(objective.length, "x198 + x199 - x187 = 0"));
489 constraints.add(equationFromString(objective.length, "x200 - x188 = 0"));
490 constraints.add(equationFromString(objective.length, "x201 - x189 = 0"));
491 constraints.add(equationFromString(objective.length, "x202 - x190 = 0"));
492 constraints.add(equationFromString(objective.length, "x203 - x191 = 0"));
493 constraints.add(equationFromString(objective.length, "x204 - x192 = 0"));
494
495 SimplexSolver solver = new SimplexSolver();
496 RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MINIMIZE, true);
497 Assert.assertEquals(7518.0, solution.getValue(), .0000001);
498 }
499
500
501
502
503
504 private LinearConstraint equationFromString(int numCoefficients, String s) {
505 Relationship relationship;
506 if (s.contains(">=")) {
507 relationship = Relationship.GEQ;
508 } else if (s.contains("<=")) {
509 relationship = Relationship.LEQ;
510 } else if (s.contains("=")) {
511 relationship = Relationship.EQ;
512 } else {
513 throw new IllegalArgumentException();
514 }
515
516 String[] equationParts = s.split("[>|<]?=");
517 double rhs = Double.parseDouble(equationParts[1].trim());
518
519 double[] lhs = new double[numCoefficients];
520 String left = equationParts[0].replaceAll(" ?x", "");
521 String[] coefficients = left.split(" ");
522 for (String coefficient : coefficients) {
523 double value = coefficient.charAt(0) == '-' ? -1 : 1;
524 int index = Integer.parseInt(coefficient.replaceFirst("[+|-]", "").trim());
525 lhs[index] = value;
526 }
527 return new LinearConstraint(lhs, relationship, rhs);
528 }
529
530 }