Refresh to update time/temperature in Philadelphia, click for forecast:

Click for Philadelphia, Pennsylvania Forecast

General -- New this week -- Syllabus -- Textbook -- Class Notes -- Homework -- Grading-- Exam-- Handouts -- Projects -- Links -- Historical perspectives OPIM-916



Department of OPIM

OPIM-916: Advanced Integer Programming

Spring 2007, Tuesdays & Thursdays 4:30-6:00 PM, 260, JMHH
Professor Monique Guignard-Spielberg



  HOME






New this week

    Exam Period (starting April 26).

    The exam is available here. Please send me an email when you pick it up and another one when you return it.
    Don't forget to return the "no cheating" form at the same time as the exam.
    The project report is due at the latest May 4.
    Both the exam and the report must be returned to one of the secretaries in the OPIM Department.
    Week of April 16.

      Homework 5 is posted. Due on 4/24 (day of class presentations).
      Project presentations: 5-7 pm, Tuesday April 24, room TBA.
    Week of April 9.

      Makeup class on 4/11 in room TBA.

      Please download the following gams code and gams listing
      showing how to do column generation for the cutting stock problem,
      as well as a gams code and gams listing
      showing how to do column generation for the strong Lagrangean relaxation of the GAP
      and the put file with results.
      The data set is here.

      For more information on the cutting stock problem, go to wikipedia or the Argonne Lab page or on Erwin's page.
      Finally if you want a more visual introduction to this problem, click on this, solve your own problem online, and "view" the answer!

      The following link is presenting Benders algorithm in a gams context.

    Week of March 26.

      Makeup class on 3/28 in room F38
      Makeup class on 4/04 in room F86
      HW4 is available.


    Week of March 4.

      Spring break and following week: no classes, but... you may want to look at these sites, either for your project or for additional learning!

      global optimization . teaching the TSP.


    Week of February 26

    • We will look at Dantzig and Wolfe decomposition and column generation. You may want to print the following paper. (posted February 26).


    Week of February 19

    • Look for HW3. Also read Chapter 10. And there is more in the "project" section. (posted February 20).


    • There will be an extra class on Wed., February 21, 4:30-6. Room F85. (posted February 20).


    Week of February 12

    • Valid inequalities and Chvatal-Gomory procedure: read classnote 2. (posted February 12).


    • If you are interested in reading about dynamic programming, I would suggest the following tutorial . (posted February 14).


    Week of February 5

    • Valid inequalities and Chvatal-Gomory procedure (in textbook, p. 113-121. (February 6).
      Additional readings: download from Discrete Mathematics, Volume 306, Issues 10-11 , 28 May 2006, Pages 886-904.
      This is a reprint of the 1973 paper by Chvatal.
    • Look for HW2.
    • You can download the book by Martello and Toth on the knapsack problem. You can also download the fortran codes for these problems.
    • And finally have some fun with an interview of Chvatal.

    Week of January 29
    Week of January 15

      Review of primal and dual simplex methods, with emphasis on re-optimization after the addition of violated cuts. (January 16 and 18) Reading


    You may be interested in the following site that
  • provides useful Operations Research Links,
  • suggests books on OR, and
  • provides OR-Objects, i.e., a collection of 500 Java classes for developing Operations research, Scientific and Engineering applications. It contains data structures and algorithms for developing problem specific solutions as well as implementations of classical algorithms.


back to the top

  HOME



General Information

    Course Description



    Many optimization models include either integer or 0-1 decision variables. The integrality requirements make the problems much harder to solve than the corresponding continuous optimization problems. The course will provide students with a variety of analytical and algorithmic tools for approaching such hard problems. Emphasis will be on modeling, as well as on approximate (heuristic), and exact (iterative and enumerative) methods.



    Prof. Monique Guignard-Spielberg
    Office: 569 JMHH
    Phone: 215-898-8235
    Email: monique_guignard at yahoo.com
    URL: http://opim-sun.wharton.upenn.edu/~guignard
    Office Hours: Tuesday, 1:30 to 2:45 p.m.

 back to the top

Textbook



    The textbook used is “Integer Programming”, by L. Wolsey, Wiley, 1998.

    Errata in the text

     

    Additional reading material will be distributed during the semester.

back to the top

  HOME




Course Syllabus

    List of topics to be covered:

     

    Course overview. Examples of problems with large integrality gaps, and with feasible rounded solutions yielding large relative gaps (January 9)

     

    Review of LP duality, (January 9) and of the primal and dual simplex methods, with emphasis on re-optimization after the addition of violated cuts. (January 11 and 16) Reading

     

    Branch-and-bound and enumeration (January 9) . Driebeck penalties. (January 16 and 18)

     

    0-1 knapsack problems. Their LP solutions. BB. Cover inequalities.(January 23)

     

    The simplex method with upper bounds. (January 25)



    LP duality and the Lagrangean function. (January 30)



    For this section, download the following tutorial. Primal relaxation and Lagrangean relaxation, geometric interpretation, integrality property. Integer linearization property, application to the capacitated p-median problem. Analysis of Lagrangean relaxation schemes and quality of bounds from the viewpoint of the geometric interpretation. Application to the GAP and review of all possible constraint dualizations. Integer linearization property for the capacitated facility location problem when the demand constraint is dualized. The bi-knapsack problem. Construction of the Lagrangean function for the total Lagrangean relaxation. Integrality property. Properties of the Lagrangean function. Examples. Contours, subgradient method. Dantzig-and-Wolfe decomposition algorithm, solution of the Lagrangean dual by column generation: example of the multi-item capacitated lotsizing problem and the GAP. Extensions of Lagrangean relaxation: Lagrangean decomposition and substitutions. Examples. (Start February 1)

     

    Valid inequalities. Chvatal-Gomory procedure. (February 6)

     

    Linear programming relaxation and Gomory cuts for pure (February xx) and mixed-integer problems. (February xx)

     

    Lifting, covers, lifted covers. (February xx)

     

    Modeling integer programming problems: choice of decision variables and of constraints, simple strengthening techniques. Examples: SPLP, CPLP, lotsizing, with and without disaggregation. Integrality gaps. Model tightening (see paper). (February xx)

     

    Variable fixing, cliques and implication tables, probing. note to read (February xx)

     

    Total unimodularity. Relationship with integer feasible solutions for integer programming problems. Special cases of network flow problems. (February xx, March xx)

     

    Benders partitioning for mixed-integer problems (March xx). Examples. Initialization. Gams coverage of Benders.   Benders inequalities of types I and II, obtained from simplex tableau ( March xx) and their use outside of the partitioning algorithm (March xx) .  Special examples with and without dual extreme rays. (March xx).

     

    Relaxations. Surrogate relaxation and surrogate duals (March xx, xx, xx).

     

    Convex nondifferentiable functions and subgradients. (March xx).

     

     

    Applications: airline crew scheduling, lotsizing, facility location, production scheduling... (throughout the semester).

    ~~~~~~~~~

     

  • For fun, play with this knapsack tutorial (Feb. --)

  • New paper


back to the top

  HOME



Class Notes


  • More will come later.
back to the top

Grading Policy

  • Homeworks: 1/3
  • Projects: 1/3
  • Final Exam (take-home): 1/3
back to the top

Homework

  • All homeworks must be turned in at the beginning of class on the days they are due.
  • Late homeworks will not be accepted!
  • Computer software (LINDO, EXCEL, GAMS, etc.) can only be used to solve problems that ask you to do so. All other problems have to be solved by hand.


    • Homework #1, due January 30.
    Homework #2, due February 14.
    Homework #3, due March 20 (corrected on March 1).
    Homework #4, due April 10.
    Homework #5, due April 24.
back to the top

Term Projects

  • A term paper related to some IP topic. A few papers have been selected and are available here. Keep checking as additional papers may be added in the coming weks.
    You may also look at the following link.

    • back to the top

    Exam

    • Final Exam: Take-home, during the final exam period.


    back to the top

    Handouts

    • Handout 1: Course syllabus & assignments, this file (posted January 15)


    back to the top

    Interesting Links about Operations Research/Management Science



    back to the top

    Historical perspectives

      Ralph Gomory was one of the first to generate and use cutting planes to solve MIP problems. You can read this paper to gain some insight into his research.

      Peter Hammer, one of the most important contributors to integer programming for several decades, died in a car accident in late December 2006. To lear more about him and his contributions, you can go to this address.


    back to the top

      HOME



    OPIM 916
    Last Updated:

     

    detect 4 you are coming from

    Weather?