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 }