Initial import

8 files changed, 367 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..19f46f5
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,6 @@
+*.py[co]
+*.sw?
+*.egg-info/
+gurobi.log
+gurobi.lic
+sandbox/
diff --git a/README.rst b/README.rst
new file mode 100644
index 0000000..cd1afdd
--- /dev/null
+++ b/README.rst
@@ -0,0 +1,25 @@
+Generic worker/slot scheduling using ILP
+========================================
+
+Assigns workers to slots with the following constraints:
+
+1. Number of slots and workers per slots
+2. Slots per worker
+3. Workers preferences (using priorities)
+
+Optimization is using these targets:
+
+a. Evenly distributed workers across slots
+b. Respect worker’s priorities
+
+Dependencies
+------------
+
+ilpscheduling depends on python and gurobi_.
+
+Using a custom licence path for gurobi is possible using::
+
+	export GRB_LICENSE_FILE=`pwd`/gurobi.lic
+
+.. _gurobi: http://www.gurobi.com/
+
diff --git a/ilpscheduling/__init__.py b/ilpscheduling/__init__.py
new file mode 100644
index 0000000..bd6693f
--- /dev/null
+++ b/ilpscheduling/__init__.py
@@ -0,0 +1,27 @@
+# vim: set fileencoding=utf-8 :
+
+"""
+Simple, ILP-based worker-slot-scheduling that optimizes for similar group sizes
+and worker’s priorities.
+
+Depends on gurobipy.
+"""
+
+import argparse
+import scheduler
+import generate
+from .convert import *
+
+def main ():
+    parser = argparse.ArgumentParser(description='ILP worker scheduling.')
+    subparsers = parser.add_subparsers ()
+
+    scheduler.addParser (subparsers)
+    importekvvParser = subparsers.add_parser ('importekvv', help='Import XML files from ekvv')
+    importekvvParser.add_argument('files', nargs='+', help='input file')
+    importekvvParser.set_defaults (func=mainImportEkvv)
+    generate.addParser (subparsers)
+
+    args = parser.parse_args()
+    args.func (args)
+
diff --git a/ilpscheduling/convert.py b/ilpscheduling/convert.py
new file mode 100644
index 0000000..f95dabf
--- /dev/null
+++ b/ilpscheduling/convert.py
@@ -0,0 +1,32 @@
+# vim: set fileencoding=utf-8 :
+
+import sys, yaml
+from lxml import etree
+from lxml import objectify
+
+def mainImportEkvv (args):
+    """
+    Parse ekvv participant management lists
+    XXX: priorities are not properly imported yet and need to be “normalized”
+
+    See http://ekvv.uni-bielefeld.de/wiki/en/Export_von_Anmeldelisten_für_Platzvergabeverfahren_im_XML_Format
+    """
+
+    worker = {}
+    limit = {}
+
+    for f in args.files:
+        with open (f, 'r') as fd:
+            tree = objectify.parse (fd)
+            root = tree.getroot ()
+            slotid = root.get ('id')
+            workerlist = root.teilnehmerliste
+            limit[slotid] = int (workerlist.get ('teilnehmerbegrenzung'))
+            for t in workerlist.teilnehmer:
+                wid = t.get ('matrikelnummer')
+                worker.setdefault (wid, {})
+                worker[wid][slotid] = int (t.get ('prioritaet'))
+
+    yaml.dump ({'worker': worker, 'slots': limit, 'env': {'minSlots': len (limit), 'maxSlots': len (limit)}}, sys.stdout)
+
+
diff --git a/ilpscheduling/generate.py b/ilpscheduling/generate.py
new file mode 100644
index 0000000..b9d1cef
--- /dev/null
+++ b/ilpscheduling/generate.py
@@ -0,0 +1,34 @@
+# vim: set fileencoding=utf-8 :
+
+import random, yaml, sys
+from model import WorkerSlotModel
+
+def main (args):
+    numSlots = args.slots
+    numWorker = args.worker
+    minDatesPerStudent = 1
+    maxDatesPerStudent = 3
+
+    worker = {}
+    slots = {}
+
+    for i in range (numSlots):
+        slots[i] = {'max': args.slotLimit, 'min': 0}
+
+    prio = list (range (1, numSlots+1))
+    for i in range (numWorker):
+        keys = slots.keys ()
+        random.shuffle (keys)
+        s = random.randint (minDatesPerStudent, maxDatesPerStudent)
+        worker[i] = {'prio': dict (zip (keys[:s], prio[:s])), 'slots': {'min': 1, 'max': 1}}
+
+    data = WorkerSlotModel (slots, worker, {'minSlots': 0, 'maxSlots': len (slots)})
+    data.dump (sys.stdout)
+
+def addParser (subparsers):
+    parser = subparsers.add_parser ('generate', help='Generate random testcase')
+    parser.add_argument('--slots', '-s', type=int, default=5)
+    parser.add_argument('--worker', '-w', type=int, default=60)
+    parser.add_argument('--slot-limit', '-l', dest='slotLimit', type=int, default=12, help='Max number of worker per slot')
+    parser.set_defaults (func=main)
+
diff --git a/ilpscheduling/model.py b/ilpscheduling/model.py
new file mode 100644
index 0000000..baa02d1
--- /dev/null
+++ b/ilpscheduling/model.py
@@ -0,0 +1,56 @@
+# vim: set fileencoding=utf-8 :
+
+import yaml
+
+class WorkerSlotModel:
+    def __init__ (self, slots, worker, env):
+        self._slots = slots
+        self._worker = worker
+        self._env = env
+
+        # generated properties, public, read-only
+        self.slotNames = set (slots.keys ())
+        assert len (self.slotNames) == len (slots.keys ()), "slot names must be unique"
+        self.workerNames = set (worker.keys ())
+        assert len (self.workerNames) == len (worker.keys ()), "worker names must be unique"
+        self.minTotalSlots = self._env.get ('minSlots', 0)
+        self.maxTotalSlots = self._env.get ('maxSlots', len (self.slotNames))
+
+    @classmethod
+    def fromYaml (obj, fd):
+        """
+        Import from YAML file. Structured like this:
+
+        """
+        data = yaml.load (fd)
+        o = obj (data['slots'], data['worker'], data.get ('env', {}))
+        return o
+
+    def available (self, worker, slot):
+        """
+        Is worker available for slot?
+        """
+        return self.priority (worker, slot) is not None
+
+    def priority (self, worker, slot):
+        """
+        Get worker’s preferences/priority for slot, priority is higher for
+        smaller numbers and must be >= 1
+        """
+        return self._worker[worker]['prio'].get (slot, None)
+
+    def maxSlots (self, worker):
+        return self._worker[worker]['slots']['max']
+
+    def minSlots (self, worker):
+        return self._worker[worker]['slots']['min']
+
+    def maxWorker (self, slot):
+        return self._slots[slot]['max']
+
+    def minWorker (self, slot):
+        return self._slots[slot]['min']
+
+    def dump (self, fd):
+        yaml.dump ({'worker': self._worker, 'slots': self._slots, 'env': self._env}, fd)
+
diff --git a/ilpscheduling/scheduler.py b/ilpscheduling/scheduler.py
new file mode 100644
index 0000000..c854be5
--- /dev/null
+++ b/ilpscheduling/scheduler.py
@@ -0,0 +1,157 @@
+# vim: set fileencoding=utf-8 :
+
+from gurobipy import *
+
+class ILPUnsolvable (Exception):
+    pass
+
+class ILPScheduler:
+    def __init__ (self, data):
+        """
+        :param data: WorkerSlotModel
+        """
+        self.data = data
+        self.model = Model("scheduling")
+
+    def optimize (self):
+        """
+        Run optimization pass
+        """
+        data = self.data
+        slotNames = data.slotNames
+        workerNames = data.workerNames
+
+        availability = { (w, s) : data.available (w, s) for w in workerNames for s in slotNames }
+
+        model = self.model
+
+        # x[(w,s)] == 1 if worker w is assigned to slot s
+        x = model.addVars(availability.keys(), ub=availability, vtype=GRB.BINARY, name='x')
+
+        # every worker needs slots
+        slotsPerWorker = model.addVars (workerNames, vtype=GRB.INTEGER, name='slotsPerWorker')
+        model.addConstrs((x.sum(w, '*') == slotsPerWorker[w] for w in workerNames), name='slotsPerWorkerConstr')
+
+        model.addConstrs((slotsPerWorker[w] >= data.minSlots (w) for w in workerNames), name='minSlotsPerWorkerConstr')
+        model.addConstrs((slotsPerWorker[w] <= data.maxSlots (w) for w in workerNames), name='maxSlotsPerWorkerConstr')
+
+        # but the number of worker per slot is limited
+        workerPerSlot = model.addVars (slotNames, vtype=GRB.INTEGER, name='workerPerSlot')
+        model.addConstrs ((x.sum('*', s) == workerPerSlot[s] for s in slotNames), name='workerPerSlotAssign')
+
+        model.addConstrs ((workerPerSlot[s] <= data.maxWorker (s) for s in slotNames), name='maxWorkerPerSlotConstr')
+        model.addConstrs ((workerPerSlot[s] >= data.minWorker (s) for s in slotNames), name='minWorkerPerSlotConstr')
+
+        # also the number of slots is limited
+        slotUsed = model.addVars (slotNames, vtype=GRB.BINARY, name='slotUsed')
+        for s in slotNames:
+            # slotUsed[s] is True iff there is at least one worker per slot
+            model.addGenConstrOr (slotUsed[s], [x[(w, s)] for w in workerNames], name='slotUsedConstr')
+        totalSlotsUsed = model.addVar (vtype=GRB.INTEGER)
+        model.addConstr (totalSlotsUsed == slotUsed.sum ('*'), name='totalSlotsUsedConstr')
+
+        model.addConstr(totalSlotsUsed >= data.minTotalSlots, name='minTotalSlotsUsedConstr')
+        model.addConstr(totalSlotsUsed <= data.maxTotalSlots, name='maxTotalSlotsUsedConstr')
+
+        # optimize for these constraints, more important first
+        # - similar-sized slots: minimize diff of each workerPerSlot and
+        # maxWorkerPerSlot. minimizing maxWorkerPerSlot is not sufficient,
+        # because solution 4/4/1 and 3/4/2 are the same
+        maxWorkerPerSlot = model.addVar (vtype=GRB.INTEGER)
+        # maxWorkerPerSlot=max(workerPerSlot)
+        model.addGenConstrMax (maxWorkerPerSlot, workerPerSlot, name='maxWorkerPerSlotConstr')
+        workerMaxDiff = model.addVars (slotNames, vtype=GRB.INTEGER, name='workerMaxDiff')
+        model.addConstrs ((workerMaxDiff[s] == maxWorkerPerSlot-workerPerSlot[s] for s in slotNames), name='workerMaxDiffConstr')
+        cost1 = model.addVar (vtype=GRB.INTEGER)
+        model.addGenConstrMax (cost1, workerMaxDiff, name='cost1Constr')
+
+        # - prefer solutions that fulfil most people’s wishes (everyone gets what he
+        # wants) by minimizing sum of priority.
+        totalPriority = model.addVar (vtype=GRB.INTEGER)
+        maxTotalPriority = 0
+        terms = []
+        for w in workerNames:
+            for s in slotNames:
+                p = data.priority (w, s)
+                if p is not None:
+                    terms.append (x[w,s]*p)
+                    maxTotalPriority += p
+        model.addConstr (totalPriority == quicksum(terms), 'totalPriority')
+
+        # - try to keep worker pairs together
+#        pairs = [(self.workers[0], self.workers[1])]
+#        terms = []
+#        for a, b in pairs:
+#            for j, s in enumerate (slotNames):
+#                terms.append (
+        # XXX: todo
+
+        # combine everything into a single cost function, because multi-objective
+        # solving sucks
+        totalCost = model.addVar (vtype=GRB.INTEGER)
+        # worker per slot is more important, so multiply with max sum of priority
+        model.addConstr (totalCost == cost1*maxTotalPriority + totalPriority, 'totalCost')
+        model.ModelSense = GRB.MINIMIZE
+        model.setObjective (totalCost)
+
+        model.optimize ()
+        status = model.Status
+        if status in (GRB.Status.INF_OR_UNBD, GRB.Status.INFEASIBLE, GRB.Status.UNBOUNDED):
+            raise ILPUnsolvable ()
+        if status != GRB.Status.OPTIMAL:
+            print ('not optimal')
+
+        print ('total priority is', totalPriority.X)
+        print ('max worker per slot is', maxWorkerPerSlot.X)
+        print ('cost1 is', cost1.X)
+        print ('total cost is', totalCost.X)
+        for s in slotNames:
+            print ('slotUsed', s, slotUsed[s].X)
+        print ('totalSlotsUsed', totalSlotsUsed.X)
+        return x, workerPerSlot
+
+def firstNonNull (l):
+    for i in range (len (l)):
+        if l[i]:
+            return i
+
+def mainOptimize (args):
+    import sys
+    from tabulate import tabulate
+    from model import WorkerSlotModel
+
+    # read data
+    with open (args.file, 'r') as fd:
+        data = WorkerSlotModel.fromYaml (fd)
+
+    sched = ILPScheduler (data)
+    try:
+        x, groupSize = sched.optimize ()
+    except ILPUnsolvable:
+        print ('unsolvable')
+        return
+
+    tbl = []
+    for w in data.workerNames:
+        r = [w]
+        for s in data.slotNames:
+            if groupSize[s].X > 0:
+                if x[w,s].X == 1:
+                    r.append (data.priority (w, s))
+                else:
+                    r.append ('')
+        tbl.append (r)
+    # skip row description, thus [1:]
+    tbl.sort (key=lambda x: firstNonNull (x[1:]))
+    hdr = []
+    for s in data.slotNames:
+        if groupSize[s].X > 0:
+            hdr.append ('{} ({})'.format (s, groupSize[s].X))
+
+    print (tabulate (tbl, headers=hdr))
+
+def addParser (subparsers):
+    parser = subparsers.add_parser ('optimize', help='Optimize schedule')
+    parser.add_argument('file', help='input file')
+    parser.set_defaults (func=mainOptimize)
+
diff --git a/setup.py b/setup.py
new file mode 100644
index 0000000..fbada48
--- /dev/null
+++ b/setup.py
@@ -0,0 +1,30 @@
+# Always prefer setuptools over distutils
+from setuptools import setup, find_packages
+# To use a consistent encoding
+from codecs import open
+from os import path
+
+here = path.abspath(path.dirname(__file__))
+
+# Get the long description from the README file
+with open(path.join(here, 'README.rst'), encoding='utf-8') as f:
+    long_description = f.read()
+
+setup(
+    name='ilpscheduling',
+    version='0.1',
+    description='ILP scheduling using gurobipy',
+    long_description=long_description,
+    #url='https://github.com/pypa/sampleproject',
+    # Author details
+    author='Lars-Dominik Braun',
+    author_email='lars@6xq.net',
+    license='MIT',
+    packages=find_packages(exclude=['contrib', 'docs', 'tests']),
+    #install_requires=['gurobipy'],
+    entry_points={
+        'console_scripts': [
+            'ilpsched=ilpscheduling:main',
+        ],
+    },
+)