Lecture Summaries  for COMP 567                    Fall 2013

      also check:   news                        return to: course home page
Please report any errors in the lecture notes, thanks!
Sep 3:  Course introduction, motivation and examples of course projects
Sept 5:  We discussed formulations of the knapsack problem, bipartite-matching and the travelling salesman problem(TSP) as integer programs. notes
              We used lp_solve for the TSP problem. Sample lp_solve files are here.
Exercises:
1. Read the notes and consider inequality (5) on P. 2. Consider any subset S and the complementary subset S' = {1,2,...,n} \ S. That is, S' contains all the cities not in S. Show that, in the presence of (3) and (4), inequality (5) using S is equivalent to inequality (5) using S'. (In class we saw subtour violations for both S={2,3,4} and S'={1,5}, but I only needed to add one inequality to the lp_solve file.)
2. Prove that the 0-1 solutions to the system of equations/inequalities defined by (3),(4),(5) are precisely the tours that visit each city exactly once and return to the starting point. You need to prove two things: (i) every such tour gives a feasible 0-1 solution and (ii) each 0-1 solution is such a tour.
Sep 10: Linear programming and the simplex method. This may be the most important lecture of the course, as everything will build on this. Therefore it is essential to understand the reading material LP_en.pdf and  notes         DO THIS EXERCISE!!

Exercise: Write down your own LP with two constraints and four variables (or more!) and solve it by hand according to the method in today's lecture.
Sep 12: More on linear programming: how to get an initial starting solution, cycling example. Read  LP2_en.pdf and   notes
Exercise: From   LP2_en.pdf do exercise 3.9 on p. 44, all three parts.
Sep 17 :   Duality. Weak and strong duality theorems. Read  notes 
Exercise: Write down the dual of each problem in ex 3.9 (Sep 12).
In each case figure out exactly the situation of the dual problem (optimum solution or unbounded or infeasible) and compare with primal outcome.
You results should be consistent with the table on page 5-6 of the   notes 
Sep 19     More on duality. Proof of weak duality. Economic interpretation of duality. Adding new variables to a problem. Brief discussion on complexity of solving LPs.
Exercise: Solve all three parts of problem 2.1 on P.26 of the handout LP2_en.pdf. In each case you need only give the final optimum dictionary. Next obtain the dual variables (described at the bottom of P5-4 of notes ) from these optimum dictionaries and verify the optimality of each solution.
Assignment 1: Exercises from lectures on Sept 5,10,12,17,19 due in class on Sep 24 !
Sep 24  The dual simplex method and Gomory's cutting plane algorithm for integer programming. slides      V. Chvatal's notes1  notes2
   The big picture is here!
