SA305 — Linear Programming

Spring 2015

Sections 3031 and 5031

Asst. Prof. Nelson Uhan

Announcements

20 Apr End-of-semester announcements:
  • Projects. Changes to instructions posted below:
    • Due COB Thursday 30 April
    • E-mail your report and GMPL model/data files to me
  • Final Exam.
    • Tuesday 5 May at 19:30
    • For more information, see the "Exams" section below
  • GMPL Exercises.
    • Due at noon on Wednesday 6 May
    • I will send you the status of your GMPL exercises electronically on Monday 27 April, Thursday 30 April, and Monday 4 May
26 Mar Exam 2 is on Thursday 2 April. See below for details.
10 Mar Instructions for the course project have been posted. See below for details.
3 Feb Exam 1 is on Thursday 12 February. See below for details.
8 Jan Welcome!

General information

GMPL information

Homework

Note: Now that the semester is over, I have taken down the homework solutions.

Numbered problems are from Rader.

GMPL exercises are starred*. For GMPL exercises, formulate a model on paper and write the accompanying GMPL code. Submit your GMPL code using this submission form (also linked above).

Date Problems Solutions
21 Apr rock-paper-scissors rock-paper-scissors
16 Apr pirates*. This is the last GMPL exercise of the semester. pirates
14 Apr 9.5, 9.7, cars 9.5, 9.7, cars
9 Apr 9.1, 9.2, 9.3, 9.4 9.1, 9.2, 9.3, 9.4
7 Apr 8.11ab, 8.12ab 8.11, 8.12
26 Mar 8.1, 8.2, 8.3, 8.8 8.1, 8.2, 8.3, 8.8
24 Mar 7.14, 7.16, 7.17 7.14, 7.16, 7.17
12 Mar 7.2, 7.3, 7.4 7.2, 7.3, 7.4
10 Mar 6.14, 6.18 6.14, 6.18
3 Mar 6.1, 6.2, 6.8, 6.9 6.1, 6.2, 6.8, 6.9
24 Feb 2.6 (redo). Use symbolic input parameters.
diet-part2* (updated 10 March partial model file, data file)
2.6
19 Feb 2.9 (redo), 2.10 (redo), 2.13*, 2.20, 2.22. Use symbolic input parameters. Complete part b in Lesson 14. 2.9, 2.10, 2.13, 2.20, 2.22
5 Feb,
10 Feb
2.14, 2.16. Use symbolic input parameters. 2.14, 2.16
3 Feb sets, 2.3 (redo), 2.24, diet-part1. Use symbolic input parameters. Bring your laptops to the next class. sets, 2.3, 2.24, diet-part1
29 Jan inventory, finco inventory, finco
27 Jan 2.9, 2.10* 2.9, 2.10
22 Jan 2.6, 2.11*, 2.12 2.6, 2.11, 2.12
15 Jan 2.1, 2.3* 2.1, 2.3
13 Jan 1.1abcd, 1.2. Bring your laptops to the next class. 1.1abcd, 1.2
8 Jan 1.1abcd using trial-and-error. For each optimization model, find a few feasible solutions and determine their values. Try to find the best feasible solution you can.

Lessons

Dates Lesson Files
23 Apr, 28 Apr 31 Review notes, solutions
21 Apr 30 LP duality and game theory notes
16 Apr 29 Maximin and minimax objectives notes
14 Apr 28 An economic interpretation of LP duality notes
14 Apr 27 Weak and strong duality notes
9 Apr 26 Bounds and the dual LP notes
7 Apr 25 Degeneracy, convergence, multiple optimal solutions notes
7 Apr 24 Finding an initial BFS notes
31 Mar 23 The simplex method — example notes, completed notes
26 Mar 22 The simplex method notes
24 Mar 21 Basic solutions in canonical form LPs notes
24 Mar 20 Linear programs in canonical form notes
12 Mar 19 Geometry and algebra of "corner points" notes
10 Mar 18 Improving search: convexity and optimality notes
3 Mar 17 Improving search: finding better solutions notes, completed notes
24 Feb 16 Introduction to algorithm design notes
24 Feb 15 Work scheduling models, revisited notes
19 Feb 14 Production process models, revisited notes, completed notes
19 Feb 13 Multiperiod models, revisited notes
5 Feb, 10 Feb 12 Blending models, revisited notes
3 Feb, 5 Feb 11 Resource allocation models, revisited notes, farmerjones.mod, farmerjones-original.dat, farmerjones-new.dat
3 Feb 10 Sets, summations, for statements notes
29 Jan 9 Multiperiod models notes
27 Jan, 29 Jan 8 Production process models notes, notes on Alvin Fine
22 Jan, 27 Jan 7 Work scheduling models notes
22 Jan 6 Blending models notes
15 Jan 5 Resource allocation models notes, thdc.mod
15 Jan 4 Solving optimization models with a computer notes, farmerjones.mod
13 Jan 3 Graphical solutions of optimization models notes, solving animation, outcomes animation
8 Jan, 13 Jan 2 Introduction to optimization modeling notes
8 Jan 1 Introduction notes

Quizzes

Note: Now that the semester is over, I have taken down the quiz solutions.

Date Quiz Solutions
16 Apr Quiz 11 pdf
9 Apr Quiz 10 pdf
26 Mar Quiz 9 pdf
24 Mar Quiz 8 pdf
5 Mar
10 Mar
Quiz 7 pdf
26 Feb
3 Mar
Quiz 6 pdf
19 Feb Quiz 5 - not really a quiz
5 Feb Quiz 4 pdf
29 Jan Quiz 3 pdf
22 Jan Quiz 2 pdf
15 Jan Quiz 1 pdf

Exams

Note: Now that the semester is over, I have taken down the solutions and previous exams.

Project