Wednesday, December 30, 2009

Modeling OR Problems in SAGE

Sage is an open source project providing a comprehensive environment for mathematical computing. It's a big package with big ambitions "Creating a viable free open source alternative to Magma, Maple, Mathematica and Matlab."  See SIAM Review (Vol 41, No. 4, 2009) for a  recent review.

Sage incorporates Python as a scripting language from which one can generate objects MixedIntegerLinearProgram objects.  Both GLPK and CBC from the COIN-OR project can be installed as optional Sage packages and used as solvers.  Coupled with the native features of Python, this approaches provides an interesting alternative to developing models using AMPL/GMPL.
# Dictionary of task durations indexed by (Job, Machine) tuples
dur = {
    ('Paper 1','Blue')   : 45,
    ('Paper 1','Yellow') : 10,
    ('Paper 2','Blue')   : 20,
    ('Paper 2','Green')  : 10,
    ('Paper 2','Yellow') : 34,
    ('Paper 3','Blue')   : 12,
    ('Paper 3','Green')  : 17,
    ('Paper 3','Yellow') : 28 }

# Task sequencing indicated by pairs of (Job, Machine) tuples
order = [
    (('Paper 1','Blue'),  ('Paper 1','Yellow')),
    (('Paper 2','Green'), ('Paper 2','Blue')),
    (('Paper 2','Blue'),  ('Paper 2','Yellow')),
    (('Paper 3','Yellow'),('Paper 3','Blue')),
    (('Paper 3','Blue'),  ('Paper 3','Green')) ]

# TASKS are a list of (job,machine) tuples found from the keys for dur{}
TASKS = dur.keys()

# JOBS and MACHS are unduplicated lists of jobs and machines 
JOBS = sorted(list(set(zip(*TASKS)[0])))
MACHS = sorted(list(set(zip(*TASKS)[1])))

# Create MILP
JobShop = MixedIntegerLinearProgram(maximization=False)

# The objective is to minimize Makespan
MakeSpan = JobShop.new_variable()

# MakeSpan is an upper bound on all tasks
x = JobShop.new_variable()
[JobShop.add_constraint(x[t] + dur[t] - MakeSpan[0], max = 0) for t in TASKS]

# Tasks must be complete in the specified order 
[JobShop.add_constraint(x[s] + dur[s] - x[t], max=0) for s,t in order]

# Disjunctive constraints to avoid machine conflicts. This uses a
# 'Big M' technique and a binary variable where y[s][t] = 0 implies
# task s must finish before task t can start and y[s][t] = 1 implies
# task t finishes before task s starts.

CONFLICTS = [(s,t) for s in TASKS for t in TASKS if s<t and s[1]==t[1]]

y = JobShop.new_variable(dim=2,vtype=JobShop.__BINARY)

BigM = sum(dur[t] for t in TASKS)

[JobShop.add_constraint(BigM*y[s][t] + x[t] - x[s] - dur[s], min=0)
    for s,t in CONFLICTS]
[JobShop.add_constraint(BigM*(1-y[s][t]) + x[s] - x[t] - dur[t], min=0)
    for s,t in CONFLICTS]

Friday, December 18, 2009

Gambling with Stochastic Dynamic Programming

Stochastic dynamic programming is a technique for multi-period decision making under uncertainty. A classic illustration is the case of a risk neutral gambler entering a game with a stake x and a goal of leaving the game with a stake N > x.  The gambler places a wager from his or her current stake, then either wins an equal amount with probability p or loses the wager with probability q. The game continues until the gambler either reaches the goal or goes bust. The gambler cares only about the expected value and not about the range of possible outcomes and therefore is said to be risk neutral.  The problem is to find a betting strategy maximizing the expected value of the game.

The usual setup for solving this problem involves Bellman's 'principle of optimality'. The optimality criterion establishes a recursive expression for the expected value of the game that is a function of the stake. The 'Bellman equation' can be solved for an optimal strategy by a well-known technique called 'policy iteration'.  Alternatively, the same equation can be solved by linear programming as demonstrated in the GMPL file RNGambling.mod.

A related example is the case of the risk averse gambler.  The risk averse gambler enters the game for a predetermined number of rounds with a goal of maximizing the expected 'utility' of the final outcome.  Utility is a concave function of wealth that more heavily penalizes losses than gains. The GMPL model RAGambling.mod demonstrates that this problem can also be solved with linear programming. This example is a closely related to the well known 'Kelly Criterion' (or here for a popular account).

