Mercurial > hg > de.mpg.mpiwg.itgroup.digilib.plugin

comparison libs/commons-math-2.1/docs/apidocs/src-html/org/apache/commons/math/optimization/linear/SimplexSolver.html @ 13:cbf34dd4d7e6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
commons-math-2.1 added
author dwinter
date Tue, 04 Jan 2011 10:02:07 +0100
parents
children
comparison
equal deleted inserted replaced
12:970d26a94fb7 13:cbf34dd4d7e6
1 <HTML>
2 <BODY BGCOLOR="white">
3 <PRE>
4 <FONT color="green">001</FONT> /*<a name="line.1"></a>
5 <FONT color="green">002</FONT> * Licensed to the Apache Software Foundation (ASF) under one or more<a name="line.2"></a>
6 <FONT color="green">003</FONT> * contributor license agreements. See the NOTICE file distributed with<a name="line.3"></a>
7 <FONT color="green">004</FONT> * this work for additional information regarding copyright ownership.<a name="line.4"></a>
8 <FONT color="green">005</FONT> * The ASF licenses this file to You under the Apache License, Version 2.0<a name="line.5"></a>
9 <FONT color="green">006</FONT> * (the "License"); you may not use this file except in compliance with<a name="line.6"></a>
10 <FONT color="green">007</FONT> * the License. You may obtain a copy of the License at<a name="line.7"></a>
11 <FONT color="green">008</FONT> *<a name="line.8"></a>
12 <FONT color="green">009</FONT> * http://www.apache.org/licenses/LICENSE-2.0<a name="line.9"></a>
13 <FONT color="green">010</FONT> *<a name="line.10"></a>
14 <FONT color="green">011</FONT> * Unless required by applicable law or agreed to in writing, software<a name="line.11"></a>
15 <FONT color="green">012</FONT> * distributed under the License is distributed on an "AS IS" BASIS,<a name="line.12"></a>
16 <FONT color="green">013</FONT> * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.<a name="line.13"></a>
17 <FONT color="green">014</FONT> * See the License for the specific language governing permissions and<a name="line.14"></a>
18 <FONT color="green">015</FONT> * limitations under the License.<a name="line.15"></a>
19 <FONT color="green">016</FONT> */<a name="line.16"></a>
20 <FONT color="green">017</FONT> <a name="line.17"></a>
21 <FONT color="green">018</FONT> package org.apache.commons.math.optimization.linear;<a name="line.18"></a>
22 <FONT color="green">019</FONT> <a name="line.19"></a>
23 <FONT color="green">020</FONT> import java.util.ArrayList;<a name="line.20"></a>
24 <FONT color="green">021</FONT> import java.util.List;<a name="line.21"></a>
25 <FONT color="green">022</FONT> <a name="line.22"></a>
26 <FONT color="green">023</FONT> import org.apache.commons.math.optimization.OptimizationException;<a name="line.23"></a>
27 <FONT color="green">024</FONT> import org.apache.commons.math.optimization.RealPointValuePair;<a name="line.24"></a>
28 <FONT color="green">025</FONT> import org.apache.commons.math.util.MathUtils;<a name="line.25"></a>
29 <FONT color="green">026</FONT> <a name="line.26"></a>
30 <FONT color="green">027</FONT> <a name="line.27"></a>
31 <FONT color="green">028</FONT> /**<a name="line.28"></a>
32 <FONT color="green">029</FONT> * Solves a linear problem using the Two-Phase Simplex Method.<a name="line.29"></a>
33 <FONT color="green">030</FONT> * @version $Revision: 812831 $ $Date: 2009-09-09 04:48:03 -0400 (Wed, 09 Sep 2009) $<a name="line.30"></a>
34 <FONT color="green">031</FONT> * @since 2.0<a name="line.31"></a>
35 <FONT color="green">032</FONT> */<a name="line.32"></a>
36 <FONT color="green">033</FONT> public class SimplexSolver extends AbstractLinearOptimizer {<a name="line.33"></a>
37 <FONT color="green">034</FONT> <a name="line.34"></a>
38 <FONT color="green">035</FONT> /** Default amount of error to accept in floating point comparisons. */<a name="line.35"></a>
39 <FONT color="green">036</FONT> private static final double DEFAULT_EPSILON = 1.0e-6;<a name="line.36"></a>
40 <FONT color="green">037</FONT> <a name="line.37"></a>
41 <FONT color="green">038</FONT> /** Amount of error to accept in floating point comparisons. */<a name="line.38"></a>
42 <FONT color="green">039</FONT> protected final double epsilon;<a name="line.39"></a>
43 <FONT color="green">040</FONT> <a name="line.40"></a>
44 <FONT color="green">041</FONT> /**<a name="line.41"></a>
45 <FONT color="green">042</FONT> * Build a simplex solver with default settings.<a name="line.42"></a>
46 <FONT color="green">043</FONT> */<a name="line.43"></a>
47 <FONT color="green">044</FONT> public SimplexSolver() {<a name="line.44"></a>
48 <FONT color="green">045</FONT> this(DEFAULT_EPSILON);<a name="line.45"></a>
49 <FONT color="green">046</FONT> }<a name="line.46"></a>
50 <FONT color="green">047</FONT> <a name="line.47"></a>
51 <FONT color="green">048</FONT> /**<a name="line.48"></a>
52 <FONT color="green">049</FONT> * Build a simplex solver with a specified accepted amount of error<a name="line.49"></a>
53 <FONT color="green">050</FONT> * @param epsilon the amount of error to accept in floating point comparisons<a name="line.50"></a>
54 <FONT color="green">051</FONT> */<a name="line.51"></a>
55 <FONT color="green">052</FONT> public SimplexSolver(final double epsilon) {<a name="line.52"></a>
56 <FONT color="green">053</FONT> this.epsilon = epsilon;<a name="line.53"></a>
57 <FONT color="green">054</FONT> }<a name="line.54"></a>
58 <FONT color="green">055</FONT> <a name="line.55"></a>
59 <FONT color="green">056</FONT> /**<a name="line.56"></a>
60 <FONT color="green">057</FONT> * Returns the column with the most negative coefficient in the objective function row.<a name="line.57"></a>
61 <FONT color="green">058</FONT> * @param tableau simple tableau for the problem<a name="line.58"></a>
62 <FONT color="green">059</FONT> * @return column with the most negative coefficient<a name="line.59"></a>
63 <FONT color="green">060</FONT> */<a name="line.60"></a>
64 <FONT color="green">061</FONT> private Integer getPivotColumn(SimplexTableau tableau) {<a name="line.61"></a>
65 <FONT color="green">062</FONT> double minValue = 0;<a name="line.62"></a>
66 <FONT color="green">063</FONT> Integer minPos = null;<a name="line.63"></a>
67 <FONT color="green">064</FONT> for (int i = tableau.getNumObjectiveFunctions(); i &lt; tableau.getWidth() - 1; i++) {<a name="line.64"></a>
68 <FONT color="green">065</FONT> if (MathUtils.compareTo(tableau.getEntry(0, i), minValue, epsilon) &lt; 0) {<a name="line.65"></a>
69 <FONT color="green">066</FONT> minValue = tableau.getEntry(0, i);<a name="line.66"></a>
70 <FONT color="green">067</FONT> minPos = i;<a name="line.67"></a>
71 <FONT color="green">068</FONT> }<a name="line.68"></a>
72 <FONT color="green">069</FONT> }<a name="line.69"></a>
73 <FONT color="green">070</FONT> return minPos;<a name="line.70"></a>
74 <FONT color="green">071</FONT> }<a name="line.71"></a>
75 <FONT color="green">072</FONT> <a name="line.72"></a>
76 <FONT color="green">073</FONT> /**<a name="line.73"></a>
77 <FONT color="green">074</FONT> * Returns the row with the minimum ratio as given by the minimum ratio test (MRT).<a name="line.74"></a>
78 <FONT color="green">075</FONT> * @param tableau simple tableau for the problem<a name="line.75"></a>
79 <FONT color="green">076</FONT> * @param col the column to test the ratio of. See {@link #getPivotColumn(SimplexTableau)}<a name="line.76"></a>
80 <FONT color="green">077</FONT> * @return row with the minimum ratio<a name="line.77"></a>
81 <FONT color="green">078</FONT> */<a name="line.78"></a>
82 <FONT color="green">079</FONT> private Integer getPivotRow(SimplexTableau tableau, final int col) {<a name="line.79"></a>
83 <FONT color="green">080</FONT> // create a list of all the rows that tie for the lowest score in the minimum ratio test<a name="line.80"></a>
84 <FONT color="green">081</FONT> List&lt;Integer&gt; minRatioPositions = new ArrayList&lt;Integer&gt;();<a name="line.81"></a>
85 <FONT color="green">082</FONT> double minRatio = Double.MAX_VALUE;<a name="line.82"></a>
86 <FONT color="green">083</FONT> for (int i = tableau.getNumObjectiveFunctions(); i &lt; tableau.getHeight(); i++) {<a name="line.83"></a>
87 <FONT color="green">084</FONT> final double rhs = tableau.getEntry(i, tableau.getWidth() - 1);<a name="line.84"></a>
88 <FONT color="green">085</FONT> final double entry = tableau.getEntry(i, col);<a name="line.85"></a>
89 <FONT color="green">086</FONT> if (MathUtils.compareTo(entry, 0, epsilon) &gt; 0) {<a name="line.86"></a>
90 <FONT color="green">087</FONT> final double ratio = rhs / entry;<a name="line.87"></a>
91 <FONT color="green">088</FONT> if (MathUtils.equals(ratio, minRatio, epsilon)) {<a name="line.88"></a>
92 <FONT color="green">089</FONT> minRatioPositions.add(i);<a name="line.89"></a>
93 <FONT color="green">090</FONT> } else if (ratio &lt; minRatio) {<a name="line.90"></a>
94 <FONT color="green">091</FONT> minRatio = ratio;<a name="line.91"></a>
95 <FONT color="green">092</FONT> minRatioPositions = new ArrayList&lt;Integer&gt;();<a name="line.92"></a>
96 <FONT color="green">093</FONT> minRatioPositions.add(i);<a name="line.93"></a>
97 <FONT color="green">094</FONT> }<a name="line.94"></a>
98 <FONT color="green">095</FONT> }<a name="line.95"></a>
99 <FONT color="green">096</FONT> }<a name="line.96"></a>
100 <FONT color="green">097</FONT> <a name="line.97"></a>
101 <FONT color="green">098</FONT> if (minRatioPositions.size() == 0) {<a name="line.98"></a>
102 <FONT color="green">099</FONT> return null;<a name="line.99"></a>
103 <FONT color="green">100</FONT> } else if (minRatioPositions.size() &gt; 1) {<a name="line.100"></a>
104 <FONT color="green">101</FONT> // there's a degeneracy as indicated by a tie in the minimum ratio test<a name="line.101"></a>
105 <FONT color="green">102</FONT> // check if there's an artificial variable that can be forced out of the basis<a name="line.102"></a>
106 <FONT color="green">103</FONT> for (Integer row : minRatioPositions) {<a name="line.103"></a>
107 <FONT color="green">104</FONT> for (int i = 0; i &lt; tableau.getNumArtificialVariables(); i++) {<a name="line.104"></a>
108 <FONT color="green">105</FONT> int column = i + tableau.getArtificialVariableOffset();<a name="line.105"></a>
109 <FONT color="green">106</FONT> if (MathUtils.equals(tableau.getEntry(row, column), 1, epsilon) &amp;&amp;<a name="line.106"></a>
110 <FONT color="green">107</FONT> row.equals(tableau.getBasicRow(column))) {<a name="line.107"></a>
111 <FONT color="green">108</FONT> return row;<a name="line.108"></a>
112 <FONT color="green">109</FONT> }<a name="line.109"></a>
113 <FONT color="green">110</FONT> }<a name="line.110"></a>
114 <FONT color="green">111</FONT> }<a name="line.111"></a>
115 <FONT color="green">112</FONT> }<a name="line.112"></a>
116 <FONT color="green">113</FONT> return minRatioPositions.get(0);<a name="line.113"></a>
117 <FONT color="green">114</FONT> }<a name="line.114"></a>
118 <FONT color="green">115</FONT> <a name="line.115"></a>
119 <FONT color="green">116</FONT> /**<a name="line.116"></a>
120 <FONT color="green">117</FONT> * Runs one iteration of the Simplex method on the given model.<a name="line.117"></a>
121 <FONT color="green">118</FONT> * @param tableau simple tableau for the problem<a name="line.118"></a>
122 <FONT color="green">119</FONT> * @throws OptimizationException if the maximal iteration count has been<a name="line.119"></a>
123 <FONT color="green">120</FONT> * exceeded or if the model is found not to have a bounded solution<a name="line.120"></a>
124 <FONT color="green">121</FONT> */<a name="line.121"></a>
125 <FONT color="green">122</FONT> protected void doIteration(final SimplexTableau tableau)<a name="line.122"></a>
126 <FONT color="green">123</FONT> throws OptimizationException {<a name="line.123"></a>
127 <FONT color="green">124</FONT> <a name="line.124"></a>
128 <FONT color="green">125</FONT> incrementIterationsCounter();<a name="line.125"></a>
129 <FONT color="green">126</FONT> <a name="line.126"></a>
130 <FONT color="green">127</FONT> Integer pivotCol = getPivotColumn(tableau);<a name="line.127"></a>
131 <FONT color="green">128</FONT> Integer pivotRow = getPivotRow(tableau, pivotCol);<a name="line.128"></a>
132 <FONT color="green">129</FONT> if (pivotRow == null) {<a name="line.129"></a>
133 <FONT color="green">130</FONT> throw new UnboundedSolutionException();<a name="line.130"></a>
134 <FONT color="green">131</FONT> }<a name="line.131"></a>
135 <FONT color="green">132</FONT> <a name="line.132"></a>
136 <FONT color="green">133</FONT> // set the pivot element to 1<a name="line.133"></a>
137 <FONT color="green">134</FONT> double pivotVal = tableau.getEntry(pivotRow, pivotCol);<a name="line.134"></a>
138 <FONT color="green">135</FONT> tableau.divideRow(pivotRow, pivotVal);<a name="line.135"></a>
139 <FONT color="green">136</FONT> <a name="line.136"></a>
140 <FONT color="green">137</FONT> // set the rest of the pivot column to 0<a name="line.137"></a>
141 <FONT color="green">138</FONT> for (int i = 0; i &lt; tableau.getHeight(); i++) {<a name="line.138"></a>
142 <FONT color="green">139</FONT> if (i != pivotRow) {<a name="line.139"></a>
143 <FONT color="green">140</FONT> double multiplier = tableau.getEntry(i, pivotCol);<a name="line.140"></a>
144 <FONT color="green">141</FONT> tableau.subtractRow(i, pivotRow, multiplier);<a name="line.141"></a>
145 <FONT color="green">142</FONT> }<a name="line.142"></a>
146 <FONT color="green">143</FONT> }<a name="line.143"></a>
147 <FONT color="green">144</FONT> }<a name="line.144"></a>
148 <FONT color="green">145</FONT> <a name="line.145"></a>
149 <FONT color="green">146</FONT> /**<a name="line.146"></a>
150 <FONT color="green">147</FONT> * Solves Phase 1 of the Simplex method.<a name="line.147"></a>
151 <FONT color="green">148</FONT> * @param tableau simple tableau for the problem<a name="line.148"></a>
152 <FONT color="green">149</FONT> * @exception OptimizationException if the maximal number of iterations is<a name="line.149"></a>
153 <FONT color="green">150</FONT> * exceeded, or if the problem is found not to have a bounded solution, or<a name="line.150"></a>
154 <FONT color="green">151</FONT> * if there is no feasible solution<a name="line.151"></a>
155 <FONT color="green">152</FONT> */<a name="line.152"></a>
156 <FONT color="green">153</FONT> protected void solvePhase1(final SimplexTableau tableau) throws OptimizationException {<a name="line.153"></a>
157 <FONT color="green">154</FONT> <a name="line.154"></a>
158 <FONT color="green">155</FONT> // make sure we're in Phase 1<a name="line.155"></a>
159 <FONT color="green">156</FONT> if (tableau.getNumArtificialVariables() == 0) {<a name="line.156"></a>
160 <FONT color="green">157</FONT> return;<a name="line.157"></a>
161 <FONT color="green">158</FONT> }<a name="line.158"></a>
162 <FONT color="green">159</FONT> <a name="line.159"></a>
163 <FONT color="green">160</FONT> while (!tableau.isOptimal()) {<a name="line.160"></a>
164 <FONT color="green">161</FONT> doIteration(tableau);<a name="line.161"></a>
165 <FONT color="green">162</FONT> }<a name="line.162"></a>
166 <FONT color="green">163</FONT> <a name="line.163"></a>
167 <FONT color="green">164</FONT> // if W is not zero then we have no feasible solution<a name="line.164"></a>
168 <FONT color="green">165</FONT> if (!MathUtils.equals(tableau.getEntry(0, tableau.getRhsOffset()), 0, epsilon)) {<a name="line.165"></a>
169 <FONT color="green">166</FONT> throw new NoFeasibleSolutionException();<a name="line.166"></a>
170 <FONT color="green">167</FONT> }<a name="line.167"></a>
171 <FONT color="green">168</FONT> }<a name="line.168"></a>
172 <FONT color="green">169</FONT> <a name="line.169"></a>
173 <FONT color="green">170</FONT> /** {@inheritDoc} */<a name="line.170"></a>
174 <FONT color="green">171</FONT> @Override<a name="line.171"></a>
175 <FONT color="green">172</FONT> public RealPointValuePair doOptimize() throws OptimizationException {<a name="line.172"></a>
176 <FONT color="green">173</FONT> final SimplexTableau tableau =<a name="line.173"></a>
177 <FONT color="green">174</FONT> new SimplexTableau(function, linearConstraints, goal, nonNegative, epsilon);<a name="line.174"></a>
178 <FONT color="green">175</FONT> <a name="line.175"></a>
179 <FONT color="green">176</FONT> solvePhase1(tableau);<a name="line.176"></a>
180 <FONT color="green">177</FONT> tableau.dropPhase1Objective();<a name="line.177"></a>
181 <FONT color="green">178</FONT> <a name="line.178"></a>
182 <FONT color="green">179</FONT> while (!tableau.isOptimal()) {<a name="line.179"></a>
183 <FONT color="green">180</FONT> doIteration(tableau);<a name="line.180"></a>
184 <FONT color="green">181</FONT> }<a name="line.181"></a>
185 <FONT color="green">182</FONT> return tableau.getSolution();<a name="line.182"></a>
186 <FONT color="green">183</FONT> }<a name="line.183"></a>
187 <FONT color="green">184</FONT> <a name="line.184"></a>
188 <FONT color="green">185</FONT> }<a name="line.185"></a>
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249 </PRE>
250 </BODY>
251 </HTML>