src/LinearProgramming.py

   1 """
   2 Classes to create, solve, and make dinner for linear programs. Handles
   3 integration with lp_solve.
   4 """
   5
   6 import os
   7 import site
   8 import sys
   9
  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
  12 # characters.
  13 LP_SOLVE_PATH = '/../lib/lp_solve'
  14 site.addsitedir(os.path.dirname(os.path.abspath(sys.argv[0])) + LP_SOLVE_PATH)
  15
  16 from lp_solve import *
  17
  18
  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.
  22 MINIMIZE = 0
  23 MAXIMIZE = 1
  24
  25
  26 class LinearProgram(object):
  27     """
  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.
  31     """
  32
  33
  34     def get_row_count(self):
  35         """
  36         Return the number of rows in the constraint matrix.
  37         """
  38         return len(self.constraint_matrix)
  39
  40
  41     def get_column_count(self):
  42         """
  43         Return the number of columns in the constraint matrix.
  44         If we don't have any rows yet, claim zero columns as well.
  45         """
  46         if self.get_row_count() == 0:
  47             return 0
  48         else:
  49             return len(self.constraint_matrix[0])
  50
  51
  52
  53     @property
  54     def type(self):
  55         """
  56         A property representing the type of linear program, either
  57         MINIMIZE or MAXIMIZE.
  58         """
  59         return self._type
  60
  61
  62     def type(self, type):
  63         if type == MINIMIZE:
  64             self._type = MINIMIZE
  65             if self._lp != None:
  66                 lpsolve('set_minim', self._lp)
  67         else:
  68             self._type = MAXIMIZE
  69             if self._lp != None:
  70                 lpsolve('set_maxim', self._lp)
  71
  72
  73
  74     @property
  75     def objective_coefficients(self):
  76         return self._objective_coefficients
  77
  78
  79     @objective_coefficients.setter
  80     def objective_coefficients(self, value):
  81         self._objective_coefficients = value
  82
  83         if self._lp != None:
  84             lpsolve('set_obj_fn',
  85                     self._lp,
  86                     self._objective_coefficients)
  87
  88
  89
  90     @property
  91     def constraint_matrix(self):
  92         return self._constraint_matrix
  93
  94     @constraint_matrix.setter
  95     def constraint_matrix(self, value):
  96         self._constraint_matrix = value
  97
  98         if self._lp != None:
  99             lpsolve('set_mat', self._lp, value)
 100
 101
 102
 103     @property
 104     def rhs(self):
 105         return self._rhs
 106
 107     @rhs.setter
 108     def rhs(self, value):
 109         self._rhs = value
 110
 111         if self._lp != None:
 112             lpsolve('set_rh_vec', self._lp, self._rhs)
 113
 114
 115
 116     @property
 117     def inequalities(self):
 118         return self._inequalities
 119
 120     @inequalities.setter
 121     def inequalities(self, value):
 122         self._inequalities = value
 123
 124         if self._lp != None:
 125             for i in range(self.get_row_count()):
 126                 lpsolve('set_constr_type', self._lp, i+1, value[i])
 127
 128
 129     @property
 130     def solution_lower_bounds(self):
 131         return self._solution_lower_bounds
 132
 133     @solution_lower_bounds.setter
 134     def solution_lower_bounds(self, value):
 135         if len(value) != self.get_column_count():
 136             return
 137
 138         self._solution_lower_bounds = value
 139
 140         if self._lp != None:
 141             for i in range(self.get_column_count()):
 142                 lpsolve('set_lowbo', self._lp, i+1, value[i])
 143
 144
 145
 146     @property
 147     def solution_upper_bounds(self):
 148         return self._solution_upper_bounds
 149
 150
 151     @solution_upper_bounds.setter
 152     def solution_upper_bounds(self, value):
 153         if len(value) != self.get_column_count():
 154             return
 155
 156         self._solution_upper_bounds = value
 157
 158         if self._lp != None:
 159             for i in range(self.get_column_count()):
 160                 lpsolve('set_upbo', self._lp, i+1, value[i])
 161
 162
 163
 164     @property
 165     def integer_variables(self):
 166         """
 167         A vector containing the indices of any solution variables
 168         which must be integers.
 169         """
 170         return self._integer_variables
 171
 172     @integer_variables.setter
 173     def integer_variables(self, value):
 174         self._integer_variables = value
 175
 176         if self._lp != None:
 177             for i in range(len(value)):
 178                 lpsolve('set_int', self._lp, value[i], 1)
 179
 180
 181
 182     def make_all_variables_integers(self):
 183         """
 184         Force all solution variables to be integers. This is achieved
 185         by filling the integer_variables vector with all possible
 186         indices.
 187         """
 188         ivs = []
 189
 190         for i in range(self.get_column_count()):
 191             ivs.append(i+1)
 192             if self._lp != None:
 193                 lpsolve('set_int', self._lp, i+1, 1)
 194
 195         self.integer_variables = ivs
 196
 197
 198
 199     @property
 200     def scale_mode(self):
 201         """
 202         The scaling mode used for handling floating point numbers.
 203         See <http://lpsolve.sourceforge.net/5.5/scaling.htm> for more
 204         information.
 205         """
 206         return self._scale_mode
 207
 208
 209     @scale_mode.setter
 210     def scale_mode(self, value):
 211         self._scale_mode = value
 212
 213         if self._lp != None:
 214             lpsolve('set_scaling', self._lp, value)
 215
 216
 217
 218     def __init__(self):
 219         """
 220         Initialize the object, setting all of the properties
 221         either empty or to sane defaults.
 222
 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.
 228
 229         If the _lp variable is *not* None, the property setters will
 230         make calls to lp_solve, updating the pre-existing linear program.
 231         """
 232
 233         self._lp = None
 234         self._objective_coefficients = []
 235         self._constraint_matrix = []
 236         self._rhs = []
 237         self._inequalities = []
 238         self._integer_variables = []
 239         self._solution_lower_bounds = []
 240         self._solution_upper_bounds = []
 241         self._scale_mode = 0
 242         self._type = MINIMIZE
 243
 244
 245     def set_all_lp_properties(self):
 246         """
 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.
 252
 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.
 257         """
 258         self.constraint_matrix = self.constraint_matrix
 259         self.rhs = self.rhs
 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
 267
 268
 269
 270     def delete(self):
 271         if self._lp != None:
 272             lpsolve('delete_lp', self._lp)
 273
 274
 275
 276     def create_lp_if_necessary(self):
 277         """
 278         If we already have a linear program instance, do nothing.
 279         Otherwise, create one, and set all of the necessary properties.
 280         """
 281         if self._lp != None:
 282             return
 283
 284         self._lp = lpsolve('make_lp',
 285                            self.get_row_count(),
 286                            self.get_column_count())
 287
 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)
 291
 292         self.set_all_lp_properties()
 293
 294
 295
 296     def solve(self):
 297         """
 298         Solve the linear program. The lp_solve instance is
 299         created beforehand if necessary.
 300         """
 301         self.create_lp_if_necessary()
 302         result = lpsolve('solve', self._lp)
 303
 304         # Default to empty return values.
 305         obj = []
 306         x = []
 307         duals = []
 308
 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):
 315
 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)
 319
 320         return [obj, x, duals]