Thursday, December 17, 2009

Example of Business Planning through Stochastic Programming

The final project/exam for the course concerned a business planning problem that could be formulated as a two stage stochastic program.  I've posted here a variation of that problem as an additional example of GMPL modeling: BusinessPlanning.mod.

Monday, December 7, 2009

Final Exam, Assignments, and Assignment 7

Given the collision of so many end-of-semester activities, let's forego any new assignments for this week. Assignment 7 will be due Wednesday followed by a take-home final that will be due noon on Thursday, December 17th.  We'll take more about the final during Wednesday's class session.

Regarding Assignment 7, please feel free to use the GMPL model for portfolio optimization using the MAD criterion.  You'll need to adapt it to the problem data given in the assignment, and in particular deal with the portfolio constraint in part (b) of the problem.

Friday, December 4, 2009

Portfolio Optimization with a Mean Absolute Deviation Criterion

A question came up after class on whether GLPK could be used for portfolio optimization.  At first glance the answer is no because the classic Markowitz formulation for portfolio optimization with a  mean-variance criterion leads to a quadratic program.  GLPK is a linear programming solver that doesn't generally handle quadratic programs. There are workarounds of limited utility, which is demonstrated in a post below.  But in general, GLPK is not suited to quadratic programming.

However, changing the optimization criterion leads to some interesting and useful tools for portfolio optimization that can be expressed as a linear programs. An example is a criterion based on the mean of the absolute deviation (MAD) of return as a risk measure, an idea attributed to Konno and Yamazaki (1991).  This approach also has some other interesting features, including the direct use of return data either from simulation or historical records. Solutions for the MAD criterion exhibit second order stochastic dominance - a a theoretically important feature for risk measures that is not shared by the Markowitz formulation.

To demonstrate the concept, I've prepared a sample GMPL file PortfolioMAD.mod that computes an optimal portfolio using the MAD criterion.  The calculation shows how to compute random samples from multivariable Normal distribution in GMPL.  This requires an implementation of a Cholesky factorization in GMPL which is given in the code.

Thursday, December 3, 2009

Notes on Assignment 6: Australian Motors Case Study

I've been responding to questions regarding the Australian Motors (AM) case study and wanted to pass on a couple of observations.

First, the purpose of this exercise is to implement the business model outlined in Exhibit 8.  AM leases trucks on 2, 3, 4, and 5 month contracts. It makes money by renting those trucks to customers for short term needs.  AM is like a rental car company that obtains it cars through leasing.  Your task is to implement a business model that AM can use to schedule leases for maximum profit.

Second, the model described in Exhibit 8 assigns no cost to AM for leasing surplus vehicles for its fleet that don't, in turn, get rented out to customers. This unrealistic assumption leads to a trivial solution.  You'll get a more realistic solution if you modify the objective function to include an additional cost of $500 per month for each surplus vehicle in the inventory.

Take some time to look over your solution.  In particular, the marginal values on the inequality constraints provides much insight into this business case.  For example, which months and demand segments would your prioritize for a marketing effort intended to increased profits?  Do you see months and demand segments where increasing demand by one unit would increase profits by more than the monthly contribution of that unit?  Why does that occur?

Notes on Assignment 7: Portfolio Optimization in GMPL/GLPK

I was reminded that not all of you are experienced with Matlab, and was asked whether it would be possible to do the portfolio optimization problem in Assignment 7 using GMPL/GLPK.  The answer is a qualified yes.

The issue is that the Mean-Variance (MV) formulation for portfolio optimization leads to a quadratic programming problem.  GLPK is for linear programs, thus the quadratic objective cannot be directly introduced to GLPK.  For the first part of this assignment, however, you can work around the issue by using the first order necessary conditions that define a solution for the MV portfolio.

Look at page 30 of the notes for Lecture 7 entitled "General Case". There you will find linear equations which constrain solutions to the MV problem.  Two of these are simple equality constraints that can be directly translated into GMPL using portfolio weights as the decision variables.  The remaining n linear equations involves the weights and two additional decision variables for the Lagrange multipliers.  Adding those two decision variables to the model allows you to translate these equations into a system of GMPL constraints.  You won't need an objective function because the linear constraints are sufficient to determine a unique solution for the MV portfolio.

