← Back to branch summary

~ubuntu-branches/ubuntu/quantal/commons-math/quantal

« back to all changes in this revision

Viewing changes to src/test/java/org/apache/commons/math/optimization/linear/SimplexSolverTest.java

  • Committer: Bazaar Package Importer
  • Author(s): Damien Raude-Morvan
  • Date: 2010-04-05 23:33:02 UTC
  • mfrom: (1.1.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20100405233302-gpqlceked76nw28a
Tags: 2.1-1
* New upstream release.
* Bump Standards-Version to 3.8.4: no changes needed
* Bump debhelper to >= 7
* Switch to 3.0 (quilt) source format:
  - Remove B-D on quilt
  - Add d/source/format
  - Remove d/README.source

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/test/java/org/apache/commons/math/optimization/linear/SimplexSolverTest.java
17
17
 
18
18
package org.apache.commons.math.optimization.linear;
19
19
 
20
 
import static org.junit.Assert.assertEquals;
 
20
import org.junit.Assert;
21
21
 
22
22
import java.util.ArrayList;
23
23
import java.util.Collection;
24
24
 
25
 
import org.apache.commons.math.linear.RealVector;
26
 
import org.apache.commons.math.linear.ArrayRealVector;
27
25
import org.apache.commons.math.optimization.GoalType;
28
26
import org.apache.commons.math.optimization.OptimizationException;
29
27
import org.apache.commons.math.optimization.RealPointValuePair;
41
39
 
42
40
        SimplexSolver solver = new SimplexSolver();
43
41
        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
 
      }
 
42
 
 
43
        Assert.assertEquals(0.0, solution.getPoint()[0], .0000001);
 
44
        Assert.assertEquals(1.0, solution.getPoint()[1], .0000001);
 
45
        Assert.assertEquals(1.0, solution.getPoint()[2], .0000001);
 
46
        Assert.assertEquals(3.0, solution.getValue(), .0000001);
 
47
    }
 
48
 
 
49
    @Test
 
50
    public void testMath286() throws OptimizationException {
 
51
        LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 0.8, 0.2, 0.7, 0.3, 0.6, 0.4 }, 0 );
 
52
        Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
 
53
        constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0, 1, 0 }, Relationship.EQ, 23.0));
 
54
        constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1, 0, 1 }, Relationship.EQ, 23.0));
 
55
        constraints.add(new LinearConstraint(new double[] { 1, 0, 0, 0, 0, 0 }, Relationship.GEQ, 10.0));
 
56
        constraints.add(new LinearConstraint(new double[] { 0, 0, 1, 0, 0, 0 }, Relationship.GEQ, 8.0));
 
57
        constraints.add(new LinearConstraint(new double[] { 0, 0, 0, 0, 1, 0 }, Relationship.GEQ, 5.0));
 
58
 
 
59
        SimplexSolver solver = new SimplexSolver();
 
60
        RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, true);
 
61
 
 
62
        Assert.assertEquals(25.8, solution.getValue(), .0000001);
 
63
        Assert.assertEquals(23.0, solution.getPoint()[0] + solution.getPoint()[2] + solution.getPoint()[4], 0.0000001);
 
64
        Assert.assertEquals(23.0, solution.getPoint()[1] + solution.getPoint()[3] + solution.getPoint()[5], 0.0000001);
 
65
        Assert.assertTrue(solution.getPoint()[0] >= 10.0 - 0.0000001);
 
66
        Assert.assertTrue(solution.getPoint()[2] >= 8.0 - 0.0000001);
 
67
        Assert.assertTrue(solution.getPoint()[4] >= 5.0 - 0.0000001);
 
68
    }
 
69
 
 
70
    @Test
 
71
    public void testDegeneracy() throws OptimizationException {
 
72
        LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 0.8, 0.7 }, 0 );
 
73
        Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
 
74
        constraints.add(new LinearConstraint(new double[] { 1, 1 }, Relationship.LEQ, 18.0));
 
75
        constraints.add(new LinearConstraint(new double[] { 1, 0 }, Relationship.GEQ, 10.0));
 
76
        constraints.add(new LinearConstraint(new double[] { 0, 1 }, Relationship.GEQ, 8.0));
 
77
 
 
78
        SimplexSolver solver = new SimplexSolver();
 
79
        RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, true);
 
80
        Assert.assertEquals(13.6, solution.getValue(), .0000001);
 
81
    }
 
82
 
 
83
    @Test
 
84
    public void testMath288() throws OptimizationException {
 
85
        LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 7, 3, 0, 0 }, 0 );
 
86
        Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
 
87
        constraints.add(new LinearConstraint(new double[] { 3, 0, -5, 0 }, Relationship.LEQ, 0.0));
 
88
        constraints.add(new LinearConstraint(new double[] { 2, 0, 0, -5 }, Relationship.LEQ, 0.0));
 
89
        constraints.add(new LinearConstraint(new double[] { 0, 3, 0, -5 }, Relationship.LEQ, 0.0));
 
