Employee Scheduling
WOW!  There is still some interest in optimization?  I&#x27;m shocked!  The message long was &quot;Operations Research is dead.&quot;<p>Gee, I got started in OR (operations research) at FedEx, covered a lot from some of the best people in grad school, taught it as a prof in B-school, and applied it to US national security and some commercial problems.<p>Good to see the interest in some of the flight operations work for Lufthansa -- I was considering (no great progress) some of those problems at FedEx!<p>One commercial problem was allocating marketing resources for some banks.  I was given the formulation, 0-1 integer linear programming with 600,000 variables and 40,000 constraints.  I derived some non-linear duality theory, used the IBM OSL (Optimization Subroutine Library), and in 500 iterations found a feasible solution with the objective function guaranteed to be within 0.025% of optimality!<p>Another commercial problem was some more marketing optimization.  It was also 0-1 integer linear programming, but surprisingly it was just a problem in least cost network flows.  That is also linear programming, but there the simplex algorithm takes on a special form where a basis is a spanning tree of arcs in the network.  A simplex pivot is to add an arc to the tree, thus, yielding a circuit, and running flow around the circuit in the direction that saves money and removing from the circuit, thus, making a tree again, one of the first arcs where the flow goes to zero.  There is a cute variation of the algorithm due to W. Cunningham (one of my profs) based on his <i>strongly feasible basis</i>, that avoids cycling.<p>A super nice point about the simplex problem on least cost network flows is if all the arc capacities are whole numbers and if start with an integer basic feasible solution, then the simplex algorithm will automatically maintain an integer basic feasible solution and terminate with an integer solution.  It is good to suspect that a lot of integer linear programming problems are actually just such network flow problems or nearly so.<p>Once I used that stuff to say, for NASA, how to assign signals to satellite channels to minimize some signal interference -- it was an example of the <i>bottleneck assignment</i> problem which should be solvable very quickly by some <i>post optimality</i> tweaking with the network simplex algorithm.<p>I enjoyed using the IBM OSL, but IBM withdrew it from marketing in about 2003, maybe in favor of marketing C-PLEX.  But it appears that at about 2004 IBM donated the source of the OSL (with lots of pieces, network flow, stochastic programming, etc.) to Riverware which might distribute the open source.<p>I got started with the OSL when I was in an AI group at IBM&#x27;s Watson lab where the OSL was written.  The Watson lab long had some high expertise in optimization -- Gomory (cutting planes, Gilmore-Gomory column generation, etc.) was head of the lab; there was Phil Wolfe (the Wolfe dual, etc.), Ellis Johnson (group theory and integer programming), etc.<p>So, in particular, if still want to do some OR and optimization, get some quite well written software, and save some money, then might look into getting all the IBM OSL code open source.