1 /* This file is part of Shapes.
3 * Shapes is free software: you can redistribute it and/or modify
4 * it under the terms of the GNU General Public License as published by
5 * the Free Software Foundation, either version 3 of the License, or
8 * Shapes is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU General Public License for more details.
13 * You should have received a copy of the GNU General Public License
14 * along with Shapes. If not, see <http://www.gnu.org/licenses/>.
16 * Copyright 2008 Henrik Tidefelt
21 #include "basicsimplex.h"
23 #include "autoonoff.h"
26 #include <iostream> // For debugging
29 using namespace Shapes
;
31 Computation::BasicSimplex::BasicSimplex( size_t nVars
, size_t nEqns
)
32 : nVars_( nVars
), nEqns_( nEqns
),
33 nExt_( nVars
+ nEqns
),
34 a_( new double[ nEqns_
* ( nExt_
) ] ),
35 b_( new double[ nEqns_
] ),
36 c_( new double[ nExt_
] ),
37 varSet_( new size_t[ nExt_
] ),
38 nonBasicBegin_( varSet_
),
39 nonBasicEnd_( nonBasicBegin_
+ nVars_
),
40 basicBegin_( nonBasicEnd_
),
41 basicEnd_( basicBegin_
+ nEqns_
)
44 Computation::BasicSimplex::~BasicSimplex( )
53 // Call this function with preallocated memory for the result!
55 // It solves the problem of minimizing < c, *xdst > under the constraints
58 // The constraints are stored in row major order, so consecutive memory
59 // belongs to the same constraint, not the same variable.
60 // The optimum is returned in *objdst, and the return value
61 // is true if optimization finished with *objdst < objGoal.
62 // If the return value is true, then the optimum is generally not located,
63 // but only a sufficiently good point.
65 Computation::BasicSimplex::minimize( double * xdst
,
66 double * objdst
, double objGoal
,
67 const double * c
, const double * a
, const double * b
,
68 bool changeSign
) const
70 // Setup extended formulation with equality constraints and slack variables:
72 bool infeasibleStart
= false;
76 double * end
= c_
+ nVars_
;
78 const double * src
= c
;
81 for( ; dst
!= end
; ++dst
, ++src
)
88 for( ; dst
!= end
; ++dst
, ++src
)
94 for( ; dst
!= end
; ++dst
)
101 // Initialize a and b
103 // First all of a is zeroed.
104 double * end
= a_
+ nEqns_
* ( nExt_
);
106 for( ; dst
!= end
; ++dst
)
112 const double * srcb
= b
;
114 for( size_t eq
= 0; eq
< nEqns_
; ++eq
, ++srcb
, ++dstb
)
119 infeasibleStart
= true;
122 double * dst
= a_
+ eq
* ( nExt_
);
123 const double * src
= a
+ eq
* nVars_
;
124 const double * end
= src
+ nVars_
;
125 for( ; src
!= end
; ++src
, ++dst
)
134 // The basic and non-basic sets contain indices to variables.
135 // The basic set is organized so that the basic variable in equaiton i is located at ( basic + i ).
139 for( size_t * dst
= nonBasicBegin_
; dst
!= basicEnd_
; ++dst
, ++i
)
146 if( infeasibleStart
)
150 objective
= phaseTwo( xdst
, objGoal
);
154 objective
= HUGE_VAL
;
159 objective
= phaseTwo( xdst
, objGoal
);
164 *objdst
= - objective
;
170 return objective
< objGoal
;
175 Computation::BasicSimplex::maximize( double * xdst
,
176 double * objdst
, double objGoal
,
177 const double * c
, const double * a
, const double * b
) const
179 return minimize( xdst
,
186 // Function to compute a feasible tableau.
188 Computation::BasicSimplex::phaseOne( ) const
190 throw "Not implemented: Computation::BasicSimplex::phaseOne.";
193 // Function for minimizing given a feasible initial tableau.
195 Computation::BasicSimplex::phaseTwo( double * xdst
, double objGoal
) const
197 double objective
= 0;
205 std::cerr
<< "Simplex tableau:" << std::endl
;
206 for( size_t i
= 0; i
< 3 + nExt_
* 8 + 5; ++i
)
210 std::cerr
<< std::endl
;
212 for( size_t col
= 0; col
< nExt_
; ++col
)
217 for( const size_t * src
= basicBegin_
; src
!= basicEnd_
; ++src
)
236 for( const size_t * src
= nonBasicBegin_
; src
!= nonBasicEnd_
; ++src
)
255 std::cerr
<< std::endl
;
257 for( const double * src
= c_
; src
!= c_
+ nExt_
; ++src
)
260 std::sprintf( buf
, "%7.3f", *src
);
261 std::cerr
<< buf
<< " " ;
263 std::cerr
<< " | obj: " << objective
<< std::endl
;
264 for( size_t i
= 0; i
< 3 + nExt_
* 8 + 5; ++i
)
268 std::cerr
<< std::endl
;
270 const double * srca
= a_
;
271 for( size_t row
= 0; row
< nEqns_
; ++row
)
273 std::cerr
<< *( basicBegin_
+ row
) << " |" ;
274 const double * end
= srca
+ nExt_
;
275 for( ; srca
!= end
; ++srca
)
278 sprintf( buf
, "%7.3f", *srca
);
279 std::cerr
<< buf
<< " " ;
281 std::cerr
<< " | " << *( b_
+ row
) << std::endl
;
283 for( size_t i
= 0; i
< 3 + nExt_
* 8 + 5; ++i
)
287 std::cerr
<< std::endl
;
288 std::cerr
<< std::endl
;
291 // End of debug prints
294 if( objective
< objGoal
)
299 // Pick a pivot column. That is, the non-basic variable with the most positive coefficient
300 size_t * nonBasicCol
= 0;
303 for( size_t * src
= nonBasicBegin_
; src
!= nonBasicEnd_
; ++src
)
305 if( *( c_
+ *src
) > best
)
307 best
= *( c_
+ *src
);
312 if( nonBasicCol
== 0 )
317 size_t col
= *nonBasicCol
;
319 // Find the outgoing row
322 double thMin
= HUGE_VAL
;
323 const double * srca
= a_
+ col
;
324 const double * srcb
= b_
;
325 for( size_t i
= 0; i
< nEqns_
; ++i
, srca
+= nExt_
, ++srcb
)
329 double tmp
= *srcb
/ *srca
;
339 // There is no constraining equation.
341 // This return value is special, and does not correspond to the returned *dstx.
342 objective
= -HUGE_VAL
;
348 // Normalize the pivot
349 double * dst
= a_
+ nExt_
* row
;
350 double tmp
= 1. / *( dst
+ col
);
351 double * end
= dst
+ nExt_
;
352 for( ; dst
!= end
; ++dst
)
356 *( b_
+ row
) *= tmp
;
362 // Note that structural zeroes are kept track of using the basic/nonBasic distinction, and need not be enforced in a.
365 double * enda
= a_
+ ( nExt_
* nEqns_
);
366 const double * pivota
= a_
+ nExt_
* row
;
368 double pivotb
= *( b_
+ row
);
369 for( ; dst
!= enda
; ++dstb
)
376 double * end
= dst
+ nExt_
;
377 const double * src
= pivota
;
378 double tmp
= *( dst
+ col
);
379 for( ; dst
!= end
; ++dst
, ++src
)
383 *dstb
-= tmp
* pivotb
;
387 // "Reduce objective"
388 const double * src
= pivota
;
390 double * end
= dst
+ nExt_
;
391 double tmp
= *( dst
+ col
);
392 for( ; dst
!= end
; ++dst
, ++src
)
396 objective
-= tmp
* pivotb
;
403 *nonBasicCol
= *( basicBegin_
+ row
);
404 *( basicBegin_
+ row
) = col
;
412 double * end
= dst
+ nVars_
;
413 for( ; dst
!= end
; ++dst
)
417 const double * srcb
= b_
;
418 for( const size_t * src
= basicBegin_
; src
!= basicEnd_
; ++src
, ++srcb
)
422 *( xdst
+ *src
) = *srcb
;