001    /*
002     * Licensed to the Apache Software Foundation (ASF) under one or more
003     * contributor license agreements.  See the NOTICE file distributed with
004     * this work for additional information regarding copyright ownership.
005     * The ASF licenses this file to You under the Apache License, Version 2.0
006     * (the "License"); you may not use this file except in compliance with
007     * the License.  You may obtain a copy of the License at
008     *
009     *      http://www.apache.org/licenses/LICENSE-2.0
010     *
011     * Unless required by applicable law or agreed to in writing, software
012     * distributed under the License is distributed on an "AS IS" BASIS,
013     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014     * See the License for the specific language governing permissions and
015     * limitations under the License.
016     */
017    
018    package org.apache.commons.math.optimization.linear;
019    
020    import static org.junit.Assert.assertEquals;
021    
022    import java.util.ArrayList;
023    import java.util.Collection;
024    
025    import org.apache.commons.math.linear.RealVector;
026    import org.apache.commons.math.linear.ArrayRealVector;
027    import org.apache.commons.math.optimization.GoalType;
028    import org.apache.commons.math.optimization.OptimizationException;
029    import org.apache.commons.math.optimization.RealPointValuePair;
030    import org.junit.Test;
031    
032    public class SimplexSolverTest {
033    
034        @Test
035        public void testMath272() throws OptimizationException {
036            LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 2, 2, 1 }, 0);
037            Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
038            constraints.add(new LinearConstraint(new double[] { 1, 1, 0 }, Relationship.GEQ,  1));
039            constraints.add(new LinearConstraint(new double[] { 1, 0, 1 }, Relationship.GEQ,  1));
040            constraints.add(new LinearConstraint(new double[] { 0, 1, 0 }, Relationship.GEQ,  1));
041    
042            SimplexSolver solver = new SimplexSolver();
043            RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MINIMIZE, true);
044            
045            assertEquals(0.0, solution.getPoint()[0], .0000001);
046            assertEquals(1.0, solution.getPoint()[1], .0000001);
047            assertEquals(1.0, solution.getPoint()[2], .0000001);
048            assertEquals(3.0, solution.getValue(), .0000001);
049          }
050    
051        @Test
052        public void testSimplexSolver() throws OptimizationException {
053            LinearObjectiveFunction f =
054                new LinearObjectiveFunction(new double[] { 15, 10 }, 7);
055            Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
056            constraints.add(new LinearConstraint(new double[] { 1, 0 }, Relationship.LEQ, 2));
057            constraints.add(new LinearConstraint(new double[] { 0, 1 }, Relationship.LEQ, 3));
058            constraints.add(new LinearConstraint(new double[] { 1, 1 }, Relationship.EQ, 4));
059    
060            SimplexSolver solver = new SimplexSolver();
061            RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
062            assertEquals(2.0, solution.getPoint()[0], 0.0);
063            assertEquals(2.0, solution.getPoint()[1], 0.0);
064            assertEquals(57.0, solution.getValue(), 0.0);
065        }
066    
067        @Test
068        public void testSingleVariableAndConstraint() throws OptimizationException {
069            LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 3 }, 0);
070            Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
071            constraints.add(new LinearConstraint(new double[] { 1 }, Relationship.LEQ, 10));
072    
073            SimplexSolver solver = new SimplexSolver();
074            RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
075            assertEquals(10.0, solution.getPoint()[0], 0.0);
076            assertEquals(30.0, solution.getValue(), 0.0);
077        }
078        
079        /**
080         * With no artificial variables needed (no equals and no greater than
081         * constraints) we can go straight to Phase 2.
082         */
083        @Test
084        public void testModelWithNoArtificialVars() throws OptimizationException {
085            LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 15, 10 }, 0);
086            Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
087            constraints.add(new LinearConstraint(new double[] { 1, 0 }, Relationship.LEQ, 2));
088            constraints.add(new LinearConstraint(new double[] { 0, 1 }, Relationship.LEQ, 3));
089            constraints.add(new LinearConstraint(new double[] { 1, 1 }, Relationship.LEQ, 4));
090    
091            SimplexSolver solver = new SimplexSolver();
092            RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
093            assertEquals(2.0, solution.getPoint()[0], 0.0);
094            assertEquals(2.0, solution.getPoint()[1], 0.0);
095            assertEquals(50.0, solution.getValue(), 0.0);
096        }
097    
098        @Test
099        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    }