Course homepage
SECTION FOR OPERATIONS RESEARCH

 
 

Course 42113 (formerly 02713): Networks and Integer Programming - Fall 2010

Welcome to the home page of course 02713. Here you will find information relevant to the course as well as links to project descriptions, slides etc.

Course information - Fall term 2010.

Information regarding the lecture plan and teaching material will be available here. The lecture plan can be subject to changes during the course.

  • The current lecture plan for the course is always available here. We will try to update it asap whenever changes occur.

  • Here is the small introduction to CPLEX.
  • Here is a small guide to the GBAR unix system here.

  • You can find a list of corrections to "Integer Programming" here.
  • This is a link to the latest version of the Supplementary Notes to Networks and Integer Programming.
  • This is a link to a short appendix on Linear Programming.
  • Project assignment 1 can be downloaded here (new, updated version).
  • Project assignment 2 is ready. Download it here.

    Oral exam - fall 2010

  • Curriculum for the course and the exams questions (fall 2010). Is now fixed
  • Here is the schedule for the oral exam for fall 2010. On all three days the oral exam will take place in room 019, building 424. Be ready at the time given in the schedule. Here you will draw your exams question, and thereafter be given approx 30 min to prepare before the examination.

    • Exercises, slides and solutions

    Below we will put in the information about exercises, slides and selected solutions.

    Date Exercises Solutions Course material
    31. aug No Exercises   Introduction Solving real-life problems
    3. sep Handouts: 1-7
    Handouts: 1-5 6, 7     		Basic LP
    7. sep Handouts: 8-11
    Handouts: 8-11     		Basic LP Duality
    10. sep LW1: 1, 2 (i) and (ii), 4, 5; handout 1(a)
    LW1: 1, 2 (i) and (ii), 4, 5; A container problem     		IP modelling Extra: Concepts
    14. sep LW1: 7, 8, 14
    LW1: 7, 8, 14     		Formulations
    17. sep LW1: 11, 13. LW2: 4, 5, 7, 8
    		Relaxation
    21. sep Binary Trees, Disjoint Sets, Quicksort (can be found on campusnet) Answers Data Structures and Complexity
    24. sep LW3: 8 (try both Kruskal and Prim); LC3: 1, 2, 3
    LW3: 8; LC3: 1, 2, 3     		MST
    28. sep LC4: 1 (check the result by entering the IP model into CPLEX), 3(a,c,d,e,f)
    LC4: 3(a,c,d,e,f)     		Shortest Path
    1. oct CO3: 2, 7, 16 (copies)
    CO3: 2, 7, 16     		Max Flow
    5. oct CO3: 46, 48 (copies)
    CO3: 46, 48     		Unimodularity, Preflow-push Max Flow
    8. oct LW3: 1; LC7: 1; LC4: 3(b) (use augmenting circuit algorithm)
    LC7: 1     		Min Cost Flow - Augmenting cycle
    12. oct LC4: 3(b) (use network simplex); Handout
    LC4:2(b) Solution for handout     		Min Cost Flow - Network simplex
    29. oct LW5: 1, 3, 5, 10
    LW5: 1, 3, 5, 10     		Dynamic Programming
    2. nov LW6: 1, 3, 8 (difficult!)
    LW6: 1, 3, 8     		Complexity & Problem Reduction
    5. nov LW7: 1, 3, 9
    LW7: 1, 3, 9     		LP-based Branch-and-Bound Overheads
    9. nov LW7: 5
    LW7: 5     		Branch-and-Bound
    12. nov LW10: 1, 5, 8
    LW10: 1, 5, 8     		Lagrange
    16. nov LW8: 1, 2 (i) (ii) (iv), 3; Gomory exercise
    LW8: 1, 2 (i) (ii) (iv), 3 Solution to Gomory exercise     		Cuts Gomory cuts
    19. nov LW9: 4(i), 5(i, ii), 8
    LW9: 4(i), 5(i, ii), 8     		Strong Valid Ineq.
    30. nov LW12: 1, 4, 5
    LW12: 4, 5     		Heuristics
    3. dec No exercises   B&C symmetric TSP

    Supplementary literature

    Supplementary literature to the subjects presented can be:


    Last modified  6 December 2010