1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
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       * With no artificial variables needed (no equals and no greater than
81       * constraints) we can go straight to Phase 2.
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      * Converts a test string to a {@link LinearConstraint}.
325      * Ex: x0 + x1 + x2 + x3 - x12 = 0
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 }