For your convenience, I've put a GMPL data file called PortfolioMVO.dat on the downloads list with the necessary data for Assignment 7.

The trouble you'll face is that the second part of Assignment introduces an additional inequality constraint. This change requires you to go back and establish KKT necessary conditions that include this new constraint.  In the end you will have have a somewhat more complex GMPL model with additional decision variables and some discrete logic.  If you're interested in doing this, let me know and I'd be glad to work you through the mechanics.

Friday, November 20, 2009

Lecture 4: Project Management Notes and files

I've uploaded notes for lecture 4 along with a polished up version of the GMPL model for doing the Critical Path Method (CPM) calculations.  Hopefully the notation is more consistent throughout the notes, and translates directly to the GMPL file.
We're becoming somewhat more sophisticated users of GMPL, so you'll note that the model and data files are now separate.  For the assignment you should be able to create a new data file describing the problem and obtain needed results with few (if any) changes to the model.
Project management is an industry of its own, and you'll find a wide variety of software tools to support project management.  Software ranges from simple charting all the way to tools for planning, scheduling, and controlling mission-critical corporate-scale endeavors.  If you're interested in this topic, you might try to try your hand at GanntProject, which is a cross-platform, GPL licensed tool for small scale desktop project management.  One option is to run it right from the web, so you can try it without having to fiddle with software installations.

Wednesday, November 18, 2009

Lecture 3 Notes, Assignment, and Examples

I've posted the notes for Lecture 3 and the GMPL file for the Network/Transportation example we developed in class.  I polished up the class example with comments, attributions, cleaned up variable names and so forth so that it is a good example of GMPL programming practice. Be sure to understand and master the basic techniques demonstrated in this example.

Assignment 2 is due Friday, and Assignment 3 -- the "Custom Vans, Inc." case study will be due next Tuesday.  Assignments 4 and 5 can wait until after the Thanksgiving holiday. We're moving pretty rapidly, so we're trying to maintain an appropriate balance between workload and staying current with lecture topics.

Finally, I've added some additional GMPL examples for Lecture 2.  These are mainly demonstrations of techniques in GMPL including some rather exotic computations one can do with sets.  You may find these useful if you find yourself trying to do complicated manipulations with sets.

For what it's worth, I'm finding the Greenhouse to be a good room for teaching.  Unless there are objections, let's try to meet there for upcoming class sessions.

Tuesday, November 17, 2009

Using GLPK/GMPL with GUSEK ...

In class I demonstrated a minimalistic, bare-bones installation of GLPK. The tools I used were a text editor (such as notepad on Windows machine, or textedit on a Mac) and the GLPK command glpsol.  These simple (and free) tools can handle a wide variety of optimization problems, but are definitely 'old school'. The good news is that integrated user interfaces are available which you may find more convenient for general development work in GMPL.

For Windows you have several choices, including the recently developed GUSEK.  My first reaction is that GUSEK appears to be a very useful tool for the development of GMPL models as used in this course. It's easy to download and install.  Go to and push the download button. Unzip the download file to any folder.  In that folder open the gusek.exe file and you should be good to go. Type your GMPL model in the first tab, save the file, then run the file using the 'Tools>Go' menu item.  If you select the 'Tools>Generate Output File on Go' option, then the optimization results are shown in a separate tab which can also be saved and printed.

For the Mac  I was able to get GUSEK working under the WINE system that allows one to use Windows software in a Mac OS X or Linux environment.  Here's a two step process that should you get you up and running (i.e., it worked for me):
  1. Download and install WINE.  The easiest way is to get a precompiled version from the web site (The download button is the little text item with the downward pointing arrow labeled 'download').  The file should download and unzip automatically then open a window for installation.  Drag the 'Wine' icon to the application folder (you may need to provide your Mac password). 
  2. Next download GUSEK from  It should download and unzip automatically.  Put the gusek folder somewhere convenient (on your desktop, for example).  Go to that folder and double-click gusek.exe.  It's a little slow the first time as WINE configures itself to run the file. There may also be several windows that open up as WINE goes through the startup - this is part of it's configuration process for the first time you use GUSEK. A little wine glass icon will appear in the upper left status bar of your Mac - that's your interface to the WINE software.
  3. At this point you're in business.  You can either open an existing GMPL model or create one from scratch.  Use the Tools menu to run and display the results of the optimization.
