Operations Research (SWFR ENG 4O03 / COMP SCI 4O03) Tutorial

TA: Feng Xie, xief@mcmaster.ca, ITB 116

Tutorials

Tutorial 1 (Jan. 15, 2010): Using softwares to solve linear programs.
Tutorial 2 (Jan. 29, Feb. 5, 2010): Two-phase Simplex method; Octave/Matlab script drawing the feasible region of the example problem; A geometrical view of Simplex method.
Tutorial 3 (Feb. 26, 2010): Solving Knapsack problems using dynamic programming.
Tutorial 4 (Mar. 12, 2010): Single source shortest path: Trip planning problem; Notes used in the tutorial.
Tutorial 5 (Mar. 30, 2010): Comments on assignment 3 & maximum flow, Notes used in the tutorial.

Extras

Degeneracy in LP: PDF file. Note: degeneracy is not a required material of the course; it is here to help understand the Simplex method better.

Solving linear programs

A linear program can be solved in many different ways. The example problem used can be found here.

Using Excel

The solver can be found in the Analysis toolbar of the Data tab. It is not activated by default. To activate it, click the Microsoft Office Button, then Excel Options, followed by Add-Ins. In the Manage list, choose Excel Add-ins, click Go, check the Solver Add-in box, and then click OK.

Find here the detailed steps of using the solver and the spreadsheet file for the example problem.

Using Matlab

The LP solver offered by Matlab is called linprog. Note that linprog always minimizes a function.

To use Matlab on server moore.mcmaster.ca, log in using ssh with your MAC ID, then type matlab (or matlab -nodisplay if you have no local X Window client). Issue the following commands to solve the example problem:

Specify the coefficients of the function to minimize: f = [-300; -500; -400]
Specify the coefficients of the left hand side of <= constraints: A = [3, 4, 4; 2, 3, 2]
Specify the constants of the right hand side of <= constraints: b = [80; 50]
Specify the lower bounds of the variables: lb = zeros (3, 1)
Solve it: linprog (f, A, b, [], [], lb)

Using AMPL (a modeling language)

AMPL student version can be downloaded from www.ampl.com.

The model and data files for the example problem are tut1.mod, tut1.dat. Issue the following commands in AMPL to solve the problem:

Specify model file: model tut1.mod;
Specify data file: data tut1.dat;
Choose solver: option solver cplex;
Solve it: solve;
Display variables: display x;

More examples:

The postal worker scheduling problem from the class: post.mod, post.dat, post2.mod, post2.dat, post3.mod, post3.dat. Note that post2 uses indexed parameter and variable; post3 uses indexed constraints.
Subsidiary investment problem: invest.mod, invest.dat.

Using callable library

A callable library allow users to call the solver as a subroutine from some other program. Here is a rather rudimentary implementation of the Simplex method: simplex.cc. It can only handle the standard form. To solve the example problem, input:


	2 5

	3 4 4 1 0

	2 3 2 0 1

	80 50

	300 500 400 0 0

A geometrical view of Simplex method

Algebraic view	Geometrical view
variables	dimensions
inequality constraint	halfspace
objective function	objective vector
slack variable	"distance" from hyperplane
feasible solution	point in feasible region
basic feasible solution	vertex of feasible region
initial basic feasible solution	starting vertex of "hopping"
optimal basic feasible solution	furthest vertex in the direction of objective vector
one iteration of Simplex method	one "hopping" from current vertex to a neighboring vertex by following an edge
candidate entering variables	edges from the current vertex that follow the direction of the objective vector
pivot rule	dictates which edge to take for the next "hopping"
leaving variable	dictates how far a "hopping" can be (where the next vertex is)

Updated on Mar. 29, 2010.