90
        constraints.add(new LinearConstraint(new double[] { 1, 0, 0, 0 }, Relationship.LEQ, 1.0));
 
91
        constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 0 }, Relationship.LEQ, 1.0));
 
92
 
 
93
        SimplexSolver solver = new SimplexSolver();
 
94
        RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, true);
 
95
        Assert.assertEquals(10.0, solution.getValue(), .0000001);
 
96
    }
 
97
 
 
98
    @Test
 
99
    public void testMath290GEQ() throws OptimizationException {
 
100
        LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 1, 5 }, 0 );
 
101
        Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
 
102
        constraints.add(new LinearConstraint(new double[] { 2, 0 }, Relationship.GEQ, -1.0));
 
103
        SimplexSolver solver = new SimplexSolver();
 
104
        RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MINIMIZE, true);
 
105
        Assert.assertEquals(0, solution.getValue(), .0000001);
 
106
        Assert.assertEquals(0, solution.getPoint()[0], .0000001);
 
107
        Assert.assertEquals(0, solution.getPoint()[1], .0000001);
 
108
    }
 
109
 
 
110
    @Test(expected=NoFeasibleSolutionException.class)
 
111
    public void testMath290LEQ() throws OptimizationException {
 
112
        LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 1, 5 }, 0 );
 
113
        Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
 
114
        constraints.add(new LinearConstraint(new double[] { 2, 0 }, Relationship.LEQ, -1.0));
 
115
        SimplexSolver solver = new SimplexSolver();
 
116
        solver.optimize(f, constraints, GoalType.MINIMIZE, true);
 
117
    }
 
118
 
 
119
    @Test
 
120
    public void testMath293() throws OptimizationException {
 
121
      LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 0.8, 0.2, 0.7, 0.3, 0.4, 0.6}, 0 );
 
122
      Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
 
123
      constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0, 1, 0 }, Relationship.EQ, 30.0));
 
124
      constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1, 0, 1 }, Relationship.EQ, 30.0));
 
125
      constraints.add(new LinearConstraint(new double[] { 0.8, 0.2, 0.0, 0.0, 0.0, 0.0 }, Relationship.GEQ, 10.0));
 
126
      constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.7, 0.3, 0.0, 0.0 }, Relationship.GEQ, 10.0));
 
127
      constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.0, 0.0, 0.4, 0.6 }, Relationship.GEQ, 10.0));
 
128
 
 
129
      SimplexSolver solver = new SimplexSolver();
 
130
      RealPointValuePair solution1 = solver.optimize(f, constraints, GoalType.MAXIMIZE, true);
 
131
 
 
132
      Assert.assertEquals(15.7143, solution1.getPoint()[0], .0001);
 
133
      Assert.assertEquals(0.0, solution1.getPoint()[1], .0001);
 
134
      Assert.assertEquals(14.2857, solution1.getPoint()[2], .0001);
 
135
      Assert.assertEquals(0.0, solution1.getPoint()[3], .0001);
 
136
      Assert.assertEquals(0.0, solution1.getPoint()[4], .0001);
 
137
      Assert.assertEquals(30.0, solution1.getPoint()[5], .0001);
 
138
      Assert.assertEquals(40.57143, solution1.getValue(), .0001);
 
139
 
 
140
      double valA = 0.8 * solution1.getPoint()[0] + 0.2 * solution1.getPoint()[1];
 
141
      double valB = 0.7 * solution1.getPoint()[2] + 0.3 * solution1.getPoint()[3];
 
142
      double valC = 0.4 * solution1.getPoint()[4] + 0.6 * solution1.getPoint()[5];
 
143
 
 
144
      f = new LinearObjectiveFunction(new double[] { 0.8, 0.2, 0.7, 0.3, 0.4, 0.6}, 0 );
 
145
      constraints = new ArrayList<LinearConstraint>();
 
146
      constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0, 1, 0 }, Relationship.EQ, 30.0));
 
147
      constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1, 0, 1 }, Relationship.EQ, 30.0));
 
148
      constraints.add(new LinearConstraint(new double[] { 0.8, 0.2, 0.0, 0.0, 0.0, 0.0 }, Relationship.GEQ, valA));
 
149
      constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.7, 0.3, 0.0, 0.0 }, Relationship.GEQ, valB));
 
150
      constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.0, 0.0, 0.4, 0.6 }, Relationship.GEQ, valC));
 
151
 
 
152
      RealPointValuePair solution2 = solver.optimize(f, constraints, GoalType.MAXIMIZE, true);
 
153
      Assert.assertEquals(40.57143, solution2.getValue(), .0001);
 
154
    }
50
155
 
51
156
    @Test
52
157
    public void testSimplexSolver() throws OptimizationException {
59
164
 
60
165
        SimplexSolver solver = new SimplexSolver();
61
166
        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);
 
167
        Assert.assertEquals(2.0, solution.getPoint()[0], 0.0);
 
