Source code for cylp.py.pivots.DantzigPivot
'''
As a part of ``cylp.python.pivots`` it implements Dantzig's
Classical Simplex pivot rule. Although it already exists in CLP,
for testing purposes we implement one in Python.
'''
import sys
import numpy as np
from operator import itemgetter
from random import shuffle
from math import floor
from .PivotPythonBase import PivotPythonBase
[docs]class DantzigPivot(PivotPythonBase):
'''
Dantzig's pivot rule implementation.
**Usage**
>>> from cylp.cy import CyClpSimplex
>>> from cylp.py.pivots import DantzigPivot
>>> from cylp.py.pivots.DantzigPivot import getMpsExample
>>> # Get the path to a sample mps file
>>> f = getMpsExample()
>>> s = CyClpSimplex()
>>> s.readMps(f) # Returns 0 if OK
0
>>> pivot = DantzigPivot(s)
>>> s.setPivotMethod(pivot)
>>> s.primal()
'optimal'
>>> round(s.objectiveValue, 5)
2520.57174
'''
def __init__(self, clpModel):
self.dim = clpModel.nRows + clpModel.nCols
self.clpModel = clpModel
def pivotColumn(self, updates, spareRow1, spareRow2, spareCol1, spareCol2):
'Finds the variable with the best reduced cost and returns its index'
s = self.clpModel
# Update the reduced costs, for both the original and the slack variables
if updates.nElements:
s.updateColumnTranspose(spareRow2, updates)
s.transposeTimes(-1, updates, spareCol2, spareCol1)
s.reducedCosts[s.nVariables:][updates.indices] -= updates.elements[:updates.nElements]
s.reducedCosts[:s.nVariables][spareCol1.indices] -= spareCol1.elements[:spareCol1.nElements]
updates.clear()
spareCol1.clear()
rc = s.reducedCosts
tol = s.dualTolerance
indicesToConsider = np.where(s.varNotFlagged & s.varNotFixed &
s.varNotBasic &
(((rc > tol) & s.varIsAtUpperBound) |
((rc < -tol) & s.varIsAtLowerBound) |
s.varIsFree))[0]
#freeVarInds = np.where(s.varIsFree)
#rc[freeVarInds] *= 10
rc2 = np.abs(rc[indicesToConsider])
checkFree = True
#rc2[np.where((status & 7 == 4) | (status & 7 == 0))] *= 10
if rc2.shape[0] > 0:
if checkFree:
w = np.where(s.varIsFree)[0]
if w.shape[0] > 0:
ind = s.argWeightedMax(rc2, indicesToConsider, 1, w)
else:
ind = np.argmax(rc2)
else:
ind = np.argmax(rc2)
#del rc2
return indicesToConsider[ind]
return -1
def saveWeights(self, model, mode):
self.clpModel = model
def isPivotAcceptable(self):
return True
def getMpsExample():
import os
import inspect
cylpDir = os.environ['CYLP_SOURCE_DIR']
return os.path.join(cylpDir, 'cylp', 'input', 'p0033.mps')
if __name__ == "__main__":
if len(sys.argv) == 1:
import doctest
doctest.testmod()
else:
from cylp.cy import CyClpSimplex
from cylp.py.pivots import DantzigPivot
s = CyClpSimplex()
s.readMps(sys.argv[1])
pivot = DantzigPivot(s)
s.setPivotMethod(pivot)
s.primal()