]>
gitweb.michael.orlitzky.com - dead/census-tools.git/blob - src/LinearProgramming.py
2 Classes to create, solve, and make dinner for linear programs. Handles
3 integration with lp_solve.
11 # Add LP_SOLVE_PATH to our path. There is no point to this variable
12 # other than to make the site.addsitedir() line fit within 80
14 LP_SOLVE_PATH
= '/../lib/lp_solve'
15 site
.addsitedir(os
.path
.dirname(os
.path
.abspath(sys
.argv
[0])) + LP_SOLVE_PATH
)
17 from lpsolve55
import *
20 # Constants representing the two types of linear programs.
21 # MINIMIZE means that we would like to minimize the objective
22 # function, and MAXIMIZE means that we would like to maximize it.
27 class LinearProgram(object):
29 Represents an instance of an lp_solve linear program.
30 The actual lp_solve linear program is only created when it
31 is needed, and modifications to it are cached beforehand.
35 def get_row_count(self
):
37 Return the number of rows in the constraint matrix.
39 return len(self
.constraint_matrix
)
42 def get_column_count(self
):
44 Return the number of columns in the constraint matrix.
45 If we don't have any rows yet, claim zero columns as well.
47 if self
.get_row_count() == 0:
50 return len(self
.constraint_matrix
[0])
57 A property representing the type of linear program, either
67 lpsolve('set_minim', self
._lp
)
71 lpsolve('set_maxim', self
._lp
)
76 def objective_coefficients(self
):
77 return self
._objective
_coefficients
80 @objective_coefficients.setter
81 def objective_coefficients(self
, value
):
82 self
._objective
_coefficients
= value
87 self
._objective
_coefficients
)
92 def constraint_matrix(self
):
93 return self
._constraint
_matrix
95 @constraint_matrix.setter
96 def constraint_matrix(self
, value
):
97 self
._constraint
_matrix
= value
100 lpsolve('set_mat', self
._lp
, value
)
109 def rhs(self
, value
):
113 lpsolve('set_rh_vec', self
._lp
, self
._rhs
)
118 def inequalities(self
):
119 return self
._inequalities
122 def inequalities(self
, value
):
123 self
._inequalities
= value
126 for i
in range(self
.get_row_count()):
127 lpsolve('set_constr_type', self
._lp
, i
+1, value
[i
])
131 def solution_lower_bounds(self
):
132 return self
._solution
_lower
_bounds
134 @solution_lower_bounds.setter
135 def solution_lower_bounds(self
, value
):
136 if len(value
) != self
.get_column_count():
139 self
._solution
_lower
_bounds
= value
142 for i
in range(self
.get_column_count()):
143 lpsolve('set_lowbo', self
._lp
, i
+1, value
[i
])
148 def solution_upper_bounds(self
):
149 return self
._solution
_upper
_bounds
152 @solution_upper_bounds.setter
153 def solution_upper_bounds(self
, value
):
154 if len(value
) != self
.get_column_count():
157 self
._solution
_upper
_bounds
= value
160 for i
in range(self
.get_column_count()):
161 lpsolve('set_upbo', self
._lp
, i
+1, value
[i
])
166 def integer_variables(self
):
168 A vector containing the indices of any solution variables
169 which must be integers.
171 return self
._integer
_variables
173 @integer_variables.setter
174 def integer_variables(self
, value
):
175 self
._integer
_variables
= value
178 for i
in range(len(value
)):
179 lpsolve('set_int', self
._lp
, value
[i
], 1)
183 def make_all_variables_integers(self
):
185 Force all solution variables to be integers. This is achieved
186 by filling the integer_variables vector with all possible
191 for i
in range(self
.get_column_count()):
194 lpsolve('set_int', self
._lp
, i
+1, 1)
196 self
.integer_variables
= ivs
201 def scale_mode(self
):
203 The scaling mode used for handling floating point numbers.
204 See <http://lpsolve.sourceforge.net/5.5/scaling.htm> for more
207 return self
._scale
_mode
211 def scale_mode(self
, value
):
212 self
._scale
_mode
= value
215 lpsolve('set_scaling', self
._lp
, value
)
221 Initialize the object, setting all of the properties
222 either empty or to sane defaults.
224 The _lp variable is set to None, initially. All of the
225 property setters will test for _lp == None, and will refuse
226 to make calls to lp_solve if that is the case. A new instance
227 of an lp_solve linear program will be created (and stored in
228 the _lp variable) on demand.
230 If the _lp variable is *not* None, the property setters will
231 make calls to lp_solve, updating the pre-existing linear program.
235 self
._objective
_coefficients
= []
236 self
._constraint
_matrix
= []
238 self
._inequalities
= []
239 self
._integer
_variables
= []
240 self
._solution
_lower
_bounds
= []
241 self
._solution
_upper
_bounds
= []
243 self
._type
= MINIMIZE
246 def set_all_lp_properties(self
):
248 Re-set all linear program properties. After a new linear
249 program is created, it will be 'empty'. We already have
250 its properties stored in our member variables, however,
251 we need to make calls to lp_solve to set them on the new
252 linear program instance.
254 All of the property setters will check for the existence of
255 self._lp and make calls to lp_solve as necessary. So, to set
256 all of our properties, we just have to trigger the property
257 setters a second time.
259 self
.constraint_matrix
= self
.constraint_matrix
261 self
.objective_coefficients
= self
.objective_coefficients
262 self
.inequalities
= self
.inequalities
263 self
.integer_variables
= self
.integer_variables
264 self
.solution_lower_bounds
= self
.solution_lower_bounds
265 self
.solution_upper_bounds
= self
.solution_upper_bounds
266 self
.scale_mode
= self
.scale_mode
267 self
.type = self
.type
273 lpsolve('delete_lp', self
._lp
)
277 def create_lp_if_necessary(self
):
279 If we already have a linear program instance, do nothing.
280 Otherwise, create one, and set all of the necessary properties.
285 self
._lp
= lpsolve('make_lp',
286 self
.get_row_count(),
287 self
.get_column_count())
289 # This is not critical, but it will encourage lp_solve to
290 # warn us about potential problems.
291 lpsolve('set_verbose', self
._lp
, IMPORTANT
)
293 self
.set_all_lp_properties()
299 Solve the linear program. The lp_solve instance is
300 created beforehand if necessary.
302 self
.create_lp_if_necessary()
303 result
= lpsolve('solve', self
._lp
)
305 # Default to empty return values.
310 # See http://lpsolve.sourceforge.net/5.5/solve.htm for a
311 # description of these constants.
312 if (result
== OPTIMAL
or
313 result
== SUBOPTIMAL
or
314 result
== PROCBREAK
or
315 result
== FEASFOUND
):
317 # If the result was "good," i.e. if get_solution will work,
318 # call it and use its return value as ours.
319 [obj
, x
, duals
, ret
] = lpsolve('get_solution', self
._lp
)
321 return [obj
, x
, duals
]
324 def objective_coefficient_gcd(self
):
326 Return the GCD of all objective function coefficients.
328 return reduce(fractions
.gcd
, self
.objective_coefficients
)