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 fractions
   7 import os
   8 import site
   9 import sys
  10
  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
  13 # characters.
  14 LP_SOLVE_PATH = '/../../lib/lp_solve'
  15 site.addsitedir(os.path.dirname(os.path.abspath(sys.argv[0])) + LP_SOLVE_PATH)
  16
  17 from lpsolve55 import *
  18
  19
  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.
  23 MINIMIZE = 0
  24 MAXIMIZE = 1
  25
  26
  27 class LinearProgram(object):
  28     """
  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.
  32     """
  33
  34
  35     def get_row_count(self):
  36         """
  37         Return the number of rows in the constraint matrix.
  38         """
  39         return len(self.constraint_matrix)
  40
  41
  42     def get_column_count(self):
  43         """
  44         Return the number of columns in the constraint matrix.
  45         If we don't have any rows yet, claim zero columns as well.
  46         """
  47         if self.get_row_count() == 0:
  48             return 0
  49         else:
  50             return len(self.constraint_matrix[0])
  51
  52
  53
  54     @property
  55     def type(self):
  56         """
  57         A property representing the type of linear program, either
  58         MINIMIZE or MAXIMIZE.
  59         """
  60         return self._type
  61
  62     @type.setter
  63     def type(self, type):
  64         if type == MINIMIZE:
  65             self._type = MINIMIZE
  66             if self._lp != None:
  67                 lpsolve('set_minim', self._lp)
  68         else:
  69             self._type = MAXIMIZE
  70             if self._lp != None:
  71                 lpsolve('set_maxim', self._lp)
  72
  73
  74
  75     @property
  76     def objective_coefficients(self):
  77         return self._objective_coefficients
  78
  79
  80     @objective_coefficients.setter
  81     def objective_coefficients(self, value):
  82         self._objective_coefficients = value
  83
  84         if self._lp != None:
  85             lpsolve('set_obj_fn',
  86                     self._lp,
  87                     self._objective_coefficients)
  88
  89
  90
  91     @property
  92     def constraint_matrix(self):
  93         return self._constraint_matrix
  94
  95     @constraint_matrix.setter
  96     def constraint_matrix(self, value):
  97         self._constraint_matrix = value
  98
  99         if self._lp != None:
 100             lpsolve('set_mat', self._lp, value)
 101
 102
 103
 104     @property
 105     def rhs(self):
 106         return self._rhs
 107
 108     @rhs.setter
 109     def rhs(self, value):
 110         self._rhs = value
 111
 112         if self._lp != None:
 113             lpsolve('set_rh_vec', self._lp, self._rhs)
 114
 115
 116
 117     @property
 118     def inequalities(self):
 119         return self._inequalities
 120
 121     @inequalities.setter
 122     def inequalities(self, value):
 123         self._inequalities = value
 124
 125         if self._lp != None:
 126             for i in range(self.get_row_count()):
 127                 lpsolve('set_constr_type', self._lp, i+1, value[i])
 128
 129
 130     @property
 131     def solution_lower_bounds(self):
 132         return self._solution_lower_bounds
 133
 134     @solution_lower_bounds.setter
 135     def solution_lower_bounds(self, value):
 136         if len(value) != self.get_column_count():
 137             return
 138
 139         self._solution_lower_bounds = value
 140
 141         if self._lp != None:
 142             for i in range(self.get_column_count()):
 143                 lpsolve('set_lowbo', self._lp, i+1, value[i])
 144
 145
 146
 147     @property
 148     def solution_upper_bounds(self):
 149         return self._solution_upper_bounds
 150
 151
 152     @solution_upper_bounds.setter
 153     def solution_upper_bounds(self, value):
 154         if len(value) != self.get_column_count():
 155             return
 156
 157         self._solution_upper_bounds = value
 158
 159         if self._lp != None:
 160             for i in range(self.get_column_count()):
 161                 lpsolve('set_upbo', self._lp, i+1, value[i])
 162
 163
 164
 165     @property
 166     def integer_variables(self):
 167         """
 168         A vector containing the indices of any solution variables
 169         which must be integers.
 170         """
 171         return self._integer_variables
 172
 173     @integer_variables.setter
 174     def integer_variables(self, value):
 175         self._integer_variables = value
 176
 177         if self._lp != None:
 178             for i in range(len(value)):
 179                 lpsolve('set_int', self._lp, value[i], 1)
 180
 181
 182
 183     def make_all_variables_integers(self):
 184         """
 185         Force all solution variables to be integers. This is achieved
 186         by filling the integer_variables vector with all possible
 187         indices.
 188         """
 189         ivs = []
 190
 191         for i in range(self.get_column_count()):
 192             ivs.append(i+1)
 193             if self._lp != None:
 194                 lpsolve('set_int', self._lp, i+1, 1)
 195
 196         self.integer_variables = ivs
 197
 198
 199
 200     @property
 201     def scale_mode(self):
 202         """
 203         The scaling mode used for handling floating point numbers.
 204         See <http://lpsolve.sourceforge.net/5.5/scaling.htm> for more
 205         information.
 206         """
 207         return self._scale_mode
 208
 209
 210     @scale_mode.setter
 211     def scale_mode(self, value):
 212         self._scale_mode = value
 213
 214         if self._lp != None:
 215             lpsolve('set_scaling', self._lp, value)
 216
 217
 218
 219     def print_tableau(self):
 220         """
 221         Tell lp_solve to print its simplex tableau. Only works after
 222         a successful call to solve().
 223         """
 224         lpsolve('set_outputfile', self._lp, '')
 225         lpsolve('print_tableau', self._lp)
 226
 227
 228     def __init__(self):
 229         """
 230         Initialize the object, setting all of the properties
 231         either empty or to sane defaults.
 232
 233         The _lp variable is set to None, initially. All of the
 234         property setters will test for _lp == None, and will refuse
 235         to make calls to lp_solve if that is the case. A new instance
 236         of an lp_solve linear program will be created (and stored in
 237         the _lp variable) on demand.
 238
 239         If the _lp variable is *not* None, the property setters will
 240         make calls to lp_solve, updating the pre-existing linear program.
 241         """
 242
 243         self._lp = None
 244         self._objective_coefficients = []
 245         self._constraint_matrix = []
 246         self._rhs = []
 247         self._inequalities = []
 248         self._integer_variables = []
 249         self._solution_lower_bounds = []
 250         self._solution_upper_bounds = []
 251         self._scale_mode = 0
 252         self._type = MINIMIZE
 253
 254
 255     def set_all_lp_properties(self):
 256         """
 257         Re-set all linear program properties. After a new linear
 258         program is created, it will be 'empty'. We already have
 259         its properties stored in our member variables, however,
 260         we need to make calls to lp_solve to set them on the new
 261         linear program instance.
 262
 263         All of the property setters will check for the existence of
 264         self._lp and make calls to lp_solve as necessary. So, to set
 265         all of our properties, we just have to trigger the property
 266         setters a second time.
 267         """
 268         self.constraint_matrix = self.constraint_matrix
 269         self.rhs = self.rhs
 270         self.objective_coefficients = self.objective_coefficients
 271         self.inequalities = self.inequalities
 272         self.integer_variables = self.integer_variables
 273         self.solution_lower_bounds = self.solution_lower_bounds
 274         self.solution_upper_bounds = self.solution_upper_bounds
 275         self.scale_mode = self.scale_mode
 276         self.type = self.type
 277
 278
 279
 280     def delete(self):
 281         if self._lp != None:
 282             lpsolve('delete_lp', self._lp)
 283
 284
 285
 286     def create_lp_if_necessary(self):
 287         """
 288         If we already have a linear program instance, do nothing.
 289         Otherwise, create one, and set all of the necessary properties.
 290         """
 291         if self._lp != None:
 292             return
 293
 294         self._lp = lpsolve('make_lp',
 295                            self.get_row_count(),
 296                            self.get_column_count())
 297
 298         # This is not critical, but it will encourage lp_solve to
 299         # warn us about potential problems.
 300         lpsolve('set_verbose', self._lp, IMPORTANT)
 301
 302         self.set_all_lp_properties()
 303
 304
 305
 306     def solve(self):
 307         """
 308         Solve the linear program. The lp_solve instance is
 309         created beforehand if necessary.
 310         """
 311         self.create_lp_if_necessary()
 312         result = lpsolve('solve', self._lp)
 313
 314         # Default to empty return values.
 315         obj = []
 316         x = []
 317         duals = []
 318
 319         # See http://lpsolve.sourceforge.net/5.5/solve.htm for a
 320         # description of these constants.
 321         if (result == OPTIMAL    or
 322             result == SUBOPTIMAL or
 323             result == PROCBREAK  or
 324             result == FEASFOUND):
 325
 326             # If the result was "good," i.e. if get_solution will work,
 327             # call it and use its return value as ours.
 328             [obj, x, duals, ret] = lpsolve('get_solution', self._lp)
 329
 330         return [obj, x, duals]
 331
 332
 333     def objective_coefficient_gcd(self):
 334         """
 335         Return the GCD of all objective function coefficients.
 336         """
 337         return reduce(fractions.gcd, self.objective_coefficients)