(Note: the Chvatal notes were just typeset by Kenji Okuda into latex. The original notes are  notes1  notes2. Kindly report any misprints to me, thanks !)
Exercise: Using the cutting plane method shown on the slides to show there is no integer solution to max x1+x2 st. x1 >= 1/2,  x2 >= 1/2, x1+x2 <= 3/2.
Show the optimum (or infeasible) dictionary at each step and how to derive the cutting plane. (You do not need to show all the details of the pivots).
Sep 26 Fixed costs and disjunctions. We looked at the Uncapacitated lot size (ULS) problem with fixed costs. We saw two formulations.  The second one has only integer vertices, so linear programming will give an optimum integer solution.  notes    input files   
A proof that the formulation in Section 4 gives integer solutions was obtained by Wolsey.
Exercise: Consider an instance ULS with n = 5, demands d = (5, 4, 9, 3, 6), variable production costs p = (3, 1, 3, 2, 4), and fixed production costs f = (20, 30, 25, 10, 5).
The storage costs are $1/unit per period. All variables are integer valued.
Formulate the problem as an ILP using both formulations in the notes. Solve each formulations using lp_solve both as (i) an ordinary LP and as (ii) an ILP
Oct 1-10 Mini-course on stochastic programming with mining applications.
Oct 1 　Guest lecturer: Amina Lamghari.　　Introduction to stochastic programming． Based on: Birge J.R., Louveaux F., Introduction to stochastic programming, Springer,  slides
Exercises (refer to slides for data)
1. Assume the farmer allocates his land according to the solution based on expected value, i.e., 120 acres of wheat, 80 acres of corn and 300 acres for sugar beets.
Show that if the yields are random (20%below average, 20% above average for all corps with equal probability one third), his expected annual profit is $107240.
2. Consider the same farmer's problem, with the difference that if in a good yield year, the price of corn and wheat goes down by 10%, and in a bad weather year, it goes up by 10%. Formulate this problem as an LP and solve it using lp_solve.
Oct 3  Guest lecturer: Roussos Dimitrakopoulos. An SIP formulation for production scheduling and application at a gold mine: An industry example of the value of stochastic solutions. paper1  paper2  slides
Oct 8 Guest lecturer: Amina Lamghari. Metaheuristics for scheduling production in large-scale open-pit mines accounting for metal uncertainty - Tabu search as an example.  paper  tutorial on tabu search. slides
Oct 10  Guest lecturer: Ryan Goodfellow. Multistage Stochastic Programming and an Application to Production Scheduling in Mining paper   slides
Oct 15  We discussed branch and bound and branch and cut strategies for integer programming. Vardges Melkonian's   slides  bb1.ppt, bb2.ppt 
Exercise: Solve the problem given in the slides bb1.ppt by first branching on x_1 (not on x_2). Show the full solution tree. You can use lp_solve to solve the LPs.
Oct 17  Another flowchart for branch and cut essentially derived from the wiki page branch and cut.
Crew scheduling problem. We formulated it as an integer linear program after preprocessing.
The files we used in class for lp_solve are here.  notes
No Exercise: Work on those proposals !
Oct 22 Consultant teams 3 and 1.  20 mins presentation (all team members) + 15 minutes discussion (all management members)
 List of project descriptions
Assignment 1 will be returned in class on Oct 24. Solutions are posted in assignments
Oct 24 Consultant teams 4 and 2.  20 mins presentation (all team members) + 15 minutes discussion (all management members)
Assignment 2: Please hand in exercises from Sept 24,26, Oct 1, Oct 15 at the beginning of class on Oct. 29.
I will go through the solutions in class, so no late assignments please!
Oct 29 Review session. Suggestions welcome! Solutions for Sep 24 and Oct 15 are here and Oct 1 (not covered on class test) is here.
Oct 31 Class test. Test covers material and exercises from lectures Sep 3 - Sep 26 and Oct 15,17,24.
Nov 5: We looked at computing ideal formulations and applied it to the knapsack problem.     lecture notes     lrs instructions
Exercise: Do both exercises in the lecture notes.
Nov 7: We studied two completely different integer programming formulations of the one machine scheduling problem with precedence constraints and release times. The objective was to minimize weighted completion time. See the  notes
Exercise: Use the precedence graph in the notes and generate a set of process times and weights for the seven jobs. You may assume no release times.
Now formulate an integer program for the minimum weighted completion time using the second method in the notes (ie. variables x_ij for jobs i and j ).
Solve the problem using lp-solve.
Nov 12: Valid inequalities for LPs, ILPs and the Chvatal-Gomory procedure. Read: Sections 8.1-8.3 (except the proof of Thm 8.4)
            A very good description of C-G procedure is in Jochen Konemann's slides (48-71)
Exercise: Refer to the lecture notes for Nov 5, Section 2.1 and 2.2.
Use the Chvatal-Gomory procedure to generate the cover inequalities: x_1 + x_4 <= 1 and x_3 + x_4 + x_5 <=2 for the given Knapsack problem.
Nov 14:
Nov 19:
Nov 21: Assignment 3 consisting  of exercises from Nov 5 - Nov 14 is due in class. 
              Project session!
Nov 26: Progress reports: Team 2 followed by Team 4
Nov 28: Progress reports: Team 1 followed by Team 3