Skip to content

Instantly share code, notes, and snippets.

@vy vy/dc-min.in
Last active Mar 4, 2016

Embed
What would you like to do?
Integer Program to solve Optimize a Data Center Problem (Hash Code 2015, Qualification Round)
2 5 1 2 5
0 0
3 10
3 10
2 5
1 5
1 1
#!/usr/bin/env python
import logging
import math
import os
import re
import sys
import subprocess
logging_format = "%(asctime)s %(levelname)-8s %(message)s"
logging.basicConfig(format=logging_format, level=logging.INFO, datefmt="%Y-%m-%d %H:%M:%S")
logger = logging.getLogger(__name__)
logger.setLevel(logging.DEBUG)
def main():
args = Args.fromArgv(sys.argv)
logger.debug("reading setup: %s", args.dcFile)
setup = Setup.fromDcFile(args.dcFile)
logger.debug(setup)
solve(args, setup)
def solve(args, setup):
gl = args.g
gr = int(math.ceil(sum(setup.serverCapacities) / float(setup.P)))
gm = (gr + gl) / 2
lastScore = 0
while gm < gr:
logger.info("solving for %d <= g=%d < %d", gl, gm, gr)
problem = Problem(setup, gm)
problemFile = args.problemFile(gm)
logger.debug("writing problem: %s", problemFile)
with Util.ensureOpen(problemFile) as pf:
print >> pf, problem
solver = Solver(args, setup, problem, problemFile)
logger.debug("running solver")
solution = solver.solve()
if not solution:
logger.debug("no solution")
logger.debug("stepping back")
gr = gm
else:
logger.debug("solution score: %d", solution.score)
solutionFile = args.solutionFile(gm)
logger.debug("writing solution: %s", solutionFile)
with Util.ensureOpen(solutionFile) as sf:
print >> sf, solution
if not solution.score or solution.score < lastScore:
logger.debug("stepping back")
gr = gm
else:
logger.debug("stepping forward")
gl = gm + 1
lastScore = solution.score
gm = (gr + gl) / 2
class Args:
def __init__(self, cplexFile, dcFile, outputFilePrefix, g):
self.cplexFile = cplexFile
self.dcFile = dcFile
self.outputFilePrefix = outputFilePrefix
self.g = g
def problemFile(self, g):
return "{}-{}.lp".format(self.outputFilePrefix, g)
def cplexOutputFile(self, g):
return "{}-{}.out".format(self.outputFilePrefix, g)
def solutionFile(self, g):
return "{}-{}.soln".format(self.outputFilePrefix, g)
@staticmethod
def fromArgv(argv):
if len(argv) != 5:
print >> sys.stderr, "invalid arguments"
print >> sys.stderr, "usage:", argv[0], "<CPLEX-FILE> <DC-FILE> <OUTPUT-FILE-PREFIX> <G>"
sys.exit(1)
return Args(argv[1], argv[2], argv[3], int(argv[4]))
class Setup:
def __init__(self, R, S, U, P, M, unavailSlotCoords, serverSizes, serverCapacities):
self.R = R
self.S = S
self.U = U
self.P = P
self.M = M
self.unavailSlotCoords = unavailSlotCoords
self.serverSizes = serverSizes
self.serverCapacities = serverCapacities
(self.availBlocks, self.availBlockCoords) = self.buildAvailBlocks()
def buildAvailBlocks(self):
unavailSlots = {}
for [i, j] in self.unavailSlotCoords:
if i not in unavailSlots: unavailSlots[i] = []
unavailSlots[i].append(j)
availBlocks = {}
availBlockCoords = {}
for i in range(self.R):
if i not in unavailSlots:
availBlocks[i] = [self.S]
availBlockCoords[i] = {0: (0, self.S)}
else:
col = 0
rowAvailBlocks = []
rowAvailBlockCoords = {}
js = sorted(unavailSlots[i])
for (j1, j2) in zip([-1] + js, js + [self.S]):
s = j2 - j1 - 1
if s > 0:
rowAvailBlocks.append(s)
rowAvailBlockCoords[col] = (j1 + 1, j2)
col += 1
availBlocks[i] = rowAvailBlocks
availBlockCoords[i] = rowAvailBlockCoords
return (availBlocks, availBlockCoords)
def __str__(self):
return "R={}, S={}, U={}, P={}, M={}".format(self.R, self.S, self.U, self.P, self.M)
@staticmethod
def fromDcFile(dcFile):
with open(dcFile) as handle:
def readInts(): return map(int, handle.readline().strip().split())
(R, S, U, P, M) = readInts()
unavailSlotCoords = [readInts() for _ in range(U)]
zcs = [readInts() for _ in range(M)]
serverSizes = [item[0] for item in zcs]
serverCapacities = [item[1] for item in zcs]
return Setup(R, S, U, P, M, unavailSlotCoords, serverSizes, serverCapacities)
class Problem:
def __init__(self, setup, g):
self.setup = setup
self.g = g
self.lines = []
self.addComments()
self.addObjective()
self.addConstraints()
self.addVariables()
self.lines.append("end")
self.data = "\n".join(self.lines)
def addComments(self):
self.lines.append("\\ setup: {}".format(self.setup))
self.lines.append("\\ g={}".format(self.g))
def addObjective(self):
self.lines.append("maximize")
self.lines.append(" \\ dummy feasibility objective")
objSumTokens = []
for i in range(self.setup.R):
for j in range(len(self.setup.availBlocks[i])):
for k in range(self.setup.M):
for l in range(self.setup.P):
objSumTokens.append("a_{i}_{j}_{k}_{l}".format(**locals()))
objSum = " + ".join(objSumTokens)
self.lines.append(" {objSum}".format(**locals()))
def addConstraints(self):
self.lines.append("subject to")
self.addServerPresenceConstraints()
self.addBlockSizeConstraints()
self.addPoolCapacityConstraints()
def addServerPresenceConstraints(self):
self.lines.append(" \\ a server can be assigned to at most 1 block and 1 pool")
for k in range(self.setup.M):
sumTokens = []
for i in range(self.setup.R):
for j in range(len(self.setup.availBlocks[i])):
for l in range(self.setup.P):
sumTokens.append("a_{i}_{j}_{k}_{l}".format(**locals()))
suM = " + ".join(sumTokens)
self.lines.append(" {suM} <= 1".format(**locals()))
def addBlockSizeConstraints(self):
self.lines.append(" \\ block sizes cannot be exceeded")
for i in range(self.setup.R):
c_i = self.setup.availBlocks[i]
for j in range(len(c_i)):
c_i_j = c_i[j]
sumTokens = []
for k in range(self.setup.M):
z_k = self.setup.serverSizes[k]
for l in range(self.setup.P):
sumTokens.append("{z_k} a_{i}_{j}_{k}_{l}".format(**locals()))
suM = " + ".join(sumTokens)
self.lines.append(" {suM} <= {c_i_j}".format(**locals()))
def addPoolCapacityConstraints(self):
g = self.g
self.lines.append(" \\ pool capacity constraints")
totCapacitySums = {l: self.poolCapacitySum(l) for l in range(self.setup.P)}
for l in range(self.setup.P):
for i in range(self.setup.R):
c_i = self.setup.availBlocks[i]
rowCapacitySumTokens = []
for k in range(self.setup.M):
c_k = self.setup.serverCapacities[k]
for j in range(len(c_i)):
rowCapacitySumTokens.append("{c_k} a_{i}_{j}_{k}_{l}".format(**locals()))
rowCapacitySum = " - ".join(rowCapacitySumTokens)
totCapacitySum = totCapacitySums[l]
self.lines.append(" {totCapacitySum} - {rowCapacitySum} >= {g}".format(**locals()))
def poolCapacitySum(self, l):
sumTokens = []
for i in range(self.setup.R):
for j in range(len(self.setup.availBlocks[i])):
for k in range(self.setup.M):
c_k = self.setup.serverCapacities[k]
sumTokens.append("{c_k} a_{i}_{j}_{k}_{l}".format(**locals()))
return " + ".join(sumTokens)
def addVariables(self):
self.lines.append("binary")
for i in range(self.setup.R):
for j in range(len(self.setup.availBlocks[i])):
for k in range(self.setup.M):
for l in range(self.setup.P):
self.lines.append("a_{i}_{j}_{k}_{l}".format(**locals()))
def __str__(self):
return self.data
class Placement:
def __init__(self, rowId, slotId, poolId):
self.rowId = rowId
self.slotId = slotId
self.poolId = poolId
def __repr__(self):
return "({}, {}, {})".format(self.rowId, self.slotId, self.poolId)
class Solution:
def __init__(self, setup, a):
self.setup = setup
self.a = a
self.serverPlacements = self.findServerPlacements()
self.score = self.findScore()
self.validate()
def findServerPlacements(self):
poolIds = self.findPoolIds()
placements = {}
for i in range(self.setup.R):
for j in range(len(self.setup.availBlocks[i])):
ks = []
for k in range(self.setup.M):
for l in range(self.setup.P):
if self.a[i][j][k][l]:
ks.append(k)
if ks:
(j1, j2) = self.setup.availBlockCoords[i][j]
for k in ks:
if k not in poolIds:
logger.warn("p[{k}][l] = 0 while a[{i}][{j}][{k}][l] = 1".format(**locals()))
else:
rowId = i
slotId = j1
poolId = poolIds[k]
placement = Placement(rowId, slotId, poolId)
if k in placements:
existingPlacement = placements[k]
raise Exception(
"existing placement found for k={k}, was putting {placement}, found {existingPlacement}"
.format(**locals()))
placements[k] = placement
j1 += self.setup.serverSizes[k]
if j1 > j2:
raise Exception(
"block size exceeded (i, j, k, l) = ({i}, {j}, {k}, {poolId})"
.format(**locals()))
return placements
def findPoolIds(self):
poolIds = {}
for i in range(self.setup.R):
for j in range(len(self.setup.availBlocks[i])):
for k in range(self.setup.M):
for l in range(self.setup.P):
if self.a[i][j][k][l]:
if k not in poolIds: poolIds[k] = l
else:
v = poolIds[k]
raise Exception(
"poolIds[{k}] = {l} conflicts with previous set value: {v}"
.format(**locals()))
return poolIds
def findScore(self):
return min([self.findPoolGuaranteedCapacity(l) for l in range(self.setup.P)])
def findPoolGuaranteedCapacity(self, l):
totCapacity = self.findPoolCapacity(l)
maxRowCapacity = max([self.findPoolRowCapacity(l, i) for i in range(self.setup.R)])
return totCapacity - maxRowCapacity
def findPoolCapacity(self, l):
return sum([self.findPoolRowCapacity(l, i) for i in range(self.setup.R)])
def findPoolRowCapacity(self, l, i):
suM = 0
for k in range(self.setup.M):
c_k = self.setup.serverCapacities[k]
for j in range(len(self.setup.availBlocks[i])):
suM += c_k * self.a[i][j][k][l]
return suM
def validate(self):
self.validateSlotAllocations()
self.validatePoolAllocations()
def validateSlotAllocations(self):
slotAllocations = {}
for (serverId, serverPlacement) in self.serverPlacements.items():
place = (serverPlacement.rowId, serverPlacement.slotId)
if place in slotAllocations:
raise Exception(
"invalid server placement: {}, was already allocated by server {}".format(
serverPlacement, slotAllocations[place]))
else: slotAllocations[place] = serverId
def validatePoolAllocations(self):
poolAllocations = {}
for (serverId, serverPlacement) in self.serverPlacements.items():
if serverId in poolAllocations:
raise Exception(
"invalid server placement: {}, was already allocated by pool".format(
serverPlacement, poolAllocations[serverId]))
else: poolAllocations[serverId] = serverPlacement.poolId
def __str__(self):
lines = []
for k in range(self.setup.M):
if k in self.serverPlacements:
serverPlacement = self.serverPlacements[k]
rowId = serverPlacement.rowId
slotId = serverPlacement.slotId
poolId = serverPlacement.poolId
lines.append('{rowId} {slotId} {poolId}'.format(**locals()))
else: lines.append('x')
return "\n".join(lines)
class Solver():
def __init__(self, args, setup, problem, problemFile):
self.args = args
self.setup = setup
self.problem = problem
self.problemFile = problemFile
def solve(self):
popen = subprocess.Popen(
[self.args.cplexFile],
stdin=subprocess.PIPE,
stderr=subprocess.STDOUT,
stdout=subprocess.PIPE)
inputTokens = [
"read {} lp\n".format(self.problemFile),
"set mip limits solutions 1",
"set mip tolerances integrality 0",
"set mip tolerances mipgap 0",
"mipopt",
"display solution variables *"]
input = "\n".join(inputTokens)
(stdoutdata, _) = popen.communicate(input)
cplexOutputFile = self.args.cplexOutputFile(self.problem.g)
logger.debug("writing cplex output: %s", cplexOutputFile)
with Util.ensureOpen(cplexOutputFile) as cof:
print >> cof, stdoutdata
if "No integer feasible solution exists." in stdoutdata:
return None
returncode = popen.returncode
if returncode:
msg = "unexpected return code: {}".format(returncode)
logger.error(msg)
logger.error(stdoutdata)
raise Exception(msg)
return self.parseStdout(stdoutdata)
def parseStdout(self, stdout):
a = {i: {j: {k: {l: 0
for l in range(self.setup.P)}
for k in range(self.setup.M)}
for j in range(len(self.setup.availBlocks[i]))}
for i in range(self.setup.R)}
for line in re.split('\r?\n', stdout):
strippedLine = line.strip()
match = re.match('^a_(\d+)_(\d+)_(\d+)_(\d+)\s+1.000000$', strippedLine)
if match:
(i, j, k, l) = map(int, match.groups())
if not a[i][j][k][l]: a[i][j][k][l] = 1
else: raise Exception("a[{i}][{j}][{k}][{l}] has already been set".format(**locals()))
return Solution(self.setup, a)
class Util:
@staticmethod
def ensureOpen(pathname, mode="w"):
dirname = os.path.dirname(pathname)
if len(dirname) > 1 and not os.path.exists(dirname):
os.makedirs(dirname)
return open(pathname, mode)
if __name__ == "__main__": main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.