Hopefully these instructions are enough to get both PC and Mac users going with GMPL and GUSEK. Let me know if there are problems.  Feel free to add comments to this post if you have any advice or experiences to share regarding the installation of GUSEK.

Sunday, November 15, 2009

Diet Problems

As we will discuss in Lecture 2, diet problems have a long history in the development and teaching of linear programming. Diet problems are examples of a broad class of 'blending problems' which find an optimal mixture of raw materials subject to linear constraints. For those interested, there have been some recent reviews of the history of diet problems.
  • Susan Garner Garille and Saul J. Gass. "Stigler's Diet Problem Revisited"  Operations Research, Vol. 49, No. 1 (Jan. - Feb. 2001), pp. 1-13.

Regarding Assignment 1 ....

I've received a few questions regarding the first assignment and thought I should share my comments with the class.
  1. The Merton Truck case study illustrates the use of linear programming in support of business decisions. The vernacular may be unfamiliar to those without business experience. In particular, the term 'contribution' refers to difference between selling price and the 'variable cost' necessary to produce an item. It's a measure of how much the production and sale of an additional item contributes to overall profit.  To compute total profit, sum contributions from all products sold then subtract Fixed Costs/Overhead. 
  2. The syllabus asks you to do your calculations with a linear programming tool of your choice.  In class I suggested doing this in both Excel and GMPL, which would provide an excellent introduction to those tools.  I meant that only as a suggestion, and apologize if there was any confusion. What's required is a solution using one tool of your choice.
  3. I encourage you to submit your work electronically via Concourse.  PDF files work well for me, but use formats that make sense to you.  If you submit multiple files, label one of them "README" so that I know where to start. 

Thursday, November 5, 2009

Lecture 1

I've posted the presentation notes and a folder of examples that I will use in the first lecture. The notes are rather long (over 100 pages) in order to include supplemental material on the theory and implementation of linear programming.

To use the examples you'll to download and install Matlab and it's toolboxes from the Notre Dame software download site, and download an appropriate version of GLPK.   Use the links in the navigation  bar to locate these sites.

Wednesday, October 21, 2009

Revised Calendar

The following calendar shows the revised class dates after taking into account the need to reschedule dates for the week of November 9th. Please let me know as soon as possible if this presents conflicts for any class participants.

Saturday, September 19, 2009

Syllabus: ESTM 60203

ESTM 60203: Module on Operations Research

Syllabus for Fall, 2009 

Jeffrey Kantor
182 Fitzpatrick Hall
Dept. of Chemical & Biomolecular Engineering
University of Notre Dame
Notre Dame, IN 46556

Office Hours: Whenever available, but best by Appointment
Voice, Text, or Voicemail: 574-699-3525 
Mobile: 574-532-4233
Email: Kantor [dot] 1 [at] nd [dot] edu

Mission Statement

Provide students with a working knowledge of selected concepts and analytical tools of Operations Research with broad application in process operations. 

Learning Outcomes

This module consists of a nine lecture overview of selected concepts from Operations Research. The course is organized around a general theme of modeling and optimization for process operations, with the main attention on techniques for modeling and solving problems in process operations, managing complex systems of activities, and understanding the role of uncertainty in capital allocation and planning.

Students completing this module will be able to:
  1. Formulate, model in a mathematical programming language, and compute solutions for small to medium scale applications of linear programming in process operations, including binary and integer decision variables.
  2. Formulate and solve network, transportation, and related logistics optimization problems of small to medium scale.
  3. Prepare a critical path analysis for medium scale projects, identify the critical path, find earliest finish times and latest start times.
  4. Analyze job shop and flow shop performance for deterministic conditions under common prioritization schedules, including FIFO, LIFO, EDD, and SDT.
  5. Calculate optimal schedules for job and flow shops under deterministic constraints.
  6. Formulate and solve capital allocation problem using mean/variance analysis of return and risk.
  7. Calculate optimal inventories using two-stage stochastic decision models with recourse.
  8. Prepare decision trees and solve for expected mean value, expected value of perfect information.
  9. Analyze case studies using selected tools from Operations Research.

