tag:blogger.com,1999:blog-82833359872753203542018-03-02T11:18:38.563-05:00ESTM 60203 Introduction to Operations ResearchNotes and materials in support of the ESTM 60203 module on Operations ResearchJeffhttp://www.blogger.com/profile/15416541103643920970noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-8283335987275320354.post-52129369921047134492010-01-21T14:24:00.005-05:002010-01-21T19:42:48.995-05:00Linear Ordering ProblemsLinear Ordering Problems (LOP) are encountered in a wide range of applications, such as ranking sports teams, triangulation of matrices (i.e., finding a reordering of the rows and columns that maximizes the total above or below the diagonal), or ordering lists of individual preferences. Recently I came across an interesting application for the scheduling of printing tasks. The data consisted of a array of entries $x_{ij}$ which give the time saved if task i is completed before task j. The times savings were attributed to setup work done for the first task that would benefit subsequent tasks. The problem was to find an ordering of tasks that maximize the overall time savings.<br /><br />Like many problems in Operations Research, the LOP has a rich history of study and algorithm development. LOP are known to be NP hard, but state of the art algorithms provide for many practical uses. A somewhat older MILP formulation is easily implemented in GMPL/GLPK as shown in the <a href="http://www.nd.edu/~jeff/Teaching/ESTM60203/GMPL_Examples/LinearOrder.mod">Scheduling: Linear Ordering of Tasks</a> example.Jeffhttp://www.blogger.com/profile/15416541103643920970noreply@blogger.com0tag:blogger.com,1999:blog-8283335987275320354.post-6326050921289604622010-01-06T14:42:00.002-05:002010-01-06T19:27:43.973-05:00Setting up a Mac for Computational WorkIt is not difficult to set up your Mac for work in the scientific/technical arena. Here are some thoughts and advice based on my own experience.<br /><br /><b>1. Backup/Collaboration</b><br /><br />First thing is to establish a backup/collaboration strategy. Obviously TimeMachine is the simplest alternative. However, I've been using on-line services for this, in particular <a href="http://www.sugarsync.com/">SugarSync</a> and <a href="http://www.dropbox.com/">Dropbox</a>. I use SugarSync to maintain an on-line mirror of the Documents folder, and Dropbox to facilitate sharing of documents with collaborators. A nice advantage of these services is that they also provide web and mobile access to your files.<br /><br />You likely maintain files on other servers. MacFusion (which requires MacFuse) allows you to access files on other servers as if they were local volumes.<br /><br /><b>2. Technical Documents</b><br /><br />It's hard to beat Latex for the preparation of scientific and technical documents. Moreover, mathematical software packages sometimes require the installation of latex to format output.<br /><br /><a href="http://www.tug.org/mactex/">MacTeX</a> is an excellent free distribution of the core tools needed to prepare a wide range of documents including papers, theses, and presentations (using Beamer). Everything you need is available in one large download and simple installation. The tools include BibDesk for managing bibliographies, TexShop and TexWorks for editing and preparing documents, and the Excalibur spell checker. Use the TeXLiveUtility to maintain the package.<br /><br />Many scientific Mac users recommend <a href="http://mekentosj.com/papers/">Papers</a> to manage bibliographies. Having tried alternatives like Papers, I personally prefer BibDesk. Though not quite as polished, by working directly with bibtex databases BiBDesk interfaces beautifully with LyX.<br /><br /><a href="http://www.lyx.org/">LyX</a> is an almost WYSIWYG front end to Latex that generally masks the underlying markup language. If you want to use Latex without having to work directly with Latex commands, then LyX is for you.<br /><br />The MacOS, of course, comes with an indispensable pdf and graphics previewer in Preview. <a href="http://skim-app.sourceforge.net/">Skim</a> is a freeware pdf viewer and notetaker that provides an additional capability to annotate pdf documents and enhanced presentation features.<br /><br /><b>3. General Software Utilities</b><br /><br />Apple provides tools for software development in a separate package called Xcode that includes text editors, compilers, and other components. Many of the software tools you download from the internet require the tools contained in Xcode. The most recent release of <a href="http://developer.apple.com/technology/xcode.html">Xcode</a> can be obtained at no cost by joining the Apple Developer's Connection.<br /><br />There are many 'programmer's text editors' available for the Mac, including TextEdit that comes with MacOS. <a href="http://macromates.com/">TextMate</a> is low-cost (with free trial) with bundles that adapt the editor for use in wide variety of applications.<br /><br /><a href="http://www.macports.org/">MacPorts</a> is a tool for finding and installing open-source software packages. MacPorts simplifies the installation of those packages which have been adapted to the Mac. MacPorts is a simple command line tool, <a href="http://porticus.alittledrop.com/">Porticus</a> provides a GUI interface to MacPorts.<br /><br />Unfortunately, you'll occasionally come across software packages that simply are not available for the Mac. One way to deal with this is to install Windows or Linux under one of the available virtual environments for the Mac such as Apple's Bootcamp, or Parallels, VMware Fusion, or VirtualBox. If you go that route you'll need to acquire and maintain a copy of a second operating system. In many cases, however, the <a href="http://winebottler.kronenberg.org/">WINE</a> package will provide enough support to run Windows software within the Mac environment.<br /><br /><b>4. Mathematical Software</b><br /><br />Finally this brings us to the tools for actually doing computational science on a Mac. Matlab and Mathematica are examples of commercial packages for doing mathematics on a Mac. There is an enormous variety of tools.<br /><br />Here are some of the tools I find useful:<br /><ul><li>General mathematical computation</li> <ul><li>Matlab. Licensed for download to University affiliated students and faculty.</li><li><a href="http://www.gnu.org/software/octave/">Octave</a>. A GPL licensed package with syntax similar to Matlab. Provided you have MacPorts installed, you can install Octave with the command line: <span style="font-family: 'Courier New', Courier, monospace;">sudo port install octave</span></li><li><span style="font-family: inherit;"><a href="http://www.sagemath.org/">Sage</a>. This is a big package based on Python that provides an enormous range of computational and visualization tools.</span></li></ul><li>Statistical Computation.</li> <ul><li>Matlab statistics and econometrics toolboxes</li><li>R</li><li>Quantlib</li></ul><li>Optimization</li> <ul><li>Gusek/GLPK (runs under WINE)</li><li>lpsolveIDE (runs under WINE)</li><li>Sage provides access to GLPK, the COIN-OR CBC package, and CVXOPT.</li><li>CVX, a Matlab class for convex optimization</li><li>YALMIP, a Matlab class for optimization with a variety of solvers</li></ul><li>Python Development</li> <ul><li>Enthought Python distribution (using TextMate)</li><li>Sage</li></ul></ul>Jeffhttp://www.blogger.com/profile/15416541103643920970noreply@blogger.com0tag:blogger.com,1999:blog-8283335987275320354.post-46803726272488818672009-12-30T12:42:00.011-05:002009-12-30T14:01:12.781-05:00Modeling OR Problems in SAGE<a href="http://www.sagemath.org/">Sage</a> 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 <a href="http://siamdl.aip.org/dbt/dbt.jsp?KEY=SIREAD&Volume=51&Issue=4">SIAM Review (Vol 41, No. 4, 2009)</a> for a <a href="http://buzzard.ups.edu/bookreview/sage-beezer-review.pdf">recent review</a>.<br /><br />Sage incorporates Python as a scripting language from which one can generate objects <span style="font-family: 'Courier New', Courier, monospace;">MixedIntegerLinearProgram</span> 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.<br /><pre># Dictionary of task durations indexed by (Job, Machine) tuples<br />dur = {<br /> ('Paper 1','Blue') : 45,<br /> ('Paper 1','Yellow') : 10,<br /> ('Paper 2','Blue') : 20,<br /> ('Paper 2','Green') : 10,<br /> ('Paper 2','Yellow') : 34,<br /> ('Paper 3','Blue') : 12,<br /> ('Paper 3','Green') : 17,<br /> ('Paper 3','Yellow') : 28 }<br /><br /># Task sequencing indicated by pairs of (Job, Machine) tuples<br />order = [<br /> (('Paper 1','Blue'), ('Paper 1','Yellow')),<br /> (('Paper 2','Green'), ('Paper 2','Blue')),<br /> (('Paper 2','Blue'), ('Paper 2','Yellow')),<br /> (('Paper 3','Yellow'),('Paper 3','Blue')),<br /> (('Paper 3','Blue'), ('Paper 3','Green')) ]<br /><br /># TASKS are a list of (job,machine) tuples found from the keys for dur{}<br />TASKS = dur.keys()<br /><br /># JOBS and MACHS are unduplicated lists of jobs and machines <br />JOBS = sorted(list(set(zip(*TASKS)[0])))<br />MACHS = sorted(list(set(zip(*TASKS)[1])))<br /><br /># Create MILP<br />JobShop = MixedIntegerLinearProgram(maximization=False)<br /><br /># The objective is to minimize Makespan<br />MakeSpan = JobShop.new_variable()<br />JobShop.set_objective(MakeSpan[0])<br /><br /># MakeSpan is an upper bound on all tasks<br />x = JobShop.new_variable()<br />[JobShop.add_constraint(x[t] + dur[t] - MakeSpan[0], max = 0) for t in TASKS]<br /><br /># Tasks must be complete in the specified order <br />[JobShop.add_constraint(x[s] + dur[s] - x[t], max=0) for s,t in order]<br /><br /># Disjunctive constraints to avoid machine conflicts. This uses a<br /># 'Big M' technique and a binary variable where y[s][t] = 0 implies<br /># task s must finish before task t can start and y[s][t] = 1 implies<br /># task t finishes before task s starts.<br /><br />CONFLICTS = [(s,t) for s in TASKS for t in TASKS if s<t and s[1]==t[1]]<br /><br />y = JobShop.new_variable(dim=2,vtype=JobShop.__BINARY)<br /><br />BigM = sum(dur[t] for t in TASKS)<br /><br />[JobShop.add_constraint(BigM*y[s][t] + x[t] - x[s] - dur[s], min=0)<br /> for s,t in CONFLICTS]<br />[JobShop.add_constraint(BigM*(1-y[s][t]) + x[s] - x[t] - dur[t], min=0)<br /> for s,t in CONFLICTS]<br />JobShop.solve('Coin')<br /><br /></pre>Jeffhttp://www.blogger.com/profile/15416541103643920970noreply@blogger.com0tag:blogger.com,1999:blog-8283335987275320354.post-91010408714245459392009-12-18T13:30:00.004-05:002009-12-19T00:01:31.431-05:00Gambling with Stochastic Dynamic ProgrammingStochastic 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.<br /><br />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 <a href="http://www.nd.edu/~jeff/Teaching/ESTM60203/GMPL_Examples/RNGambling.mod">RNGambling.mod</a>.<br /><br />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 <a href="http://www.nd.edu/~jeff/Teaching/ESTM60203/GMPL_Examples/RAGambling.mod">RAGambling.mod</a> demonstrates that this problem can also be solved with linear programming. This example is a closely related to the well known '<a href="http://en.wikipedia.org/wiki/Kelly_criterion">Kelly Criterion</a>' (or <a href="http://www.amazon.com/Fortunes-Formula-Scientific-Betting-Casinos/dp/0809046377">here</a> for a popular account).Jeffhttp://www.blogger.com/profile/15416541103643920970noreply@blogger.com1tag:blogger.com,1999:blog-8283335987275320354.post-72893809896844632252009-12-17T15:46:00.001-05:002009-12-17T15:53:49.372-05:00Example of Business Planning through Stochastic ProgrammingThe 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: <a href="http://www.nd.edu/~jeff/Teaching/ESTM60203/GMPL_Examples/BusinessPlanning.mod">BusinessPlanning.mod</a>.Jeffhttp://www.blogger.com/profile/15416541103643920970noreply@blogger.com0tag:blogger.com,1999:blog-8283335987275320354.post-67834502640037426092009-12-07T23:54:00.001-05:002009-12-08T00:11:58.981-05:00Final Exam, Assignments, and Assignment 7Given 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.<br /><br />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.Jeffhttp://www.blogger.com/profile/15416541103643920970noreply@blogger.com0tag:blogger.com,1999:blog-8283335987275320354.post-83338982319938885342009-12-04T16:33:00.008-05:002009-12-17T15:59:24.376-05:00Portfolio Optimization with a Mean Absolute Deviation CriterionA 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.<br /><div><br /></div><div>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 <a href="http://www.jstor.org/stable/2632458">Konno and Yamazaki (1991)</a>. 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.<br /></div><div><br /></div><div>To demonstrate the concept, I've prepared a sample GMPL file <span style="font-family: 'Courier New', Courier, monospace;"><a href="http://www.blogger.com/goog_1259962859554">Po</a></span><span style="font-family: 'Courier New', Courier, monospace;"><a href="http://www.nd.edu/~jeff/Teaching/ESTM60203/GMPL_Examples/PortfolioMAD.mod">rtfolioMAD.mod</a></span> 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.<br /></div>Jeffhttp://www.blogger.com/profile/15416541103643920970noreply@blogger.com0tag:blogger.com,1999:blog-8283335987275320354.post-25838130323563377402009-12-03T22:07:00.015-05:002009-12-05T11:38:38.133-05:00Notes on Assignment 6: Australian Motors Case StudyI've been responding to questions regarding the Australian Motors (AM) case study and wanted to pass on a couple of observations.<br /><br />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.<br /><br /><div>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.<br /></div><div><br />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?<br /></div>Jeffhttp://www.blogger.com/profile/15416541103643920970noreply@blogger.com3tag:blogger.com,1999:blog-8283335987275320354.post-40524916739910237472009-12-03T10:38:00.004-05:002009-12-03T22:21:45.920-05:00Notes on Assignment 7: Portfolio Optimization in GMPL/GLPKI 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.<br /><br />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.<br /><br />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 <i>n</i> 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.<br /><br />For your convenience, I've put a GMPL data file called <span style="font-family: 'Courier New', Courier, monospace;">PortfolioMVO.dat</span> on the downloads list with the necessary data for Assignment 7.<br /><br />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.Jeffhttp://www.blogger.com/profile/15416541103643920970noreply@blogger.com0tag:blogger.com,1999:blog-8283335987275320354.post-27915184400220987312009-11-20T22:24:00.006-05:002009-12-08T19:13:53.293-05:00Lecture 4: Project Management Notes and files<div class="separator" style="clear: both; text-align: center;"><br /></div><div class="separator" style="clear: both; text-align: center;"><br /><a href="http://www.nd.edu/~jeff/Teaching/ESTM60203/Images/20091119_0591-3.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="283" src="http://www.nd.edu/~jeff/Teaching/ESTM60203/Images/20091119_0591-3.jpg" width="640" /></a><br /></div><div class="separator" style="clear: both; text-align: left;"><br /></div><div class="separator" style="clear: both; text-align: left;">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.<br /></div><div class="separator" style="clear: both; text-align: left;">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.<br /></div><div class="separator" style="clear: both; text-align: left;">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 <a href="http://www.ganttproject.biz/">GanntProject</a>, 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. <br /></div>Jeffhttp://www.blogger.com/profile/15416541103643920970noreply@blogger.com1tag:blogger.com,1999:blog-8283335987275320354.post-61864346637360095622009-11-18T21:27:00.001-05:002009-11-18T22:03:08.339-05:00Lecture 3 Notes, Assignment, and ExamplesI'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.<br /><br />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.<br /><br />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.<br /><br />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.Jeffhttp://www.blogger.com/profile/15416541103643920970noreply@blogger.com0tag:blogger.com,1999:blog-8283335987275320354.post-90396527951253603792009-11-17T12:34:00.007-05:002009-11-18T21:38:02.443-05:00Using 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 <span style="font-family: 'Courier New', Courier, monospace;">glpsol</span>. 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.<br /><br />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 <a href="http://sourceforge.net/projects/gusek/">http://sourceforge.net/projects/gusek/</a> and push the download button. Unzip the download file to any folder. In that folder open the <span style="font-family: 'Courier New', Courier, monospace;">gusek.exe</span> 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. <br /><br />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):<br /><ol><li>Download and install WINE. The easiest way is to get a precompiled version from the web site <a href="http://winebottler.kronenberg.org/">http://winebottler.kronenberg.org/ </a>(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). </li><li>Next download GUSEK from <a href="http://sourceforge.net/projects/gusek/">http://sourceforge.net/projects/gusek/</a>. It should download and unzip automatically. Put the gusek folder somewhere convenient (on your desktop, for example). Go to that folder and double-click <span style="font-family: 'Courier New', Courier, monospace;">gusek.exe</span>. 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.</li><li>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.</li></ol><div>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.<br /></div>Jeffhttp://www.blogger.com/profile/15416541103643920970noreply@blogger.com1tag:blogger.com,1999:blog-8283335987275320354.post-87793203768844251922009-11-15T18:28:00.002-05:002009-11-15T18:28:45.164-05:00Diet ProblemsAs 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.<br /><ul><li>Susan Garner Garille and Saul J. Gass. "Stigler's Diet Problem Revisited" Operations Research, Vol. 49, No. 1 (Jan. - Feb. 2001), pp. 1-13. <a href="http://www.jstor.org/stable/222950">http://www.jstor.org/stable/222950</a></li></ul>Jeffhttp://www.blogger.com/profile/15416541103643920970noreply@blogger.com0tag:blogger.com,1999:blog-8283335987275320354.post-59157536257664349452009-11-15T10:27:00.003-05:002009-11-15T10:43:33.782-05:00Regarding Assignment 1 ....I've received a few questions regarding the first assignment and thought I should share my comments with the class.<br /><ol><li>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. </li><li>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.</li><li>I encourage you to submit your work electronically via <a href="https://concourse.nd.edu/webct/logon/174465119011">Concourse</a>. 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. </li></ol>Jeffhttp://www.blogger.com/profile/15416541103643920970noreply@blogger.com0tag:blogger.com,1999:blog-8283335987275320354.post-42240010965665258092009-11-05T12:52:00.003-05:002009-12-19T12:07:57.107-05:00Lecture 1I've posted the <a href="http://www.nd.edu/~jeff/Teaching/ESTM60203/Lecture_01.pdf">presentation notes</a> and a <a href="http://www.nd.edu/~jeff/Teaching/ESTM60203/Lecture_01_Download.zip">folder of examples</a> 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.<br /><div class="separator" style="clear: both; text-align: center;"><a href="http://www.nd.edu/~jeff/Teaching/ESTM60203/Lecture_01_Download/images/Giapettos6.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="300" src="http://www.nd.edu/~jeff/Teaching/ESTM60203/Lectures/Lecture_01_Download/images/Giapettos6.png" width="400" /></a><br /></div><div class="separator" style="clear: both; text-align: left;">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.<br /></div>Jeffhttp://www.blogger.com/profile/15416541103643920970noreply@blogger.com0tag:blogger.com,1999:blog-8283335987275320354.post-91595873796715636362009-10-21T14:56:00.001-04:002009-10-21T15:11:38.666-04:00Revised CalendarThe 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. <br /><br /><div style="text-align: center;"><iframe frameborder="0" height="350" scrolling="no" src="http://www.google.com/calendar/embed?src=utqhhf0frs0to3hh1uni3kosvc%40group.calendar.google.com&ctz=America/New_York" style="border: 0;" width="600"></iframe><br /></div>Jeffhttp://www.blogger.com/profile/15416541103643920970noreply@blogger.com0tag:blogger.com,1999:blog-8283335987275320354.post-1437893454134661742009-09-19T23:30:00.001-04:002009-12-07T23:24:15.304-05:00Syllabus: ESTM 60203<h1 style="text-align: center;">ESTM 60203: Module on Operations Research</h1><h1 style="text-align: center;">Syllabus for Fall, 2009 </h1><div style="text-align: center;"><br></div><div style="text-align: center;"><div><table id="y63m" width="100%" cellpadding="3" cellspacing="0" border="0" class="zeroBorder" bordercolor="#000000"><tbody><tr><td width="100%"><div style="text-align: center">Jeffrey Kantor</div><div style="text-align: center">182 Fitzpatrick Hall</div><div style="text-align: center">Dept. of Chemical & Biomolecular Engineering</div><div style="text-align: center">University of Notre Dame</div><div style="text-align: center">Notre Dame, IN 46556</div><div style="text-align: center"><br></div></td></tr><tr><td width="100%"><div style="text-align: center">Office Hours: Whenever available, but best by Appointment</div><div style="text-align: center">Voice, Text, or Voicemail: 574-699-3525 </div><div style="text-align: center">Mobile: 574-532-4233</div><div style="text-align: center">Email: Kantor [dot] 1 [at] nd [dot] edu</div></td></tr></tbody></table></div><br></div><h3>Mission Statement</h3><div style="text-align: left;"><span style=" font-weight: normal"><font size="2">Provide students with a working knowledge of selected concepts and analytical tools of Operations Research with broad application in process operations. </font></span></div><h3>Learning Outcomes</h3><h3><span style=" font-weight: normal"><font size="2">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.</font></span></h3><div>Students completing this module will be able to:</div><div><ol><li>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.</li><li><font size="2">Formulate and solve network, transportation, and related logistics optimization problems of small to medium scale.</font></li><li><font size="2">Prepare a critical path analysis for medium scale projects, identify the critical path, find earliest finish times and latest start times.</font></li><li><font size="2">Analyze job shop and flow shop performance for deterministic conditions under common prioritization schedules, including FIFO, LIFO, EDD, and SDT.</font></li><li><font size="2">Calculate optimal schedules for job and flow shops under deterministic constraints.</font></li><li><font size="2">Formulate and solve capital allocation problem using mean/variance analysis of return and risk.</font></li><li><font size="2">Calculate optimal inventories using two-stage stochastic decision models with recourse.</font></li><li><font size="2">Prepare decision trees and solve for expected mean value, expected value of perfect information.</font></li><li><font size="2">Analyze case studies using selected tools from Operations Research.</font></li></ol></div><h3>Texts and Other Materials</h3><div>Primary Texts:</div><div><ol><li><u>Operations Management 9/e</u> by Jay Heizer and Barry Render. Published in 2008 by Pearson Education.</li><li>Class presentation slides will be available on Concourse.</li><li>Case Studies (will be provided):</li><ul><li>Merton Truck Co., Harvard Business School Case Study <span style="font-family: Arial, Helvetica, sans-serif"><font size="2">189163-PDF-ENG</font></span></li><li><font class="Apple-style-span" face="Arial, Helvetica, sans-serif"><font size="2">Australian Motors Ltd., H<span style="font-family: Arial, sans-serif"><font size="2">arvard Business School Case Study </font></span><font size="2">OIT23-PDF-ENG</font></font></font></li><li><font class="Apple-style-span" face="Arial, Helvetica, sans-serif" size="3"><font size="2">Optimization Modeling Exercises, H<span style="font-family: Arial, sans-serif"><font size="2">arvard Business School Case Study <span style="font-family: Arial, Helvetica, sans-serif"><font size="2">UV0432-PDF-ENG</font></span></font></span></font></font></li></ul><li><span style="font-family: Arial, Helvetica, sans-serif">IBM DeveloperWorks Series on Linear Programming (available on-line):</span></li><font class="Apple-style-span" face="Arial, Helvetica, sans-serif"><ul><ul><li>Part 1: <a id="w-td" href="http://www.ibm.com/developerworks/linux/library/l-glpk1/" title="http://www.ibm.com/developerworks/linux/library/l-glpk1/" style="color: rgb(85, 26, 139)">http://www.ibm.com/developerworks/linux/library/l-glpk1/</a></li><li>Part 2: <a id="vcaq" href="http://www.ibm.com/developerworks/linux/library/l-glpk2/" title="http://www.ibm.com/developerworks/linux/library/l-glpk2/" style="color: rgb(85, 26, 139)">http://www.ibm.com/developerworks/linux/library/l-glpk2/</a></li><li>Part 3: <a id="qe.q" href="http://www.ibm.com/developerworks/linux/library/l-glpk3/" title="http://www.ibm.com/developerworks/linux/library/l-glpk3/" style="color: rgb(85, 26, 139)">http://www.ibm.com/developerworks/linux/library/l-glpk3/</a></li></ul></ul></font></ol><div><font class="Apple-style-span" face="Arial, Helvetica, sans-serif"><font size="2"><br></font></font></div><div></div><div>Supplementary Materials (available on-line at no cost):<br><ul><li>Case Studies</li><ul><li><a id="h4h-" href="http://www.scienceofbetter.org/index.htm" title="Operations Research">Operations Research</a>. INFORMS web site to describe the benefits of OR in business applications.</li><li><a id="jh2l" href="http://www.bnet.com/2436-13241_23-188245.html" title="P&G's Secret Weapon: "OR Inside"">P&G's Secret Weapon: "OR Inside"</a>. Case study on the application of OR at Proctor and Gamble.</li></ul><li>IBM DeveloperWorks series on linear programming:</li><ul><li>Presentation: <a id="hrm6" href="http://www.linuxconf.eu/2007/papers/Castro.pdf" title="http://www.linuxconf.eu/2007/papers/Castro.pdf">http://www.linuxconf.eu/2007/papers/Castro.pdf</a></li></ul><li>Lecture on Linear Programming</li><ul><li>Gilbert Strang: http://deimos3.apple.com/WebObjects/Core.woa/Browse/mit.edu.1303074306?i=1098364323</li></ul><li><u>Applications of Optimization with Xpress-MP</u> by Christelle Gueret, Christian Prins, and Marc Sevaux. Translated and revised by Susanne Heipcke. Published in 2002 by Dash Optimization, ISBN 0-9543503-0-8. Available from <a id="m6n9" href="http://www.amazon.com/exec/obidos/tg/detail/-/0954350308/qid=1092839645/sr=1-1/ref=sr_1_1/103-4521137-6040621?v=glance&s=books&tag=dashoptimizat-20" title="Amazon.com">Amazon.com</a> or by <a id="m2hd" href="http://www.dashoptimization.com/home/services/publications/applications_book.html" title="download">download</a> from the Dash Optimization web site.</li><li>Other Links</li><ul><li>Barr's Course <a id="rqer" href="http://faculty.smu.edu/barr/models/html/links.html" title="http://faculty.smu.edu/barr/models/html/links.html">http://faculty.smu.edu/barr/models/html/links.html</a></li><li>Operations Research Toolkit: <a id="zzml" href="http://lyle.smu.edu/~barr/ortoolkit/" title="http://lyle.smu.edu/~barr/ortoolkit/">http://lyle.smu.edu/~barr/ortoolkit/</a></li></ul></ul></div></div><div><br></div><div><b><font size="3">Software</font></b></div><h3><span style=" font-weight: normal"><font size="2">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:</font></span></h3><div><ul><li><b>Matlab with Optimization Toolbox</b>. 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.</li><li><b><a id="re0r" href="http://www.gnu.org/software/glpk/" title="GLPK">GLPK</a></b> (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. <a id="rcv9" href="http://cio.umh.es/cursos/programacion_lineal_gnu/glpk/glpsol_tutorial.pdf" title="Tutorials">Tutorials</a> </li><li><b>Excel with Solver</b>. 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 <a id="ok1a" href="http://www.solver.com/mac/dwnmacsolver.htm" title="available from Frontline Systems">available from Frontline Systems</a>.</li></ul></div><div><br></div><div><b><font size="3">Grading</font></b></div><div>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.</div><h3>Schedule</h3><h3><span style="font-weight: normal"><font size="2">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. </font><i><font size="2"> In the event of rescheduling, topics will be covered in the order listed below.</font></i></span></h3><div><div><table id="olwz" cellpadding="3" cellspacing="0" border="1" class="" bordercolor="#000000" width="100%"><tbody><tr><td style="text-align: center;" width="10%">Date </td><td style="text-align: center;" width="15%"><b>Topic</b></td><td style="text-align: center;" width="35%"><b>Reading Materials</b></td><td style="text-align: center;" width="40%"><b>Assignment</b></td></tr><tr valign="top"><td width="10%">Nov 6<br>(Fri., 9-10:15am)</td><td width="15%">Introduction to Linear Optimization</td><td width="35%">1. Quantitative Module B of Heizer and Render, pp. 705-732.<br>2. Part 1 of IBM Developer Works series on Linear Programming.</td><td width="40%">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.</td></tr><tr valign="top"><td width="10%">Nov 16<br>(Mon., 4:30-6pm)</td><td width="15%">Blending Problems</td><td width="35%">Part 2 of IBM DeveloperWorks series on Linear Programming.</td><td width="40%">Assignment 2: Problem B.29 (p. 730) from Heizer & Render. Use the GMPL mathematical programming language to prepare a solution. (Due Fri., Nov 20th)<br></td></tr><tr valign="top"><td width="10%">Nov 18<br>(Wed., 4:30-6pm)</td><td width="15%">Network Flow and Transportation</td><td width="35%">Quantitative Module C, pp. 733-753 from Heizer & Render.<br></td><td width="40%">Assignment 3: Case Study "Custom Vans, Inc.", Heizer and Render, pp. 751-752. (Due Tues., Nov. 24th).</td></tr><tr valign="top"><td width="10%">Nov 20<br>(Fri., 9-10:15am)</td><td width="15%">Project Management</td><td width="35%">Chapter 3 of Heizer & Render, pp. 55-102. </td><td width="40%">Assignment 4: Case Study "Managing Hard Rock's Rockfest", Heizer and Render Video Case p. 101.<br></td></tr><tr valign="top"><td width="10%">Nov 23<br>(Mon, 4:30-6pm)</td><td width="15%">Discrete Optimization</td><td width="35%">Part 3 of the IBM Developer Series on Linear Programming.</td><td width="40%">Assignment 5: Find a solution to today's New York Times Sudoku puzzle.</td></tr><tr valign="top"><td width="10%">Nov 30<br>(Mon., 4:30-6pm)</td><td width="15%">Job Shops and Flow Shops </td><td width="35%">Chapter 15, "Short-Term Scheduling," Heizer and Render.</td><td width="40%">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.<br></td></tr><tr valign="top"><td width="10%">Dec 2<br>(Wed., 4:30-6pm)</td><td width="15%">Uncertainty, Risk, and Diversification</td><td width="35%">Lecture Notes</td><td width="40%">Assignment 7: Prepare a solution to Problem 1 of the "Optimization Modeling Exercises" Case Study using Matlab.</td></tr><tr valign="top"><td width="10%">Dec 7<br>(Mon., 4:30-6pm)</td><td width="15%">Inventory Management</td><td width="35%">Chapter 12, "Inventory Management," of Heizer and Render. pp. 481-523.</td><td width="40%"><br></td></tr><tr valign="top"><td width="10%">Dec 9<br>(Wed., 4:30-6pm)</td><td width="15%">Optimization Under Uncertainty<br><br></td><td width="35%">Quantitative Module 4, "Decision Making Tools," Heizer and Render, pp. 685-704.</td><td width="40%"><br><br></td></tr><tr><td width="10%">Dec 17<br>(Thur.)</td><td width="15%">FINAL EXAM</td><td width="35%"><br></td><td width="40%">Take-Home Final Due at Noon, 12/17</td></tr></tbody></table></div></div><div><br></div><br>Jeffhttp://www.blogger.com/profile/15416541103643920970noreply@blogger.com0