1#! /usr/bin/env python 2# PuLP : Python LP Modeler 3 4 5# Copyright (c) 2002-2005, Jean-Sebastien Roy (js@jeannot.org) 6# Modifications Copyright (c) 2007- Stuart Anthony Mitchell (s.mitchell@auckland.ac.nz) 7# $Id: pulp.py 1791 2008-04-23 22:54:34Z smit023 $ 8 9# Permission is hereby granted, free of charge, to any person obtaining a 10# copy of this software and associated documentation files (the 11# "Software"), to deal in the Software without restriction, including 12# without limitation the rights to use, copy, modify, merge, publish, 13# distribute, sublicense, and/or sell copies of the Software, and to 14# permit persons to whom the Software is furnished to do so, subject to 15# the following conditions: 16 17# The above copyright notice and this permission notice shall be included 18# in all copies or substantial portions of the Software. 19 20# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 21# OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 22# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 23# IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY 24# CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, 25# TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE 26# SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 27 28""" 29PuLP is an LP modeler written in python. PuLP can generate MPS or LP files 30and call GLPK[1], COIN CLP/CBC[2], CPLEX[3], GUROBI[4] and MOSEK[5] to solve linear 31problems. 32 33See the examples directory for examples. 34 35The examples require at least a solver in your PATH or a shared library file. 36 37Documentation is found on https://www.coin-or.org/PuLP/. 38A comprehensive wiki can be found at https://www.coin-or.org/PuLP/ 39 40Use LpVariable() to create new variables. To create a variable 0 <= x <= 3 41>>> x = LpVariable("x", 0, 3) 42 43To create a variable 0 <= y <= 1 44>>> y = LpVariable("y", 0, 1) 45 46Use LpProblem() to create new problems. Create "myProblem" 47>>> prob = LpProblem("myProblem", const.LpMinimize) 48 49Combine variables to create expressions and constraints and add them to the 50problem. 51>>> prob += x + y <= 2 52 53If you add an expression (not a constraint), it will 54become the objective. 55>>> prob += -4 * x + y 56 57Choose a solver and solve the problem. ex: 58>>> status = prob.solve(PULP_CBC_CMD(msg=0)) 59 60Display the status of the solution 61>>> const.LpStatus[status] 62'Optimal' 63 64You can get the value of the variables using value(). ex: 65>>> value(x) 662.0 67 68Exported Classes: 69 - LpProblem -- Container class for a Linear programming problem 70 - LpVariable -- Variables that are added to constraints in the LP 71 - LpConstraint -- A constraint of the general form 72 a1x1+a2x2 ...anxn (<=, =, >=) b 73 - LpConstraintVar -- Used to construct a column of the model in column-wise 74 modelling 75 76Exported Functions: 77 - value() -- Finds the value of a variable or expression 78 - lpSum() -- given a list of the form [a1*x1, a2x2, ..., anxn] will construct 79 a linear expression to be used as a constraint or variable 80 - lpDot() --given two lists of the form [a1, a2, ..., an] and 81 [ x1, x2, ..., xn] will construct a linear epression to be used 82 as a constraint or variable 83 84Comments, bug reports, patches and suggestions are welcome. 85https://github.com/coin-or/pulp 86 87References: 88[1] http://www.gnu.org/software/glpk/glpk.html 89[2] http://www.coin-or.org/ 90[3] http://www.cplex.com/ 91[4] http://www.gurobi.com/ 92[5] http://www.mosek.com/ 93""" 94 95import sys 96import warnings 97from time import time 98 99from .apis import LpSolverDefault, PULP_CBC_CMD 100from .apis.core import clock 101from .utilities import value 102from . import constants as const 103from . import mps_lp as mpslp 104 105try: 106 from collections.abc import Iterable 107except ImportError: 108 # python 2.7 compatible 109 from collections import Iterable 110 111import logging 112 113log = logging.getLogger(__name__) 114 115try: # allow Python 2/3 compatibility 116 maketrans = str.maketrans 117except AttributeError: 118 from string import maketrans 119 120_DICT_TYPE = dict 121 122if sys.platform not in ["cli"]: 123 # iron python does not like an OrderedDict 124 try: 125 from odict import OrderedDict 126 127 _DICT_TYPE = OrderedDict 128 except ImportError: 129 pass 130 try: 131 # python 2.7 or 3.1 132 from collections import OrderedDict 133 134 _DICT_TYPE = OrderedDict 135 except ImportError: 136 pass 137 138try: 139 import ujson as json 140except ImportError: 141 import json 142 143import re 144 145 146class LpElement(object): 147 """Base class for LpVariable and LpConstraintVar""" 148 149 # To remove illegal characters from the names 150 illegal_chars = "-+[] ->/" 151 expression = re.compile("[{}]".format(re.escape(illegal_chars))) 152 trans = maketrans(illegal_chars, "________") 153 154 def setName(self, name): 155 if name: 156 if self.expression.match(name): 157 warnings.warn( 158 "The name {} has illegal characters that will be replaced by _".format( 159 name 160 ) 161 ) 162 self.__name = str(name).translate(self.trans) 163 else: 164 self.__name = None 165 166 def getName(self): 167 return self.__name 168 169 name = property(fget=getName, fset=setName) 170 171 def __init__(self, name): 172 self.name = name 173 # self.hash MUST be different for each variable 174 # else dict() will call the comparison operators that are overloaded 175 self.hash = id(self) 176 self.modified = True 177 178 def __hash__(self): 179 return self.hash 180 181 def __str__(self): 182 return self.name 183 184 def __repr__(self): 185 return self.name 186 187 def __neg__(self): 188 return -LpAffineExpression(self) 189 190 def __pos__(self): 191 return self 192 193 def __bool__(self): 194 return 1 195 196 def __add__(self, other): 197 return LpAffineExpression(self) + other 198 199 def __radd__(self, other): 200 return LpAffineExpression(self) + other 201 202 def __sub__(self, other): 203 return LpAffineExpression(self) - other 204 205 def __rsub__(self, other): 206 return other - LpAffineExpression(self) 207 208 def __mul__(self, other): 209 return LpAffineExpression(self) * other 210 211 def __rmul__(self, other): 212 return LpAffineExpression(self) * other 213 214 def __div__(self, other): 215 return LpAffineExpression(self) / other 216 217 def __rdiv__(self, other): 218 raise TypeError("Expressions cannot be divided by a variable") 219 220 def __le__(self, other): 221 return LpAffineExpression(self) <= other 222 223 def __ge__(self, other): 224 return LpAffineExpression(self) >= other 225 226 def __eq__(self, other): 227 return LpAffineExpression(self) == other 228 229 def __ne__(self, other): 230 if isinstance(other, LpVariable): 231 return self.name is not other.name 232 elif isinstance(other, LpAffineExpression): 233 if other.isAtomic(): 234 return self is not other.atom() 235 else: 236 return 1 237 else: 238 return 1 239 240 241class LpVariable(LpElement): 242 """ 243 This class models an LP Variable with the specified associated parameters 244 245 :param name: The name of the variable used in the output .lp file 246 :param lowBound: The lower bound on this variable's range. 247 Default is negative infinity 248 :param upBound: The upper bound on this variable's range. 249 Default is positive infinity 250 :param cat: The category this variable is in, Integer, Binary or 251 Continuous(default) 252 :param e: Used for column based modelling: relates to the variable's 253 existence in the objective function and constraints 254 """ 255 256 def __init__( 257 self, name, lowBound=None, upBound=None, cat=const.LpContinuous, e=None 258 ): 259 LpElement.__init__(self, name) 260 self._lowbound_original = self.lowBound = lowBound 261 self._upbound_original = self.upBound = upBound 262 self.cat = cat 263 self.varValue = None 264 self.dj = None 265 if cat == const.LpBinary: 266 self.lowBound = 0 267 self.upBound = 1 268 self.cat = const.LpInteger 269 # Code to add a variable to constraints for column based 270 # modelling. 271 if e: 272 self.add_expression(e) 273 274 def toDict(self): 275 """ 276 Exports a variable into a dictionary with its relevant information 277 278 :return: a dictionary with the variable information 279 :rtype: dict 280 """ 281 return dict( 282 lowBound=self.lowBound, 283 upBound=self.upBound, 284 cat=self.cat, 285 varValue=self.varValue, 286 dj=self.dj, 287 name=self.name, 288 ) 289 290 to_dict = toDict 291 292 @classmethod 293 def fromDict(cls, dj=None, varValue=None, **kwargs): 294 """ 295 Initializes a variable object from information that comes from a dictionary (kwargs) 296 297 :param dj: shadow price of the variable 298 :param float varValue: the value to set the variable 299 :param kwargs: arguments to initialize the variable 300 :return: a :py:class:`LpVariable` 301 :rtype: :LpVariable 302 """ 303 var = cls(**kwargs) 304 var.dj = dj 305 var.varValue = varValue 306 return var 307 308 from_dict = fromDict 309 310 def add_expression(self, e): 311 self.expression = e 312 self.addVariableToConstraints(e) 313 314 @classmethod 315 def matrix( 316 cls, 317 name, 318 indices=None, # required param. enforced within function for backwards compatibility 319 lowBound=None, 320 upBound=None, 321 cat=const.LpContinuous, 322 indexStart=[], 323 indexs=None, 324 ): 325 326 # Backwards Compatiblity with Deprecation Warning for indexs 327 if indices is not None and indexs is not None: 328 raise TypeError( 329 "Both 'indices' and 'indexs' provided to LpVariable.matrix. Use one only, preferably 'indices'." 330 ) 331 elif indices is not None: 332 pass 333 elif indexs is not None: 334 warnings.warn( 335 "'indexs' is deprecated; use 'indices'.", DeprecationWarning, 2 336 ) 337 indices = indexs 338 else: 339 raise TypeError( 340 "LpVariable.matrix missing both 'indices' and deprecated 'indexs' arguments." 341 ) 342 343 if not isinstance(indices, tuple): 344 indices = (indices,) 345 if "%" not in name: 346 name += "_%s" * len(indices) 347 348 index = indices[0] 349 indices = indices[1:] 350 if len(indices) == 0: 351 return [ 352 LpVariable(name % tuple(indexStart + [i]), lowBound, upBound, cat) 353 for i in index 354 ] 355 else: 356 return [ 357 LpVariable.matrix( 358 name, indices, lowBound, upBound, cat, indexStart + [i] 359 ) 360 for i in index 361 ] 362 363 @classmethod 364 def dicts( 365 cls, 366 name, 367 indices=None, # required param. enforced within function for backwards compatibility 368 lowBound=None, 369 upBound=None, 370 cat=const.LpContinuous, 371 indexStart=[], 372 indexs=None, 373 ): 374 """ 375 This function creates a dictionary of :py:class:`LpVariable` with the specified associated parameters. 376 377 :param name: The prefix to the name of each LP variable created 378 :param indices: A list of strings of the keys to the dictionary of LP 379 variables, and the main part of the variable name itself 380 :param lowBound: The lower bound on these variables' range. Default is 381 negative infinity 382 :param upBound: The upper bound on these variables' range. Default is 383 positive infinity 384 :param cat: The category these variables are in, Integer or 385 Continuous(default) 386 :param indexs: (deprecated) Replaced with `indices` parameter 387 388 :return: A dictionary of :py:class:`LpVariable` 389 """ 390 391 # Backwards Compatiblity with Deprecation Warning for indexs 392 if indices is not None and indexs is not None: 393 raise TypeError( 394 "Both 'indices' and 'indexs' provided to LpVariable.dicts. Use one only, preferably 'indices'." 395 ) 396 elif indices is not None: 397 pass 398 elif indexs is not None: 399 warnings.warn( 400 "'indexs' is deprecated; use 'indices'.", DeprecationWarning, 2 401 ) 402 indices = indexs 403 else: 404 raise TypeError( 405 "LpVariable.dicts missing both 'indices' and deprecated 'indexs' arguments." 406 ) 407 408 if not isinstance(indices, tuple): 409 indices = (indices,) 410 if "%" not in name: 411 name += "_%s" * len(indices) 412 413 index = indices[0] 414 indices = indices[1:] 415 d = {} 416 if len(indices) == 0: 417 for i in index: 418 d[i] = LpVariable( 419 name % tuple(indexStart + [str(i)]), lowBound, upBound, cat 420 ) 421 else: 422 for i in index: 423 d[i] = LpVariable.dicts( 424 name, indices, lowBound, upBound, cat, indexStart + [i] 425 ) 426 return d 427 428 @classmethod 429 def dict(cls, name, indices, lowBound=None, upBound=None, cat=const.LpContinuous): 430 if not isinstance(indices, tuple): 431 indices = (indices,) 432 if "%" not in name: 433 name += "_%s" * len(indices) 434 435 lists = indices 436 437 if len(indices) > 1: 438 # Cartesian product 439 res = [] 440 while len(lists): 441 first = lists[-1] 442 nres = [] 443 if res: 444 if first: 445 for f in first: 446 nres.extend([[f] + r for r in res]) 447 else: 448 nres = res 449 res = nres 450 else: 451 res = [[f] for f in first] 452 lists = lists[:-1] 453 index = [tuple(r) for r in res] 454 elif len(indices) == 1: 455 index = indices[0] 456 else: 457 return {} 458 459 d = {} 460 for i in index: 461 d[i] = cls(name % i, lowBound, upBound, cat) 462 return d 463 464 def getLb(self): 465 return self.lowBound 466 467 def getUb(self): 468 return self.upBound 469 470 def bounds(self, low, up): 471 self.lowBound = low 472 self.upBound = up 473 self.modified = True 474 475 def positive(self): 476 self.bounds(0, None) 477 478 def value(self): 479 return self.varValue 480 481 def round(self, epsInt=1e-5, eps=1e-7): 482 if self.varValue is not None: 483 if ( 484 self.upBound != None 485 and self.varValue > self.upBound 486 and self.varValue <= self.upBound + eps 487 ): 488 self.varValue = self.upBound 489 elif ( 490 self.lowBound != None 491 and self.varValue < self.lowBound 492 and self.varValue >= self.lowBound - eps 493 ): 494 self.varValue = self.lowBound 495 if ( 496 self.cat == const.LpInteger 497 and abs(round(self.varValue) - self.varValue) <= epsInt 498 ): 499 self.varValue = round(self.varValue) 500 501 def roundedValue(self, eps=1e-5): 502 if ( 503 self.cat == const.LpInteger 504 and self.varValue != None 505 and abs(self.varValue - round(self.varValue)) <= eps 506 ): 507 return round(self.varValue) 508 else: 509 return self.varValue 510 511 def valueOrDefault(self): 512 if self.varValue != None: 513 return self.varValue 514 elif self.lowBound != None: 515 if self.upBound != None: 516 if 0 >= self.lowBound and 0 <= self.upBound: 517 return 0 518 else: 519 if self.lowBound >= 0: 520 return self.lowBound 521 else: 522 return self.upBound 523 else: 524 if 0 >= self.lowBound: 525 return 0 526 else: 527 return self.lowBound 528 elif self.upBound != None: 529 if 0 <= self.upBound: 530 return 0 531 else: 532 return self.upBound 533 else: 534 return 0 535 536 def valid(self, eps): 537 if self.name == "__dummy" and self.varValue is None: 538 return True 539 if self.varValue is None: 540 return False 541 if self.upBound is not None and self.varValue > self.upBound + eps: 542 return False 543 if self.lowBound is not None and self.varValue < self.lowBound - eps: 544 return False 545 if ( 546 self.cat == const.LpInteger 547 and abs(round(self.varValue) - self.varValue) > eps 548 ): 549 return False 550 return True 551 552 def infeasibilityGap(self, mip=1): 553 if self.varValue == None: 554 raise ValueError("variable value is None") 555 if self.upBound != None and self.varValue > self.upBound: 556 return self.varValue - self.upBound 557 if self.lowBound != None and self.varValue < self.lowBound: 558 return self.varValue - self.lowBound 559 if ( 560 mip 561 and self.cat == const.LpInteger 562 and round(self.varValue) - self.varValue != 0 563 ): 564 return round(self.varValue) - self.varValue 565 return 0 566 567 def isBinary(self): 568 return self.cat == const.LpInteger and self.lowBound == 0 and self.upBound == 1 569 570 def isInteger(self): 571 return self.cat == const.LpInteger 572 573 def isFree(self): 574 return self.lowBound is None and self.upBound is None 575 576 def isConstant(self): 577 return self.lowBound is not None and self.upBound == self.lowBound 578 579 def isPositive(self): 580 return self.lowBound == 0 and self.upBound is None 581 582 def asCplexLpVariable(self): 583 if self.isFree(): 584 return self.name + " free" 585 if self.isConstant(): 586 return self.name + " = %.12g" % self.lowBound 587 if self.lowBound == None: 588 s = "-inf <= " 589 # Note: XPRESS and CPLEX do not interpret integer variables without 590 # explicit bounds 591 elif self.lowBound == 0 and self.cat == const.LpContinuous: 592 s = "" 593 else: 594 s = "%.12g <= " % self.lowBound 595 s += self.name 596 if self.upBound is not None: 597 s += " <= %.12g" % self.upBound 598 return s 599 600 def asCplexLpAffineExpression(self, name, constant=1): 601 return LpAffineExpression(self).asCplexLpAffineExpression(name, constant) 602 603 def __ne__(self, other): 604 if isinstance(other, LpElement): 605 return self.name is not other.name 606 elif isinstance(other, LpAffineExpression): 607 if other.isAtomic(): 608 return self is not other.atom() 609 else: 610 return 1 611 else: 612 return 1 613 614 def addVariableToConstraints(self, e): 615 """adds a variable to the constraints indicated by 616 the LpConstraintVars in e 617 """ 618 for constraint, coeff in e.items(): 619 constraint.addVariable(self, coeff) 620 621 def setInitialValue(self, val, check=True): 622 """ 623 sets the initial value of the variable to `val` 624 May be used for warmStart a solver, if supported by the solver 625 626 :param float val: value to set to variable 627 :param bool check: if True, we check if the value fits inside the variable bounds 628 :return: True if the value was set 629 :raises ValueError: if check=True and the value does not fit inside the bounds 630 """ 631 lb = self.lowBound 632 ub = self.upBound 633 config = [ 634 ("smaller", "lowBound", lb, lambda: val < lb), 635 ("greater", "upBound", ub, lambda: val > ub), 636 ] 637 638 for rel, bound_name, bound_value, condition in config: 639 if bound_value is not None and condition(): 640 if not check: 641 return False 642 raise ValueError( 643 "In variable {}, initial value {} is {} than {} {}".format( 644 self.name, val, rel, bound_name, bound_value 645 ) 646 ) 647 self.varValue = val 648 return True 649 650 def fixValue(self): 651 """ 652 changes lower bound and upper bound to the initial value if exists. 653 :return: None 654 """ 655 self._lowbound_unfix = self.lowBound 656 self._upbound_unfix = self.upBound 657 val = self.varValue 658 if val is not None: 659 self.bounds(val, val) 660 661 def isFixed(self): 662 """ 663 664 :return: True if upBound and lowBound are the same 665 :rtype: bool 666 """ 667 return self.isConstant() 668 669 def unfixValue(self): 670 self.bounds(self._lowbound_original, self._upbound_original) 671 672 673class LpAffineExpression(_DICT_TYPE): 674 """ 675 A linear combination of :class:`LpVariables<LpVariable>`. 676 Can be initialised with the following: 677 678 #. e = None: an empty Expression 679 #. e = dict: gives an expression with the values being the coefficients of the keys (order of terms is undetermined) 680 #. e = list or generator of 2-tuples: equivalent to dict.items() 681 #. e = LpElement: an expression of length 1 with the coefficient 1 682 #. e = other: the constant is initialised as e 683 684 Examples: 685 686 >>> f=LpAffineExpression(LpElement('x')) 687 >>> f 688 1*x + 0 689 >>> x_name = ['x_0', 'x_1', 'x_2'] 690 >>> x = [LpVariable(x_name[i], lowBound = 0, upBound = 10) for i in range(3) ] 691 >>> c = LpAffineExpression([ (x[0],1), (x[1],-3), (x[2],4)]) 692 >>> c 693 1*x_0 + -3*x_1 + 4*x_2 + 0 694 """ 695 696 # to remove illegal characters from the names 697 trans = maketrans("-+[] ", "_____") 698 699 def setName(self, name): 700 if name: 701 self.__name = str(name).translate(self.trans) 702 else: 703 self.__name = None 704 705 def getName(self): 706 return self.__name 707 708 name = property(fget=getName, fset=setName) 709 710 def __init__(self, e=None, constant=0, name=None): 711 self.name = name 712 # TODO remove isinstance usage 713 if e is None: 714 e = {} 715 if isinstance(e, LpAffineExpression): 716 # Will not copy the name 717 self.constant = e.constant 718 super(LpAffineExpression, self).__init__(list(e.items())) 719 elif isinstance(e, dict): 720 self.constant = constant 721 super(LpAffineExpression, self).__init__(list(e.items())) 722 elif isinstance(e, Iterable): 723 self.constant = constant 724 super(LpAffineExpression, self).__init__(e) 725 elif isinstance(e, LpElement): 726 self.constant = 0 727 super(LpAffineExpression, self).__init__([(e, 1)]) 728 else: 729 self.constant = e 730 super(LpAffineExpression, self).__init__() 731 732 # Proxy functions for variables 733 734 def isAtomic(self): 735 return len(self) == 1 and self.constant == 0 and list(self.values())[0] == 1 736 737 def isNumericalConstant(self): 738 return len(self) == 0 739 740 def atom(self): 741 return list(self.keys())[0] 742 743 # Functions on expressions 744 745 def __bool__(self): 746 return (float(self.constant) != 0.0) or (len(self) > 0) 747 748 def value(self): 749 s = self.constant 750 for v, x in self.items(): 751 if v.varValue is None: 752 return None 753 s += v.varValue * x 754 return s 755 756 def valueOrDefault(self): 757 s = self.constant 758 for v, x in self.items(): 759 s += v.valueOrDefault() * x 760 return s 761 762 def addterm(self, key, value): 763 y = self.get(key, 0) 764 if y: 765 y += value 766 self[key] = y 767 else: 768 self[key] = value 769 770 def emptyCopy(self): 771 return LpAffineExpression() 772 773 def copy(self): 774 """Make a copy of self except the name which is reset""" 775 # Will not copy the name 776 return LpAffineExpression(self) 777 778 def __str__(self, constant=1): 779 s = "" 780 for v in self.sorted_keys(): 781 val = self[v] 782 if val < 0: 783 if s != "": 784 s += " - " 785 else: 786 s += "-" 787 val = -val 788 elif s != "": 789 s += " + " 790 if val == 1: 791 s += str(v) 792 else: 793 s += str(val) + "*" + str(v) 794 if constant: 795 if s == "": 796 s = str(self.constant) 797 else: 798 if self.constant < 0: 799 s += " - " + str(-self.constant) 800 elif self.constant > 0: 801 s += " + " + str(self.constant) 802 elif s == "": 803 s = "0" 804 return s 805 806 def sorted_keys(self): 807 """ 808 returns the list of keys sorted by name 809 """ 810 result = [(v.name, v) for v in self.keys()] 811 result.sort() 812 result = [v for _, v in result] 813 return result 814 815 def __repr__(self): 816 l = [str(self[v]) + "*" + str(v) for v in self.sorted_keys()] 817 l.append(str(self.constant)) 818 s = " + ".join(l) 819 return s 820 821 @staticmethod 822 def _count_characters(line): 823 # counts the characters in a list of strings 824 return sum(len(t) for t in line) 825 826 def asCplexVariablesOnly(self, name): 827 """ 828 helper for asCplexLpAffineExpression 829 """ 830 result = [] 831 line = ["%s:" % name] 832 notFirst = 0 833 variables = self.sorted_keys() 834 for v in variables: 835 val = self[v] 836 if val < 0: 837 sign = " -" 838 val = -val 839 elif notFirst: 840 sign = " +" 841 else: 842 sign = "" 843 notFirst = 1 844 if val == 1: 845 term = "%s %s" % (sign, v.name) 846 else: 847 # adding zero to val to remove instances of negative zero 848 term = "%s %.12g %s" % (sign, val + 0, v.name) 849 850 if self._count_characters(line) + len(term) > const.LpCplexLPLineSize: 851 result += ["".join(line)] 852 line = [term] 853 else: 854 line += [term] 855 return result, line 856 857 def asCplexLpAffineExpression(self, name, constant=1): 858 """ 859 returns a string that represents the Affine Expression in lp format 860 """ 861 # refactored to use a list for speed in iron python 862 result, line = self.asCplexVariablesOnly(name) 863 if not self: 864 term = " %s" % self.constant 865 else: 866 term = "" 867 if constant: 868 if self.constant < 0: 869 term = " - %s" % (-self.constant) 870 elif self.constant > 0: 871 term = " + %s" % self.constant 872 if self._count_characters(line) + len(term) > const.LpCplexLPLineSize: 873 result += ["".join(line)] 874 line = [term] 875 else: 876 line += [term] 877 result += ["".join(line)] 878 result = "%s\n" % "\n".join(result) 879 return result 880 881 def addInPlace(self, other): 882 if isinstance(other, int) and (other == 0): 883 return self 884 if other is None: 885 return self 886 if isinstance(other, LpElement): 887 self.addterm(other, 1) 888 elif isinstance(other, LpAffineExpression): 889 self.constant += other.constant 890 for v, x in other.items(): 891 self.addterm(v, x) 892 elif isinstance(other, dict): 893 for e in other.values(): 894 self.addInPlace(e) 895 elif isinstance(other, list) or isinstance(other, Iterable): 896 for e in other: 897 self.addInPlace(e) 898 else: 899 self.constant += other 900 return self 901 902 def subInPlace(self, other): 903 if isinstance(other, int) and (other == 0): 904 return self 905 if other is None: 906 return self 907 if isinstance(other, LpElement): 908 self.addterm(other, -1) 909 elif isinstance(other, LpAffineExpression): 910 self.constant -= other.constant 911 for v, x in other.items(): 912 self.addterm(v, -x) 913 elif isinstance(other, dict): 914 for e in other.values(): 915 self.subInPlace(e) 916 elif isinstance(other, list) or isinstance(other, Iterable): 917 for e in other: 918 self.subInPlace(e) 919 else: 920 self.constant -= other 921 return self 922 923 def __neg__(self): 924 e = self.emptyCopy() 925 e.constant = -self.constant 926 for v, x in self.items(): 927 e[v] = -x 928 return e 929 930 def __pos__(self): 931 return self 932 933 def __add__(self, other): 934 return self.copy().addInPlace(other) 935 936 def __radd__(self, other): 937 return self.copy().addInPlace(other) 938 939 def __iadd__(self, other): 940 return self.addInPlace(other) 941 942 def __sub__(self, other): 943 return self.copy().subInPlace(other) 944 945 def __rsub__(self, other): 946 return (-self).addInPlace(other) 947 948 def __isub__(self, other): 949 return (self).subInPlace(other) 950 951 def __mul__(self, other): 952 e = self.emptyCopy() 953 if isinstance(other, LpAffineExpression): 954 e.constant = self.constant * other.constant 955 if len(other): 956 if len(self): 957 raise TypeError("Non-constant expressions cannot be multiplied") 958 else: 959 c = self.constant 960 if c != 0: 961 for v, x in other.items(): 962 e[v] = c * x 963 else: 964 c = other.constant 965 if c != 0: 966 for v, x in self.items(): 967 e[v] = c * x 968 elif isinstance(other, LpVariable): 969 return self * LpAffineExpression(other) 970 else: 971 if other != 0: 972 e.constant = self.constant * other 973 for v, x in self.items(): 974 e[v] = other * x 975 return e 976 977 def __rmul__(self, other): 978 return self * other 979 980 def __div__(self, other): 981 if isinstance(other, LpAffineExpression) or isinstance(other, LpVariable): 982 if len(other): 983 raise TypeError( 984 "Expressions cannot be divided by a non-constant expression" 985 ) 986 other = other.constant 987 e = self.emptyCopy() 988 e.constant = self.constant / other 989 for v, x in self.items(): 990 e[v] = x / other 991 return e 992 993 def __truediv__(self, other): 994 if isinstance(other, LpAffineExpression) or isinstance(other, LpVariable): 995 if len(other): 996 raise TypeError( 997 "Expressions cannot be divided by a non-constant expression" 998 ) 999 other = other.constant 1000 e = self.emptyCopy() 1001 e.constant = self.constant / other 1002 for v, x in self.items(): 1003 e[v] = x / other 1004 return e 1005 1006 def __rdiv__(self, other): 1007 e = self.emptyCopy() 1008 if len(self): 1009 raise TypeError( 1010 "Expressions cannot be divided by a non-constant expression" 1011 ) 1012 c = self.constant 1013 if isinstance(other, LpAffineExpression): 1014 e.constant = other.constant / c 1015 for v, x in other.items(): 1016 e[v] = x / c 1017 else: 1018 e.constant = other / c 1019 return e 1020 1021 def __le__(self, other): 1022 return LpConstraint(self - other, const.LpConstraintLE) 1023 1024 def __ge__(self, other): 1025 return LpConstraint(self - other, const.LpConstraintGE) 1026 1027 def __eq__(self, other): 1028 return LpConstraint(self - other, const.LpConstraintEQ) 1029 1030 def toDict(self): 1031 """ 1032 exports the :py:class:`LpAffineExpression` into a list of dictionaries with the coefficients 1033 it does not export the constant 1034 1035 :return: list of dictionaries with the coefficients 1036 :rtype: list 1037 """ 1038 return [dict(name=k.name, value=v) for k, v in self.items()] 1039 1040 to_dict = toDict 1041 1042 1043class LpConstraint(LpAffineExpression): 1044 """An LP constraint""" 1045 1046 def __init__(self, e=None, sense=const.LpConstraintEQ, name=None, rhs=None): 1047 """ 1048 :param e: an instance of :class:`LpAffineExpression` 1049 :param sense: one of :data:`~pulp.const.LpConstraintEQ`, :data:`~pulp.const.LpConstraintGE`, :data:`~pulp.const.LpConstraintLE` (0, 1, -1 respectively) 1050 :param name: identifying string 1051 :param rhs: numerical value of constraint target 1052 """ 1053 LpAffineExpression.__init__(self, e, name=name) 1054 if rhs is not None: 1055 self.constant -= rhs 1056 self.sense = sense 1057 self.pi = None 1058 self.slack = None 1059 self.modified = True 1060 1061 def getLb(self): 1062 if (self.sense == const.LpConstraintGE) or (self.sense == const.LpConstraintEQ): 1063 return -self.constant 1064 else: 1065 return None 1066 1067 def getUb(self): 1068 if (self.sense == const.LpConstraintLE) or (self.sense == const.LpConstraintEQ): 1069 return -self.constant 1070 else: 1071 return None 1072 1073 def __str__(self): 1074 s = LpAffineExpression.__str__(self, 0) 1075 if self.sense is not None: 1076 s += " " + const.LpConstraintSenses[self.sense] + " " + str(-self.constant) 1077 return s 1078 1079 def asCplexLpConstraint(self, name): 1080 """ 1081 Returns a constraint as a string 1082 """ 1083 result, line = self.asCplexVariablesOnly(name) 1084 if not list(self.keys()): 1085 line += ["0"] 1086 c = -self.constant 1087 if c == 0: 1088 c = 0 # Supress sign 1089 term = " %s %.12g" % (const.LpConstraintSenses[self.sense], c) 1090 if self._count_characters(line) + len(term) > const.LpCplexLPLineSize: 1091 result += ["".join(line)] 1092 line = [term] 1093 else: 1094 line += [term] 1095 result += ["".join(line)] 1096 result = "%s\n" % "\n".join(result) 1097 return result 1098 1099 def changeRHS(self, RHS): 1100 """ 1101 alters the RHS of a constraint so that it can be modified in a resolve 1102 """ 1103 self.constant = -RHS 1104 self.modified = True 1105 1106 def __repr__(self): 1107 s = LpAffineExpression.__repr__(self) 1108 if self.sense is not None: 1109 s += " " + const.LpConstraintSenses[self.sense] + " 0" 1110 return s 1111 1112 def copy(self): 1113 """Make a copy of self""" 1114 return LpConstraint(self, self.sense) 1115 1116 def emptyCopy(self): 1117 return LpConstraint(sense=self.sense) 1118 1119 def addInPlace(self, other): 1120 if isinstance(other, LpConstraint): 1121 if self.sense * other.sense >= 0: 1122 LpAffineExpression.addInPlace(self, other) 1123 self.sense |= other.sense 1124 else: 1125 LpAffineExpression.subInPlace(self, other) 1126 self.sense |= -other.sense 1127 elif isinstance(other, list): 1128 for e in other: 1129 self.addInPlace(e) 1130 else: 1131 LpAffineExpression.addInPlace(self, other) 1132 # raise TypeError, "Constraints and Expressions cannot be added" 1133 return self 1134 1135 def subInPlace(self, other): 1136 if isinstance(other, LpConstraint): 1137 if self.sense * other.sense <= 0: 1138 LpAffineExpression.subInPlace(self, other) 1139 self.sense |= -other.sense 1140 else: 1141 LpAffineExpression.addInPlace(self, other) 1142 self.sense |= other.sense 1143 elif isinstance(other, list): 1144 for e in other: 1145 self.subInPlace(e) 1146 else: 1147 LpAffineExpression.subInPlace(self, other) 1148 # raise TypeError, "Constraints and Expressions cannot be added" 1149 return self 1150 1151 def __neg__(self): 1152 c = LpAffineExpression.__neg__(self) 1153 c.sense = -c.sense 1154 return c 1155 1156 def __add__(self, other): 1157 return self.copy().addInPlace(other) 1158 1159 def __radd__(self, other): 1160 return self.copy().addInPlace(other) 1161 1162 def __sub__(self, other): 1163 return self.copy().subInPlace(other) 1164 1165 def __rsub__(self, other): 1166 return (-self).addInPlace(other) 1167 1168 def __mul__(self, other): 1169 if isinstance(other, LpConstraint): 1170 c = LpAffineExpression.__mul__(self, other) 1171 if c.sense == 0: 1172 c.sense = other.sense 1173 elif other.sense != 0: 1174 c.sense *= other.sense 1175 return c 1176 else: 1177 return LpAffineExpression.__mul__(self, other) 1178 1179 def __rmul__(self, other): 1180 return self * other 1181 1182 def __div__(self, other): 1183 if isinstance(other, LpConstraint): 1184 c = LpAffineExpression.__div__(self, other) 1185 if c.sense == 0: 1186 c.sense = other.sense 1187 elif other.sense != 0: 1188 c.sense *= other.sense 1189 return c 1190 else: 1191 return LpAffineExpression.__mul__(self, other) 1192 1193 def __rdiv__(self, other): 1194 if isinstance(other, LpConstraint): 1195 c = LpAffineExpression.__rdiv__(self, other) 1196 if c.sense == 0: 1197 c.sense = other.sense 1198 elif other.sense != 0: 1199 c.sense *= other.sense 1200 return c 1201 else: 1202 return LpAffineExpression.__mul__(self, other) 1203 1204 def valid(self, eps=0): 1205 val = self.value() 1206 if self.sense == const.LpConstraintEQ: 1207 return abs(val) <= eps 1208 else: 1209 return val * self.sense >= -eps 1210 1211 def makeElasticSubProblem(self, *args, **kwargs): 1212 """ 1213 Builds an elastic subproblem by adding variables to a hard constraint 1214 1215 uses FixedElasticSubProblem 1216 """ 1217 return FixedElasticSubProblem(self, *args, **kwargs) 1218 1219 def toDict(self): 1220 """ 1221 exports constraint information into a dictionary 1222 1223 :return: dictionary with all the constraint information 1224 """ 1225 return dict( 1226 sense=self.sense, 1227 pi=self.pi, 1228 constant=self.constant, 1229 name=self.name, 1230 coefficients=LpAffineExpression.toDict(self), 1231 ) 1232 1233 @classmethod 1234 def fromDict(cls, _dict): 1235 """ 1236 Initializes a constraint object from a dictionary with necessary information 1237 1238 :param dict _dict: dictionary with data 1239 :return: a new :py:class:`LpConstraint` 1240 """ 1241 const = cls( 1242 e=_dict["coefficients"], 1243 rhs=-_dict["constant"], 1244 name=_dict["name"], 1245 sense=_dict["sense"], 1246 ) 1247 const.pi = _dict["pi"] 1248 return const 1249 1250 from_dict = fromDict 1251 1252 1253class LpFractionConstraint(LpConstraint): 1254 """ 1255 Creates a constraint that enforces a fraction requirement a/b = c 1256 """ 1257 1258 def __init__( 1259 self, 1260 numerator, 1261 denominator=None, 1262 sense=const.LpConstraintEQ, 1263 RHS=1.0, 1264 name=None, 1265 complement=None, 1266 ): 1267 """ 1268 creates a fraction Constraint to model constraints of 1269 the nature 1270 numerator/denominator {==, >=, <=} RHS 1271 numerator/(numerator + complement) {==, >=, <=} RHS 1272 1273 :param numerator: the top of the fraction 1274 :param denominator: as described above 1275 :param sense: the sense of the relation of the constraint 1276 :param RHS: the target fraction value 1277 :param complement: as described above 1278 """ 1279 self.numerator = numerator 1280 if denominator is None and complement is not None: 1281 self.complement = complement 1282 self.denominator = numerator + complement 1283 elif denominator is not None and complement is None: 1284 self.denominator = denominator 1285 self.complement = denominator - numerator 1286 else: 1287 self.denominator = denominator 1288 self.complement = complement 1289 lhs = self.numerator - RHS * self.denominator 1290 LpConstraint.__init__(self, lhs, sense=sense, rhs=0, name=name) 1291 self.RHS = RHS 1292 1293 def findLHSValue(self): 1294 """ 1295 Determines the value of the fraction in the constraint after solution 1296 """ 1297 if abs(value(self.denominator)) >= const.EPS: 1298 return value(self.numerator) / value(self.denominator) 1299 else: 1300 if abs(value(self.numerator)) <= const.EPS: 1301 # zero divided by zero will return 1 1302 return 1.0 1303 else: 1304 raise ZeroDivisionError 1305 1306 def makeElasticSubProblem(self, *args, **kwargs): 1307 """ 1308 Builds an elastic subproblem by adding variables and splitting the 1309 hard constraint 1310 1311 uses FractionElasticSubProblem 1312 """ 1313 return FractionElasticSubProblem(self, *args, **kwargs) 1314 1315 1316class LpConstraintVar(LpElement): 1317 """A Constraint that can be treated as a variable when constructing 1318 a LpProblem by columns 1319 """ 1320 1321 def __init__(self, name=None, sense=None, rhs=None, e=None): 1322 LpElement.__init__(self, name) 1323 self.constraint = LpConstraint(name=self.name, sense=sense, rhs=rhs, e=e) 1324 1325 def addVariable(self, var, coeff): 1326 """ 1327 Adds a variable to the constraint with the 1328 activity coeff 1329 """ 1330 self.constraint.addterm(var, coeff) 1331 1332 def value(self): 1333 return self.constraint.value() 1334 1335 1336class LpProblem(object): 1337 """An LP Problem""" 1338 1339 def __init__(self, name="NoName", sense=const.LpMinimize): 1340 """ 1341 Creates an LP Problem 1342 1343 This function creates a new LP Problem with the specified associated parameters 1344 1345 :param name: name of the problem used in the output .lp file 1346 :param sense: of the LP problem objective. \ 1347 Either :data:`~pulp.const.LpMinimize` (default) \ 1348 or :data:`~pulp.const.LpMaximize`. 1349 :return: An LP Problem 1350 """ 1351 if " " in name: 1352 warnings.warn("Spaces are not permitted in the name. Converted to '_'") 1353 name = name.replace(" ", "_") 1354 self.objective = None 1355 self.constraints = _DICT_TYPE() 1356 self.name = name 1357 self.sense = sense 1358 self.sos1 = {} 1359 self.sos2 = {} 1360 self.status = const.LpStatusNotSolved 1361 self.sol_status = const.LpSolutionNoSolutionFound 1362 self.noOverlap = 1 1363 self.solver = None 1364 self.modifiedVariables = [] 1365 self.modifiedConstraints = [] 1366 self.resolveOK = False 1367 self._variables = [] 1368 self._variable_ids = {} # old school using dict.keys() for a set 1369 self.dummyVar = None 1370 self.solutionTime = 0 1371 self.solutionCpuTime = 0 1372 1373 # locals 1374 self.lastUnused = 0 1375 1376 def __repr__(self): 1377 s = self.name + ":\n" 1378 if self.sense == 1: 1379 s += "MINIMIZE\n" 1380 else: 1381 s += "MAXIMIZE\n" 1382 s += repr(self.objective) + "\n" 1383 1384 if self.constraints: 1385 s += "SUBJECT TO\n" 1386 for n, c in self.constraints.items(): 1387 s += c.asCplexLpConstraint(n) + "\n" 1388 s += "VARIABLES\n" 1389 for v in self.variables(): 1390 s += v.asCplexLpVariable() + " " + const.LpCategories[v.cat] + "\n" 1391 return s 1392 1393 def __getstate__(self): 1394 # Remove transient data prior to pickling. 1395 state = self.__dict__.copy() 1396 del state["_variable_ids"] 1397 return state 1398 1399 def __setstate__(self, state): 1400 # Update transient data prior to unpickling. 1401 self.__dict__.update(state) 1402 self._variable_ids = {} 1403 for v in self._variables: 1404 self._variable_ids[v.hash] = v 1405 1406 def copy(self): 1407 """Make a copy of self. Expressions are copied by reference""" 1408 lpcopy = LpProblem(name=self.name, sense=self.sense) 1409 lpcopy.objective = self.objective 1410 lpcopy.constraints = self.constraints.copy() 1411 lpcopy.sos1 = self.sos1.copy() 1412 lpcopy.sos2 = self.sos2.copy() 1413 return lpcopy 1414 1415 def deepcopy(self): 1416 """Make a copy of self. Expressions are copied by value""" 1417 lpcopy = LpProblem(name=self.name, sense=self.sense) 1418 if self.objective is not None: 1419 lpcopy.objective = self.objective.copy() 1420 lpcopy.constraints = {} 1421 for k, v in self.constraints.items(): 1422 lpcopy.constraints[k] = v.copy() 1423 lpcopy.sos1 = self.sos1.copy() 1424 lpcopy.sos2 = self.sos2.copy() 1425 return lpcopy 1426 1427 def toDict(self): 1428 """ 1429 creates a dictionary from the model with as much data as possible. 1430 It replaces variables by variable names. 1431 So it requires to have unique names for variables. 1432 1433 :return: dictionary with model data 1434 :rtype: dict 1435 """ 1436 try: 1437 self.checkDuplicateVars() 1438 except const.PulpError: 1439 raise const.PulpError( 1440 "Duplicated names found in variables:\nto export the model, variable names need to be unique" 1441 ) 1442 self.fixObjective() 1443 variables = self.variables() 1444 return dict( 1445 objective=dict( 1446 name=self.objective.name, coefficients=self.objective.toDict() 1447 ), 1448 constraints=[v.toDict() for v in self.constraints.values()], 1449 variables=[v.toDict() for v in variables], 1450 parameters=dict( 1451 name=self.name, 1452 sense=self.sense, 1453 status=self.status, 1454 sol_status=self.sol_status, 1455 ), 1456 sos1=list(self.sos1.values()), 1457 sos2=list(self.sos2.values()), 1458 ) 1459 1460 to_dict = toDict 1461 1462 @classmethod 1463 def fromDict(cls, _dict): 1464 """ 1465 Takes a dictionary with all necessary information to build a model. 1466 And returns a dictionary of variables and a problem object 1467 1468 :param _dict: dictionary with the model stored 1469 :return: a tuple with a dictionary of variables and a :py:class:`LpProblem` 1470 """ 1471 1472 # we instantiate the problem 1473 params = _dict["parameters"] 1474 pb_params = {"name", "sense"} 1475 args = {k: params[k] for k in pb_params} 1476 pb = cls(**args) 1477 pb.status = params["status"] 1478 pb.sol_status = params["sol_status"] 1479 1480 # recreate the variables. 1481 var = {v["name"]: LpVariable.fromDict(**v) for v in _dict["variables"]} 1482 1483 # objective function. 1484 # we change the names for the objects: 1485 obj_e = {var[v["name"]]: v["value"] for v in _dict["objective"]["coefficients"]} 1486 pb += LpAffineExpression(e=obj_e, name=_dict["objective"]["name"]) 1487 1488 # constraints 1489 # we change the names for the objects: 1490 def edit_const(const): 1491 const = dict(const) 1492 const["coefficients"] = { 1493 var[v["name"]]: v["value"] for v in const["coefficients"] 1494 } 1495 return const 1496 1497 constraints = [edit_const(v) for v in _dict["constraints"]] 1498 for c in constraints: 1499 pb += LpConstraint.fromDict(c) 1500 1501 # last, parameters, other options 1502 list_to_dict = lambda v: {k: v for k, v in enumerate(v)} 1503 pb.sos1 = list_to_dict(_dict["sos1"]) 1504 pb.sos2 = list_to_dict(_dict["sos2"]) 1505 1506 return var, pb 1507 1508 from_dict = fromDict 1509 1510 def toJson(self, filename, *args, **kwargs): 1511 """ 1512 Creates a json file from the LpProblem information 1513 1514 :param str filename: filename to write json 1515 :param args: additional arguments for json function 1516 :param kwargs: additional keyword arguments for json function 1517 :return: None 1518 """ 1519 with open(filename, "w") as f: 1520 json.dump(self.toDict(), f, *args, **kwargs) 1521 1522 to_json = toJson 1523 1524 @classmethod 1525 def fromJson(cls, filename): 1526 """ 1527 Creates a new Lp Problem from a json file with information 1528 1529 :param str filename: json file name 1530 :return: a tuple with a dictionary of variables and an LpProblem 1531 :rtype: (dict, :py:class:`LpProblem`) 1532 """ 1533 with open(filename, "r") as f: 1534 data = json.load(f) 1535 return cls.fromDict(data) 1536 1537 from_json = fromJson 1538 1539 @classmethod 1540 def fromMPS(cls, filename, sense=const.LpMinimize, **kwargs): 1541 data = mpslp.readMPS(filename, sense=sense, **kwargs) 1542 return cls.fromDict(data) 1543 1544 def normalisedNames(self): 1545 constraintsNames = {k: "C%07d" % i for i, k in enumerate(self.constraints)} 1546 _variables = self.variables() 1547 variablesNames = {k.name: "X%07d" % i for i, k in enumerate(_variables)} 1548 return constraintsNames, variablesNames, "OBJ" 1549 1550 def isMIP(self): 1551 for v in self.variables(): 1552 if v.cat == const.LpInteger: 1553 return 1 1554 return 0 1555 1556 def roundSolution(self, epsInt=1e-5, eps=1e-7): 1557 """ 1558 Rounds the lp variables 1559 1560 Inputs: 1561 - none 1562 1563 Side Effects: 1564 - The lp variables are rounded 1565 """ 1566 for v in self.variables(): 1567 v.round(epsInt, eps) 1568 1569 def unusedConstraintName(self): 1570 self.lastUnused += 1 1571 while 1: 1572 s = "_C%d" % self.lastUnused 1573 if s not in self.constraints: 1574 break 1575 self.lastUnused += 1 1576 return s 1577 1578 def valid(self, eps=0): 1579 for v in self.variables(): 1580 if not v.valid(eps): 1581 return False 1582 for c in self.constraints.values(): 1583 if not c.valid(eps): 1584 return False 1585 else: 1586 return True 1587 1588 def infeasibilityGap(self, mip=1): 1589 gap = 0 1590 for v in self.variables(): 1591 gap = max(abs(v.infeasibilityGap(mip)), gap) 1592 for c in self.constraints.values(): 1593 if not c.valid(0): 1594 gap = max(abs(c.value()), gap) 1595 return gap 1596 1597 def addVariable(self, variable): 1598 """ 1599 Adds a variable to the problem before a constraint is added 1600 1601 @param variable: the variable to be added 1602 """ 1603 if variable.hash not in self._variable_ids: 1604 self._variables.append(variable) 1605 self._variable_ids[variable.hash] = variable 1606 1607 def addVariables(self, variables): 1608 """ 1609 Adds variables to the problem before a constraint is added 1610 1611 @param variables: the variables to be added 1612 """ 1613 for v in variables: 1614 self.addVariable(v) 1615 1616 def variables(self): 1617 """ 1618 Returns the problem variables 1619 1620 :return: A list containing the problem variables 1621 :rtype: (list, :py:class:`LpVariable`) 1622 """ 1623 if self.objective: 1624 self.addVariables(list(self.objective.keys())) 1625 for c in self.constraints.values(): 1626 self.addVariables(list(c.keys())) 1627 self._variables.sort(key=lambda v: v.name) 1628 return self._variables 1629 1630 def variablesDict(self): 1631 variables = {} 1632 if self.objective: 1633 for v in self.objective: 1634 variables[v.name] = v 1635 for c in list(self.constraints.values()): 1636 for v in c: 1637 variables[v.name] = v 1638 return variables 1639 1640 def add(self, constraint, name=None): 1641 self.addConstraint(constraint, name) 1642 1643 def addConstraint(self, constraint, name=None): 1644 if not isinstance(constraint, LpConstraint): 1645 raise TypeError("Can only add LpConstraint objects") 1646 if name: 1647 constraint.name = name 1648 try: 1649 if constraint.name: 1650 name = constraint.name 1651 else: 1652 name = self.unusedConstraintName() 1653 except AttributeError: 1654 raise TypeError("Can only add LpConstraint objects") 1655 # removed as this test fails for empty constraints 1656 # if len(constraint) == 0: 1657 # if not constraint.valid(): 1658 # raise ValueError, "Cannot add false constraints" 1659 if name in self.constraints: 1660 if self.noOverlap: 1661 raise const.PulpError("overlapping constraint names: " + name) 1662 else: 1663 print("Warning: overlapping constraint names:", name) 1664 self.constraints[name] = constraint 1665 self.modifiedConstraints.append(constraint) 1666 self.addVariables(list(constraint.keys())) 1667 1668 def setObjective(self, obj): 1669 """ 1670 Sets the input variable as the objective function. Used in Columnwise Modelling 1671 1672 :param obj: the objective function of type :class:`LpConstraintVar` 1673 1674 Side Effects: 1675 - The objective function is set 1676 """ 1677 if isinstance(obj, LpVariable): 1678 # allows the user to add a LpVariable as an objective 1679 obj = obj + 0.0 1680 try: 1681 obj = obj.constraint 1682 name = obj.name 1683 except AttributeError: 1684 name = None 1685 self.objective = obj 1686 self.objective.name = name 1687 self.resolveOK = False 1688 1689 def __iadd__(self, other): 1690 if isinstance(other, tuple): 1691 other, name = other 1692 else: 1693 name = None 1694 if other is True: 1695 return self 1696 elif other is False: 1697 raise TypeError("A False object cannot be passed as a constraint") 1698 elif isinstance(other, LpConstraintVar): 1699 self.addConstraint(other.constraint) 1700 elif isinstance(other, LpConstraint): 1701 self.addConstraint(other, name) 1702 elif isinstance(other, LpAffineExpression): 1703 if self.objective is not None: 1704 warnings.warn("Overwriting previously set objective.") 1705 self.objective = other 1706 if name is not None: 1707 # we may keep the LpAffineExpression name 1708 self.objective.name = name 1709 elif isinstance(other, LpVariable) or isinstance(other, (int, float)): 1710 if self.objective is not None: 1711 warnings.warn("Overwriting previously set objective.") 1712 self.objective = LpAffineExpression(other) 1713 self.objective.name = name 1714 else: 1715 raise TypeError( 1716 "Can only add LpConstraintVar, LpConstraint, LpAffineExpression or True objects" 1717 ) 1718 return self 1719 1720 def extend(self, other, use_objective=True): 1721 """ 1722 extends an LpProblem by adding constraints either from a dictionary 1723 a tuple or another LpProblem object. 1724 1725 @param use_objective: determines whether the objective is imported from 1726 the other problem 1727 1728 For dictionaries the constraints will be named with the keys 1729 For tuples an unique name will be generated 1730 For LpProblems the name of the problem will be added to the constraints 1731 name 1732 """ 1733 if isinstance(other, dict): 1734 for name in other: 1735 self.constraints[name] = other[name] 1736 elif isinstance(other, LpProblem): 1737 for v in set(other.variables()).difference(self.variables()): 1738 v.name = other.name + v.name 1739 for name, c in other.constraints.items(): 1740 c.name = other.name + name 1741 self.addConstraint(c) 1742 if use_objective: 1743 self.objective += other.objective 1744 else: 1745 for c in other: 1746 if isinstance(c, tuple): 1747 name = c[0] 1748 c = c[1] 1749 else: 1750 name = None 1751 if not name: 1752 name = c.name 1753 if not name: 1754 name = self.unusedConstraintName() 1755 self.constraints[name] = c 1756 1757 def coefficients(self, translation=None): 1758 coefs = [] 1759 if translation == None: 1760 for c in self.constraints: 1761 cst = self.constraints[c] 1762 coefs.extend([(v.name, c, cst[v]) for v in cst]) 1763 else: 1764 for c in self.constraints: 1765 ctr = translation[c] 1766 cst = self.constraints[c] 1767 coefs.extend([(translation[v.name], ctr, cst[v]) for v in cst]) 1768 return coefs 1769 1770 def writeMPS(self, filename, mpsSense=0, rename=0, mip=1): 1771 """ 1772 Writes an mps files from the problem information 1773 1774 :param str filename: name of the file to write 1775 :param int mpsSense: 1776 :param bool rename: if True, normalized names are used for variables and constraints 1777 :param mip: variables and variable renames 1778 :return: 1779 Side Effects: 1780 - The file is created 1781 """ 1782 return mpslp.writeMPS(self, filename, mpsSense=mpsSense, rename=rename, mip=mip) 1783 1784 def writeLP(self, filename, writeSOS=1, mip=1, max_length=100): 1785 """ 1786 Write the given Lp problem to a .lp file. 1787 1788 This function writes the specifications (objective function, 1789 constraints, variables) of the defined Lp problem to a file. 1790 1791 :param str filename: the name of the file to be created. 1792 :return: variables 1793 Side Effects: 1794 - The file is created 1795 """ 1796 return mpslp.writeLP( 1797 self, filename=filename, writeSOS=writeSOS, mip=mip, max_length=max_length 1798 ) 1799 1800 def checkDuplicateVars(self): 1801 """ 1802 Checks if there are at least two variables with the same name 1803 :return: 1 1804 :raises `const.PulpError`: if there ar duplicates 1805 """ 1806 vs = self.variables() 1807 1808 repeated_names = {} 1809 for v in vs: 1810 repeated_names[v.name] = repeated_names.get(v.name, 0) + 1 1811 repeated_names = [ 1812 (key, value) for key, value in list(repeated_names.items()) if value >= 2 1813 ] 1814 if repeated_names: 1815 raise const.PulpError("Repeated variable names:\n" + str(repeated_names)) 1816 return 1 1817 1818 def checkLengthVars(self, max_length): 1819 """ 1820 Checks if variables have names smaller than `max_length` 1821 :param int max_length: max size for variable name 1822 :return: 1823 :raises const.PulpError: if there is at least one variable that has a long name 1824 """ 1825 vs = self.variables() 1826 long_names = [v.name for v in vs if len(v.name) > max_length] 1827 if long_names: 1828 raise const.PulpError( 1829 "Variable names too long for Lp format\n" + str(long_names) 1830 ) 1831 return 1 1832 1833 def assignVarsVals(self, values): 1834 variables = self.variablesDict() 1835 for name in values: 1836 if name != "__dummy": 1837 variables[name].varValue = values[name] 1838 1839 def assignVarsDj(self, values): 1840 variables = self.variablesDict() 1841 for name in values: 1842 if name != "__dummy": 1843 variables[name].dj = values[name] 1844 1845 def assignConsPi(self, values): 1846 for name in values: 1847 try: 1848 self.constraints[name].pi = values[name] 1849 except KeyError: 1850 pass 1851 1852 def assignConsSlack(self, values, activity=False): 1853 for name in values: 1854 try: 1855 if activity: 1856 # reports the activity not the slack 1857 self.constraints[name].slack = -1 * ( 1858 self.constraints[name].constant + float(values[name]) 1859 ) 1860 else: 1861 self.constraints[name].slack = float(values[name]) 1862 except KeyError: 1863 pass 1864 1865 def get_dummyVar(self): 1866 if self.dummyVar is None: 1867 self.dummyVar = LpVariable("__dummy", 0, 0) 1868 return self.dummyVar 1869 1870 def fixObjective(self): 1871 if self.objective is None: 1872 self.objective = 0 1873 wasNone = 1 1874 else: 1875 wasNone = 0 1876 if not isinstance(self.objective, LpAffineExpression): 1877 self.objective = LpAffineExpression(self.objective) 1878 if self.objective.isNumericalConstant(): 1879 dummyVar = self.get_dummyVar() 1880 self.objective += dummyVar 1881 else: 1882 dummyVar = None 1883 return wasNone, dummyVar 1884 1885 def restoreObjective(self, wasNone, dummyVar): 1886 if wasNone: 1887 self.objective = None 1888 elif not dummyVar is None: 1889 self.objective -= dummyVar 1890 1891 def solve(self, solver=None, **kwargs): 1892 """ 1893 Solve the given Lp problem. 1894 1895 This function changes the problem to make it suitable for solving 1896 then calls the solver.actualSolve() method to find the solution 1897 1898 :param solver: Optional: the specific solver to be used, defaults to the 1899 default solver. 1900 1901 Side Effects: 1902 - The attributes of the problem object are changed in 1903 :meth:`~pulp.solver.LpSolver.actualSolve()` to reflect the Lp solution 1904 """ 1905 1906 if not (solver): 1907 solver = self.solver 1908 if not (solver): 1909 solver = LpSolverDefault 1910 wasNone, dummyVar = self.fixObjective() 1911 # time it 1912 self.startClock() 1913 status = solver.actualSolve(self, **kwargs) 1914 self.stopClock() 1915 self.restoreObjective(wasNone, dummyVar) 1916 self.solver = solver 1917 return status 1918 1919 def startClock(self): 1920 "initializes properties with the current time" 1921 self.solutionCpuTime = -clock() 1922 self.solutionTime = -time() 1923 1924 def stopClock(self): 1925 "updates time wall time and cpu time" 1926 self.solutionTime += time() 1927 self.solutionCpuTime += clock() 1928 1929 def sequentialSolve( 1930 self, objectives, absoluteTols=None, relativeTols=None, solver=None, debug=False 1931 ): 1932 """ 1933 Solve the given Lp problem with several objective functions. 1934 1935 This function sequentially changes the objective of the problem 1936 and then adds the objective function as a constraint 1937 1938 :param objectives: the list of objectives to be used to solve the problem 1939 :param absoluteTols: the list of absolute tolerances to be applied to 1940 the constraints should be +ve for a minimise objective 1941 :param relativeTols: the list of relative tolerances applied to the constraints 1942 :param solver: the specific solver to be used, defaults to the default solver. 1943 1944 """ 1945 # TODO Add a penalty variable to make problems elastic 1946 # TODO add the ability to accept different status values i.e. infeasible etc 1947 1948 if not (solver): 1949 solver = self.solver 1950 if not (solver): 1951 solver = LpSolverDefault 1952 if not (absoluteTols): 1953 absoluteTols = [0] * len(objectives) 1954 if not (relativeTols): 1955 relativeTols = [1] * len(objectives) 1956 # time it 1957 self.startClock() 1958 statuses = [] 1959 for i, (obj, absol, rel) in enumerate( 1960 zip(objectives, absoluteTols, relativeTols) 1961 ): 1962 self.setObjective(obj) 1963 status = solver.actualSolve(self) 1964 statuses.append(status) 1965 if debug: 1966 self.writeLP("%sSequence.lp" % i) 1967 if self.sense == const.LpMinimize: 1968 self += obj <= value(obj) * rel + absol, "%s_Sequence_Objective" % i 1969 elif self.sense == const.LpMaximize: 1970 self += obj >= value(obj) * rel + absol, "%s_Sequence_Objective" % i 1971 self.stopClock() 1972 self.solver = solver 1973 return statuses 1974 1975 def resolve(self, solver=None, **kwargs): 1976 """ 1977 resolves an Problem using the same solver as previously 1978 """ 1979 if not (solver): 1980 solver = self.solver 1981 if self.resolveOK: 1982 return self.solver.actualResolve(self, **kwargs) 1983 else: 1984 return self.solve(solver=solver, **kwargs) 1985 1986 def setSolver(self, solver=LpSolverDefault): 1987 """Sets the Solver for this problem useful if you are using 1988 resolve 1989 """ 1990 self.solver = solver 1991 1992 def numVariables(self): 1993 """ 1994 1995 :return: number of variables in model 1996 """ 1997 return len(self._variable_ids) 1998 1999 def numConstraints(self): 2000 """ 2001 2002 :return: number of constraints in model 2003 """ 2004 return len(self.constraints) 2005 2006 def getSense(self): 2007 return self.sense 2008 2009 def assignStatus(self, status, sol_status=None): 2010 """ 2011 Sets the status of the model after solving. 2012 :param status: code for the status of the model 2013 :param sol_status: code for the status of the solution 2014 :return: 2015 """ 2016 if status not in const.LpStatus: 2017 raise const.PulpError("Invalid status code: " + str(status)) 2018 2019 if sol_status is not None and sol_status not in const.LpSolution: 2020 raise const.PulpError("Invalid solution status code: " + str(sol_status)) 2021 2022 self.status = status 2023 if sol_status is None: 2024 sol_status = const.LpStatusToSolution.get( 2025 status, const.LpSolutionNoSolutionFound 2026 ) 2027 self.sol_status = sol_status 2028 return True 2029 2030 2031class FixedElasticSubProblem(LpProblem): 2032 """ 2033 Contains the subproblem generated by converting a fixed constraint 2034 :math:`\\sum_{i}a_i x_i = b` into an elastic constraint. 2035 2036 :param constraint: The LpConstraint that the elastic constraint is based on 2037 :param penalty: penalty applied for violation (+ve or -ve) of the constraints 2038 :param proportionFreeBound: 2039 the proportional bound (+ve and -ve) on 2040 constraint violation that is free from penalty 2041 :param proportionFreeBoundList: the proportional bound on \ 2042 constraint violation that is free from penalty, expressed as a list\ 2043 where [-ve, +ve] 2044 """ 2045 2046 def __init__( 2047 self, 2048 constraint, 2049 penalty=None, 2050 proportionFreeBound=None, 2051 proportionFreeBoundList=None, 2052 ): 2053 subProblemName = "%s_elastic_SubProblem" % constraint.name 2054 LpProblem.__init__(self, subProblemName, const.LpMinimize) 2055 self.objective = LpAffineExpression() 2056 self.constraint = constraint 2057 self.constant = constraint.constant 2058 self.RHS = -constraint.constant 2059 self.objective = LpAffineExpression() 2060 self += constraint, "_Constraint" 2061 # create and add these variables but disabled 2062 self.freeVar = LpVariable("_free_bound", upBound=0, lowBound=0) 2063 self.upVar = LpVariable("_pos_penalty_var", upBound=0, lowBound=0) 2064 self.lowVar = LpVariable("_neg_penalty_var", upBound=0, lowBound=0) 2065 constraint.addInPlace(self.freeVar + self.lowVar + self.upVar) 2066 if proportionFreeBound: 2067 proportionFreeBoundList = [proportionFreeBound, proportionFreeBound] 2068 if proportionFreeBoundList: 2069 # add a costless variable 2070 self.freeVar.upBound = abs(constraint.constant * proportionFreeBoundList[0]) 2071 self.freeVar.lowBound = -abs( 2072 constraint.constant * proportionFreeBoundList[1] 2073 ) 2074 # Note the reversal of the upbound and lowbound due to the nature of the 2075 # variable 2076 if penalty is not None: 2077 # activate these variables 2078 self.upVar.upBound = None 2079 self.lowVar.lowBound = None 2080 self.objective = penalty * self.upVar - penalty * self.lowVar 2081 2082 def _findValue(self, attrib): 2083 """ 2084 safe way to get the value of a variable that may not exist 2085 """ 2086 var = getattr(self, attrib, 0) 2087 if var: 2088 if value(var) is not None: 2089 return value(var) 2090 else: 2091 return 0.0 2092 else: 2093 return 0.0 2094 2095 def isViolated(self): 2096 """ 2097 returns true if the penalty variables are non-zero 2098 """ 2099 upVar = self._findValue("upVar") 2100 lowVar = self._findValue("lowVar") 2101 freeVar = self._findValue("freeVar") 2102 result = abs(upVar + lowVar) >= const.EPS 2103 if result: 2104 log.debug( 2105 "isViolated %s, upVar %s, lowVar %s, freeVar %s result %s" 2106 % (self.name, upVar, lowVar, freeVar, result) 2107 ) 2108 log.debug( 2109 "isViolated value lhs %s constant %s" % (self.findLHSValue(), self.RHS) 2110 ) 2111 return result 2112 2113 def findDifferenceFromRHS(self): 2114 """ 2115 The amount the actual value varies from the RHS (sense: LHS - RHS) 2116 """ 2117 return self.findLHSValue() - self.RHS 2118 2119 def findLHSValue(self): 2120 """ 2121 for elastic constraints finds the LHS value of the constraint without 2122 the free variable and or penalty variable assumes the constant is on the 2123 rhs 2124 """ 2125 upVar = self._findValue("upVar") 2126 lowVar = self._findValue("lowVar") 2127 freeVar = self._findValue("freeVar") 2128 return self.constraint.value() - self.constant - upVar - lowVar - freeVar 2129 2130 def deElasticize(self): 2131 """de-elasticize constraint""" 2132 self.upVar.upBound = 0 2133 self.lowVar.lowBound = 0 2134 2135 def reElasticize(self): 2136 """ 2137 Make the Subproblem elastic again after deElasticize 2138 """ 2139 self.upVar.lowBound = 0 2140 self.upVar.upBound = None 2141 self.lowVar.upBound = 0 2142 self.lowVar.lowBound = None 2143 2144 def alterName(self, name): 2145 """ 2146 Alters the name of anonymous parts of the problem 2147 2148 """ 2149 self.name = "%s_elastic_SubProblem" % name 2150 if hasattr(self, "freeVar"): 2151 self.freeVar.name = self.name + "_free_bound" 2152 if hasattr(self, "upVar"): 2153 self.upVar.name = self.name + "_pos_penalty_var" 2154 if hasattr(self, "lowVar"): 2155 self.lowVar.name = self.name + "_neg_penalty_var" 2156 2157 2158class FractionElasticSubProblem(FixedElasticSubProblem): 2159 """ 2160 Contains the subproblem generated by converting a Fraction constraint 2161 numerator/(numerator+complement) = b 2162 into an elastic constraint 2163 2164 :param name: The name of the elastic subproblem 2165 :param penalty: penalty applied for violation (+ve or -ve) of the constraints 2166 :param proportionFreeBound: the proportional bound (+ve and -ve) on 2167 constraint violation that is free from penalty 2168 :param proportionFreeBoundList: the proportional bound on 2169 constraint violation that is free from penalty, expressed as a list 2170 where [-ve, +ve] 2171 """ 2172 2173 def __init__( 2174 self, 2175 name, 2176 numerator, 2177 RHS, 2178 sense, 2179 complement=None, 2180 denominator=None, 2181 penalty=None, 2182 proportionFreeBound=None, 2183 proportionFreeBoundList=None, 2184 ): 2185 subProblemName = "%s_elastic_SubProblem" % name 2186 self.numerator = numerator 2187 if denominator is None and complement is not None: 2188 self.complement = complement 2189 self.denominator = numerator + complement 2190 elif denominator is not None and complement is None: 2191 self.denominator = denominator 2192 self.complement = denominator - numerator 2193 else: 2194 raise const.PulpError( 2195 "only one of denominator and complement must be specified" 2196 ) 2197 self.RHS = RHS 2198 self.lowTarget = self.upTarget = None 2199 LpProblem.__init__(self, subProblemName, const.LpMinimize) 2200 self.freeVar = LpVariable("_free_bound", upBound=0, lowBound=0) 2201 self.upVar = LpVariable("_pos_penalty_var", upBound=0, lowBound=0) 2202 self.lowVar = LpVariable("_neg_penalty_var", upBound=0, lowBound=0) 2203 if proportionFreeBound: 2204 proportionFreeBoundList = [proportionFreeBound, proportionFreeBound] 2205 if proportionFreeBoundList: 2206 upProportionFreeBound, lowProportionFreeBound = proportionFreeBoundList 2207 else: 2208 upProportionFreeBound, lowProportionFreeBound = (0, 0) 2209 # create an objective 2210 self += LpAffineExpression() 2211 # There are three cases if the constraint.sense is ==, <=, >= 2212 if sense in [const.LpConstraintEQ, const.LpConstraintLE]: 2213 # create a constraint the sets the upper bound of target 2214 self.upTarget = RHS + upProportionFreeBound 2215 self.upConstraint = LpFractionConstraint( 2216 self.numerator, 2217 self.complement, 2218 const.LpConstraintLE, 2219 self.upTarget, 2220 denominator=self.denominator, 2221 ) 2222 if penalty is not None: 2223 self.lowVar.lowBound = None 2224 self.objective += -1 * penalty * self.lowVar 2225 self.upConstraint += self.lowVar 2226 self += self.upConstraint, "_upper_constraint" 2227 if sense in [const.LpConstraintEQ, const.LpConstraintGE]: 2228 # create a constraint the sets the lower bound of target 2229 self.lowTarget = RHS - lowProportionFreeBound 2230 self.lowConstraint = LpFractionConstraint( 2231 self.numerator, 2232 self.complement, 2233 const.LpConstraintGE, 2234 self.lowTarget, 2235 denominator=self.denominator, 2236 ) 2237 if penalty is not None: 2238 self.upVar.upBound = None 2239 self.objective += penalty * self.upVar 2240 self.lowConstraint += self.upVar 2241 self += self.lowConstraint, "_lower_constraint" 2242 2243 def findLHSValue(self): 2244 """ 2245 for elastic constraints finds the LHS value of the constraint without 2246 the free variable and or penalty variable assumes the constant is on the 2247 rhs 2248 """ 2249 # uses code from LpFractionConstraint 2250 if abs(value(self.denominator)) >= const.EPS: 2251 return value(self.numerator) / value(self.denominator) 2252 else: 2253 if abs(value(self.numerator)) <= const.EPS: 2254 # zero divided by zero will return 1 2255 return 1.0 2256 else: 2257 raise ZeroDivisionError 2258 2259 def isViolated(self): 2260 """ 2261 returns true if the penalty variables are non-zero 2262 """ 2263 if abs(value(self.denominator)) >= const.EPS: 2264 if self.lowTarget is not None: 2265 if self.lowTarget > self.findLHSValue(): 2266 return True 2267 if self.upTarget is not None: 2268 if self.findLHSValue() > self.upTarget: 2269 return True 2270 else: 2271 # if the denominator is zero the constraint is satisfied 2272 return False 2273 2274 2275def lpSum(vector): 2276 """ 2277 Calculate the sum of a list of linear expressions 2278 2279 :param vector: A list of linear expressions 2280 """ 2281 return LpAffineExpression().addInPlace(vector) 2282 2283 2284def lpDot(v1, v2): 2285 """Calculate the dot product of two lists of linear expressions""" 2286 if not const.isiterable(v1) and not const.isiterable(v2): 2287 return v1 * v2 2288 elif not const.isiterable(v1): 2289 return lpDot([v1] * len(v2), v2) 2290 elif not const.isiterable(v2): 2291 return lpDot(v1, [v2] * len(v1)) 2292 else: 2293 return lpSum([lpDot(e1, e2) for e1, e2 in zip(v1, v2)]) 2294