From ade85ef1d6cea62110e02a426f84042edd6613b9 Mon Sep 17 00:00:00 2001 From: Michael Orlitzky Date: Mon, 26 Apr 2010 15:40:38 -0400 Subject: [PATCH] Change MINIMUM, MAXIMUM to MINIMIZE, MAXIMIZE respectively. Add all useful lp_solve properties as properties of the LinearProgram class. Create the lp_solve instance of a linear program on-demand. Cache changes to the linear program until needed. --- src/LinearProgramming.py | 307 +++++++++++++++++++++++++++++++++++++-- 1 file changed, 294 insertions(+), 13 deletions(-) diff --git a/src/LinearProgramming.py b/src/LinearProgramming.py index 7f27409..71d02ff 100644 --- a/src/LinearProgramming.py +++ b/src/LinearProgramming.py @@ -15,25 +15,306 @@ site.addsitedir(os.path.dirname(os.path.abspath(sys.argv[0])) + LP_SOLVE_PATH) from lp_solve import * -MINIMUM = 0 -MAXIMUM = 1 + +# Constants representing the two types of linear programs. +# MINIMIZE means that we would like to minimize the objective +# function, and MAXIMIZE means that we would like to maximize it. +MINIMIZE = 0 +MAXIMIZE = 1 + class LinearProgram(object): """ - Represents an instance of an lp_solve linear program. + Represents an instance of an lp_solve linear program. + The actual lp_solve linear program is only created when it + is needed, and modifications to it are cached beforehand. """ - + + + def get_row_count(self): + """ + Return the number of rows in the constraint matrix. + """ + return len(self.constraint_matrix) + + + def get_column_count(self): + """ + Return the number of columns in the constraint matrix. + If we don't have any rows yet, claim zero columns as well. + """ + if self.get_row_count() == 0: + return 0 + else: + return len(self.constraint_matrix[0]) + + + + @property + def type(self): + """ + A property representing the type of linear program, either + MINIMIZE or MAXIMIZE. + """ + return self._type + + + def type(self, type): + if type == MINIMIZE: + self._type = MINIMIZE + if self._lp != None: + lpsolve('set_minim', self._lp) + else: + self._type = MAXIMIZE + if self._lp != None: + lpsolve('set_maxim', self._lp) + + + + @property + def objective_coefficients(self): + return self._objective_coefficients + + + @objective_coefficients.setter + def objective_coefficients(self, value): + self._objective_coefficients = value + + if self._lp != None: + lpsolve('set_obj_fn', + self._lp, + self._objective_coefficients) + + + + @property + def constraint_matrix(self): + return self._constraint_matrix + + @constraint_matrix.setter + def constraint_matrix(self, value): + self._constraint_matrix = value + + if self._lp != None: + lpsolve('set_mat', self._lp, value) + + + + @property + def rhs(self): + return self._rhs + + @rhs.setter + def rhs(self, value): + self._rhs = value + + if self._lp != None: + lpsolve('set_rh_vec', self._lp, self._rhs) + + + + @property + def inequalities(self): + return self._inequalities + + @inequalities.setter + def inequalities(self, value): + self._inequalities = value + + if self._lp != None: + for i in range(self.get_row_count()): + lpsolve('set_constr_type', self._lp, i+1, value[i]) + + + @property + def solution_lower_bounds(self): + return self._solution_lower_bounds + + @solution_lower_bounds.setter + def solution_lower_bounds(self, value): + if len(value) != self.get_column_count(): + return + + self._solution_lower_bounds = value + + if self._lp != None: + for i in range(self.get_column_count()): + lpsolve('set_lowbo', self._lp, i+1, value[i]) + + + + @property + def solution_upper_bounds(self): + return self._solution_upper_bounds + + + @solution_upper_bounds.setter + def solution_upper_bounds(self, value): + if len(value) != self.get_column_count(): + return + + self._solution_upper_bounds = value + + if self._lp != None: + for i in range(self.get_column_count()): + lpsolve('set_upbo', self._lp, i+1, value[i]) + + + + @property + def integer_variables(self): + """ + A vector containing the indices of any solution variables + which must be integers. + """ + return self._integer_variables + + @integer_variables.setter + def integer_variables(self, value): + self._integer_variables = value + + if self._lp != None: + for i in range(len(value)): + lpsolve('set_int', self._lp, value[i], 1) + + + + def make_all_variables_integers(self): + """ + Force all solution variables to be integers. This is achieved + by filling the integer_variables vector with all possible + indices. + """ + ivs = [] + + for i in range(self.get_column_count()): + ivs.append(i+1) + if self._lp != None: + lpsolve('set_int', self._lp, i+1, 1) + + self.integer_variables = ivs + + + + @property + def scale_mode(self): + """ + The scaling mode used for handling floating point numbers. + See for more + information. + """ + return self._scale_mode + + + @scale_mode.setter + def scale_mode(self, value): + self._scale_mode = value + + if self._lp != None: + lpsolve('set_scaling', self._lp, value) + + + def __init__(self): - self.objective_function_coefficients = [] - self.constraint_matrix = [] - self.rhs = [] - self.inequalities = [] + """ + Initialize the object, setting all of the properties + either empty or to sane defaults. + + The _lp variable is set to None, initially. All of the + property setters will test for _lp == None, and will refuse + to make calls to lp_solve if that is the case. A new instance + of an lp_solve linear program will be created (and stored in + the _lp variable) on demand. + + If the _lp variable is *not* None, the property setters will + make calls to lp_solve, updating the pre-existing linear program. + """ + + self._lp = None + self._objective_coefficients = [] + self._constraint_matrix = [] + self._rhs = [] + self._inequalities = [] + self._integer_variables = [] + self._solution_lower_bounds = [] + self._solution_upper_bounds = [] + self._scale_mode = 0 + self._type = MINIMIZE + + + def set_all_lp_properties(self): + """ + Re-set all linear program properties. After a new linear + program is created, it will be 'empty'. We already have + its properties stored in our member variables, however, + we need to make calls to lp_solve to set them on the new + linear program instance. + + All of the property setters will check for the existence of + self._lp and make calls to lp_solve as necessary. So, to set + all of our properties, we just have to trigger the property + setters a second time. + """ + self.constraint_matrix = self.constraint_matrix + self.rhs = self.rhs + self.objective_coefficients = self.objective_coefficients + self.inequalities = self.inequalities + self.integer_variables = self.integer_variables + self.solution_lower_bounds = self.solution_lower_bounds + self.solution_upper_bounds = self.solution_upper_bounds + self.scale_mode = self.scale_mode + self.type = self.type + + + + def delete(self): + if self._lp != None: + lpsolve('delete_lp', self._lp) + + + + def create_lp_if_necessary(self): + """ + If we already have a linear program instance, do nothing. + Otherwise, create one, and set all of the necessary properties. + """ + if self._lp != None: + return + + self._lp = lpsolve('make_lp', + self.get_row_count(), + self.get_column_count()) + + # This is not critical, but it will encourage lp_solve to + # warn us about potential problems. + lpsolve('set_verbose', self._lp, IMPORTANT) + + self.set_all_lp_properties() + def solve(self): - [v,x,duals] = lp_solve(self.objective_function_coefficients, - self.constraint_matrix, - self.rhs, - self.inequalities) - return [v,x,duals] + """ + Solve the linear program. The lp_solve instance is + created beforehand if necessary. + """ + self.create_lp_if_necessary() + result = lpsolve('solve', self._lp) + + # Default to empty return values. + obj = [] + x = [] + duals = [] + + # See http://lpsolve.sourceforge.net/5.5/solve.htm for a + # description of these constants. + if (result == OPTIMAL or + result == SUBOPTIMAL or + result == PROCBREAK or + result == FEASFOUND): + + # If the result was "good," i.e. if get_solution will work, + # call it and use its return value as ours. + [obj, x, duals, ret] = lpsolve('get_solution', self._lp) + return [obj, x, duals] -- 2.44.2