168
        Assert.assertEquals(2.0, solution.getPoint()[1], 0.0);
 
169
        Assert.assertEquals(57.0, solution.getValue(), 0.0);
65
170
    }
66
171
 
67
172
    @Test
72
177
 
73
178
        SimplexSolver solver = new SimplexSolver();
74
179
        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);
 
180
        Assert.assertEquals(10.0, solution.getPoint()[0], 0.0);
 
181
        Assert.assertEquals(30.0, solution.getValue(), 0.0);
77
182
    }
78
 
    
 
183
 
79
184
    /**
80
185
     * With no artificial variables needed (no equals and no greater than
81
186
     * constraints) we can go straight to Phase 2.
90
195
 
91
196
        SimplexSolver solver = new SimplexSolver();
92
197
        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);
 
198
        Assert.assertEquals(2.0, solution.getPoint()[0], 0.0);
 
199
        Assert.assertEquals(2.0, solution.getPoint()[1], 0.0);
 
200
        Assert.assertEquals(50.0, solution.getValue(), 0.0);
96
201
    }
97
202
 
98
203
    @Test
105
210
 
106
211
        SimplexSolver solver = new SimplexSolver();
107
212
        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);
 
213
        Assert.assertEquals(4.0, solution.getPoint()[0], 0.0);
 
214
        Assert.assertEquals(0.0, solution.getPoint()[1], 0.0);
 
215
        Assert.assertEquals(-13.0, solution.getValue(), 0.0);
111
216
    }
112
217
 
113
218
    @Test
119
224
 
120
225
        SimplexSolver solver = new SimplexSolver();
121
226
        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);
 
227
        Assert.assertEquals(-2.0, solution.getPoint()[0], 0.0);
 
228
        Assert.assertEquals(8.0, solution.getPoint()[1], 0.0);
 
229
        Assert.assertEquals(12.0, solution.getValue(), 0.0);
125
230
    }
126
231
 
127
232
    @Test(expected = NoFeasibleSolutionException.class)
157
262
 
158
263
        SimplexSolver solver = new SimplexSolver();
159
264
        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);
 
265
        Assert.assertEquals(2902.92783505155, solution.getPoint()[0], .0000001);
 
266
        Assert.assertEquals(480.419243986254, solution.getPoint()[1], .0000001);
 
267
        Assert.assertEquals(0.0, solution.getPoint()[2], .0000001);
 
268
        Assert.assertEquals(0.0, solution.getPoint()[3], .0000001);
 
269
        Assert.assertEquals(0.0, solution.getPoint()[4], .0000001);
 
270
        Assert.assertEquals(1438556.7491409, solution.getValue(), .0000001);
166
271
    }
167
272
 
168
273
    @Test
176
281
 
177
282
      SimplexSolver solver = new SimplexSolver();
178
283
      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);
 
284
      Assert.assertEquals(1.0, solution.getPoint()[0], 0.0);
 
285
      Assert.assertEquals(1.0, solution.getPoint()[1], 0.0);
 
286
      Assert.assertEquals(0.0, solution.getPoint()[2], 0.0);
 
287
      Assert.assertEquals(15.0, solution.getValue(), 0.0);
183
288
  }
184
 
    
 
289
 
185
290
    @Test
186
291
    public void testTrivialModel() throws OptimizationException {
187
292
        LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 1, 1 }, 0);
190
295
 
191
296
        SimplexSolver solver = new SimplexSolver();
192
297
        RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, true);
193
 
        assertEquals(0, solution.getValue(), .0000001);
 
298
        Assert.assertEquals(0, solution.getValue(), .0000001);
194
299
    }
195
300
 
196
301
    @Test
317
422
 
318
423
        SimplexSolver solver = new SimplexSolver();
319
424
        RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MINIMIZE, true);
320
 
        assertEquals(7518.0, solution.getValue(), .0000001);
 
425
        Assert.assertEquals(7518.0, solution.getValue(), .0000001);
321
426
    }
322
 
    
 
427
 
323
428
    /**
324
429
     * Converts a test string to a {@link LinearConstraint}.
325
430
     * Ex: x0 + x1 + x2 + x3 - x12 = 0
339
444
        String[] equationParts = s.split("[>|<]?=");
340
445
        double rhs = Double.parseDouble(equationParts[1].trim());
341
446
 
342
 
        RealVector lhs = new ArrayRealVector(numCoefficients);
 
447
        double[] lhs = new double[numCoefficients];
343
448
        String left = equationParts[0].replaceAll(" ?x", "");
344
449
        String[] coefficients = left.split(" ");
345
450
        for (String coefficient : coefficients) {
346
451
            double value = coefficient.charAt(0) == '-' ? -1 : 1;
347
452
            int index = Integer.parseInt(coefficient.replaceFirst("[+|-]", "").trim());
348
 
            lhs.setEntry(index, value);
 
453
            lhs[index] = value;
349
454
        }
350
455
        return new LinearConstraint(lhs, relationship, rhs);
351
456
    }