Source code for CyLP.py.pivots.MostFrequentPivot

import numpy as np
from operator import itemgetter
from random import shuffle
from math import floor
from PivotPythonBase import PivotPythonBase


[docs]class MostFrequentPivot(PivotPythonBase): ''' Last-In-First-Out pivot rule implementation. **Usage** >>> from CyLP.cy import CyClpSimplex >>> from CyLP.py.pivots import MostFrequentPivot >>> from CyLP.py.pivots.MostFrequentPivot import getMpsExample >>> # Get the path to a sample mps file >>> f = getMpsExample() >>> s = CyClpSimplex() >>> s.readMps(f) # Returns 0 if OK 0 >>> pivot = MostFrequentPivot(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 #self.banList = np.zeros(self.dim, np.int) self.banList = [] self.priorityList = range(self.dim) self.frequencies = np.zeros(self.dim) def pivotColumn(self, updates, spareRow1, spareRow2, spareCol1, spareCol2): 'Finds the variable with the best reduced cost and returns its index' self.updateReducedCosts(updates, spareRow1, spareRow2, spareCol1, spareCol2) s = self.clpModel rc = s.getReducedCosts() dim = s.nRows + s.nCols tol = s.dualTolerance for i in self.priorityList: if s.flagged(i) or s.CLP_getVarStatus(i) == 5: # flagged or fixed continue #TODO: can we just say dualInfeasibility = rc[i] ** 2 if s.CLP_getVarStatus(i) == 2: # upperbound dualInfeasibility = rc[i] # free or superbasic elif s.CLP_getVarStatus(i) == 4 or s.CLP_getVarStatus(i) == 0: dualInfeasibility = abs(rc[i]) else: # lowerbound dualInfeasibility = -rc[i] if dualInfeasibility > tol: self.addFrequency(i) return i return -1 def addFrequency(self, i): ''' Add one to frequency of variable i, resorts the priorityList (always sorted) ''' self.frequencies[i] += 1 self.priorityList.remove(i) for j in xrange(self.dim): if self.frequencies[i] >= self.frequencies[self.priorityList[j]]: self.priorityList.insert(j, i) return self.priorityList.append(i) 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')