]>
gitweb.michael.orlitzky.com - dead/census-tools.git/blob - LinearProgramming.py
5f4668a705d1e3972f42433ff045fa27ee427e71
2 Classes to create, solve, and make dinner for linear programs. Handles
3 integration with lp_solve.
10 # Add LP_SOLVE_PATH to our path. There is no point to this variable
11 # other than to make the site.addsitedir() line fit within 80
13 LP_SOLVE_PATH
= '/../lib/lp_solve'
14 site
.addsitedir(os
.path
.dirname(os
.path
.abspath(sys
.argv
[0])) + LP_SOLVE_PATH
)
16 from lpsolve55
import *
19 # Constants representing the two types of linear programs.
20 # MINIMIZE means that we would like to minimize the objective
21 # function, and MAXIMIZE means that we would like to maximize it.
26 class LinearProgram(object):
28 Represents an instance of an lp_solve linear program.
29 The actual lp_solve linear program is only created when it
30 is needed, and modifications to it are cached beforehand.
34 def get_row_count(self
):
36 Return the number of rows in the constraint matrix.
38 return len(self
.constraint_matrix
)
41 def get_column_count(self
):
43 Return the number of columns in the constraint matrix.
44 If we don't have any rows yet, claim zero columns as well.
46 if self
.get_row_count() == 0:
49 return len(self
.constraint_matrix
[0])
56 A property representing the type of linear program, either
66 lpsolve('set_minim', self
._lp
)
70 lpsolve('set_maxim', self
._lp
)
75 def objective_coefficients(self
):
76 return self
._objective
_coefficients
79 @objective_coefficients.setter
80 def objective_coefficients(self
, value
):
81 self
._objective
_coefficients
= value
86 self
._objective
_coefficients
)
91 def constraint_matrix(self
):
92 return self
._constraint
_matrix
94 @constraint_matrix.setter
95 def constraint_matrix(self
, value
):
96 self
._constraint
_matrix
= value
99 lpsolve('set_mat', self
._lp
, value
)
108 def rhs(self
, value
):
112 lpsolve('set_rh_vec', self
._lp
, self
._rhs
)
117 def inequalities(self
):
118 return self
._inequalities
121 def inequalities(self
, value
):
122 self
._inequalities
= value
125 for i
in range(self
.get_row_count()):
126 lpsolve('set_constr_type', self
._lp
, i
+1, value
[i
])
130 def solution_lower_bounds(self
):
131 return self
._solution
_lower
_bounds
133 @solution_lower_bounds.setter
134 def solution_lower_bounds(self
, value
):
135 if len(value
) != self
.get_column_count():
138 self
._solution
_lower
_bounds
= value
141 for i
in range(self
.get_column_count()):
142 lpsolve('set_lowbo', self
._lp
, i
+1, value
[i
])
147 def solution_upper_bounds(self
):
148 return self
._solution
_upper
_bounds
151 @solution_upper_bounds.setter
152 def solution_upper_bounds(self
, value
):
153 if len(value
) != self
.get_column_count():
156 self
._solution
_upper
_bounds
= value
159 for i
in range(self
.get_column_count()):
160 lpsolve('set_upbo', self
._lp
, i
+1, value
[i
])
165 def integer_variables(self
):
167 A vector containing the indices of any solution variables
168 which must be integers.
170 return self
._integer
_variables
172 @integer_variables.setter
173 def integer_variables(self
, value
):
174 self
._integer
_variables
= value
177 for i
in range(len(value
)):
178 lpsolve('set_int', self
._lp
, value
[i
], 1)
182 def make_all_variables_integers(self
):
184 Force all solution variables to be integers. This is achieved
185 by filling the integer_variables vector with all possible
190 for i
in range(self
.get_column_count()):
193 lpsolve('set_int', self
._lp
, i
+1, 1)
195 self
.integer_variables
= ivs
200 def scale_mode(self
):
202 The scaling mode used for handling floating point numbers.
203 See <http://lpsolve.sourceforge.net/5.5/scaling.htm> for more
206 return self
._scale
_mode
210 def scale_mode(self
, value
):
211 self
._scale
_mode
= value
214 lpsolve('set_scaling', self
._lp
, value
)
220 Initialize the object, setting all of the properties
221 either empty or to sane defaults.
223 The _lp variable is set to None, initially. All of the
224 property setters will test for _lp == None, and will refuse
225 to make calls to lp_solve if that is the case. A new instance
226 of an lp_solve linear program will be created (and stored in
227 the _lp variable) on demand.
229 If the _lp variable is *not* None, the property setters will
230 make calls to lp_solve, updating the pre-existing linear program.
234 self
._objective
_coefficients
= []
235 self
._constraint
_matrix
= []
237 self
._inequalities
= []
238 self
._integer
_variables
= []
239 self
._solution
_lower
_bounds
= []
240 self
._solution
_upper
_bounds
= []
242 self
._type
= MINIMIZE
245 def set_all_lp_properties(self
):
247 Re-set all linear program properties. After a new linear
248 program is created, it will be 'empty'. We already have
249 its properties stored in our member variables, however,
250 we need to make calls to lp_solve to set them on the new
251 linear program instance.
253 All of the property setters will check for the existence of
254 self._lp and make calls to lp_solve as necessary. So, to set
255 all of our properties, we just have to trigger the property
256 setters a second time.
258 self
.constraint_matrix
= self
.constraint_matrix
260 self
.objective_coefficients
= self
.objective_coefficients
261 self
.inequalities
= self
.inequalities
262 self
.integer_variables
= self
.integer_variables
263 self
.solution_lower_bounds
= self
.solution_lower_bounds
264 self
.solution_upper_bounds
= self
.solution_upper_bounds
265 self
.scale_mode
= self
.scale_mode
266 self
.type = self
.type
272 lpsolve('delete_lp', self
._lp
)
276 def create_lp_if_necessary(self
):
278 If we already have a linear program instance, do nothing.
279 Otherwise, create one, and set all of the necessary properties.
284 self
._lp
= lpsolve('make_lp',
285 self
.get_row_count(),
286 self
.get_column_count())
288 # This is not critical, but it will encourage lp_solve to
289 # warn us about potential problems.
290 lpsolve('set_verbose', self
._lp
, IMPORTANT
)
292 self
.set_all_lp_properties()
298 Solve the linear program. The lp_solve instance is
299 created beforehand if necessary.
301 self
.create_lp_if_necessary()
302 result
= lpsolve('solve', self
._lp
)
304 # Default to empty return values.
309 # See http://lpsolve.sourceforge.net/5.5/solve.htm for a
310 # description of these constants.
311 if (result
== OPTIMAL
or
312 result
== SUBOPTIMAL
or
313 result
== PROCBREAK
or
314 result
== FEASFOUND
):
316 # If the result was "good," i.e. if get_solution will work,
317 # call it and use its return value as ours.
318 [obj
, x
, duals
, ret
] = lpsolve('get_solution', self
._lp
)
320 return [obj
, x
, duals
]