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 2016, WED 3:00-6:00 PM, JMHH F88
Professor Monique Guignard-Spielberg



  HOME




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: guignard_monique at yahoo.fr
      URL: http://opim.wharton.upenn.edu/~guignard
      Office Hours: By appointment

    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 (?????)

       

      Review of LP duality, and of the primal and dual simplex methods, with emphasis on re-optimization after the addition of violated cuts. The dual simplex method for LPs with upper bounds. Reading another reading (please don't hesitate to click on "short description"! (????)

       

      Branch-and-bound and enumeration. Driebeck penalties. (?????)

       

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

       

      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. Convex nondifferentiable functions and subgradients. (??????)

       

      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. (???????)

       

      Valid inequalities. Chvatal-Gomory procedure. (???????)

       

      Linear programming relaxation and Gomory cuts for pure and mixed-integer problems. (Pure: ???????)

       

      Lifting, covers, lifted covers. (???????)

       

      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 ). (throughout the semester)

       

      Variable fixing, cliques and implication tables, probing. see paper (reading)

       

      Total unimodularity. Relationship with integer feasible solutions for integer programming problems. Special cases of network flow problems. (???????)

       

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

       

      Relaxations. Surrogate relaxation and surrogate duals (???????).

       

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

      ~~~~~~~~~

       

    • For fun, play with this knapsack tutorial (???????)

    • New paper


    back to the top

      HOME




    Class Notes


    • LR tutorial file.

      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