Texts and Other Materials

Primary Texts:
  1. Operations Management 9/e by Jay Heizer and Barry Render. Published in 2008 by Pearson Education.
  2. Class presentation slides will be available on Concourse.
  3. Case Studies (will be provided):
    • Merton Truck Co., Harvard Business School Case Study 189163-PDF-ENG
    • Australian Motors Ltd., Harvard Business School Case Study OIT23-PDF-ENG
    • Optimization Modeling Exercises, Harvard Business School Case Study UV0432-PDF-ENG
  4. IBM DeveloperWorks Series on Linear Programming (available on-line):

Supplementary Materials (available on-line at no cost):


A key objective of this course is to provide students with the technical skills necessary to formulate and solve classic applications in operations management.  This objective is facilitated if students have individual access to software tools for implementation. Recommended software configurations:

  • Matlab with Optimization Toolbox.  The University maintains a site license for Matlab and a set of toolboxes for both Macintosh and PC platforms. Matlab provides a interactive computational environment for a wide range of applications.
  • GLPK (GNU Linear Programming Kit). The GLPK toolkit provides command-line tools for the solution of linear and mixed integer programming problems. GLPK includes a non-proprietary language MathProg for the specification of MILP programs. Tutorials 
  • Excel with Solver. The Windows version of Microsoft Excel incorporates a 'solver' for small to medium scale linear and mixed integer linear programming problems. Use on a Macintosh requires installation of a separate, stand-alone Solver application available from Frontline Systems.

A grade will be assigned based on in-class participation and performance on assignments, a short project, and a take-home examination. The take-home examination will be assigned on the last class day.


The Operations Research component of the ESTEEM program will be taught in a series of ten 75 minute lectures scheduled between November 6 and December 9, 2009.  In the event of rescheduling, topics will be covered in the order listed below.

Date TopicReading MaterialsAssignment
Nov 6
(Fri., 9-10:15am)
Introduction to Linear Optimization1. Quantitative Module B of Heizer and Render, pp. 705-732.
2. Part 1 of IBM Developer Works series on Linear Programming.
Assignment 1: Download and install Matlab and toolboxes, Excel with Solver, and GLPK. Verify the software is working. Following lecture, prepare an analysis of for the Merton Truck Case Study.  Support your analysis with a computational tool of your choice.
Nov 16
(Mon., 4:30-6pm)
Blending ProblemsPart 2 of IBM DeveloperWorks series on Linear Programming.Assignment 2: Problem B.29 (p. 730) from Heizer & Render.  Use the GMPL mathematical programming language to prepare a solution. (Due Fri., Nov 20th)
Nov 18
(Wed., 4:30-6pm)
Network Flow and TransportationQuantitative Module C, pp. 733-753 from Heizer & Render.
Assignment 3: Case Study "Custom Vans, Inc.", Heizer and Render, pp. 751-752. (Due Tues., Nov. 24th).
Nov 20
(Fri., 9-10:15am)
Project ManagementChapter 3 of Heizer & Render, pp. 55-102. Assignment 4: Case Study "Managing Hard Rock's Rockfest", Heizer and Render Video Case p. 101.
Nov 23
(Mon, 4:30-6pm)
Discrete OptimizationPart 3 of the IBM Developer Series on Linear Programming.Assignment 5: Find a solution to today's New York Times Sudoku puzzle.
Nov 30
(Mon., 4:30-6pm)
Job Shops and Flow Shops Chapter 15, "Short-Term Scheduling," Heizer and Render.Assignment 6: Australian Motors, Ltd. Case Study. Prepare GMPL model of the simplified AM Model. Be prepared to discuss the implementation issues raised in the case study.
Dec 2
(Wed., 4:30-6pm)
Uncertainty, Risk, and DiversificationLecture NotesAssignment 7: Prepare a solution to Problem 1 of the "Optimization Modeling Exercises" Case Study using Matlab.
Dec 7
(Mon., 4:30-6pm)
Inventory ManagementChapter 12, "Inventory Management," of Heizer and Render. pp. 481-523.
Dec 9
(Wed., 4:30-6pm)
Optimization Under Uncertainty

Quantitative Module 4, "Decision Making Tools," Heizer and Render, pp. 685-704.

Dec 17
Take-Home Final Due at Noon, 12/17