Kurzbeschreibung

Literatur

• Korte, B. und Vygen, J.; Combinatorial Optimization, Springer 2000

• Wolsey, L. A.; Integer Programming; Wiley 1998

• Cook, W. J., Cunningham, W.H., Pulleyblank, W. R., Schrijver, A.; Combinatorial Optimization; Wiley 1998

• Schrijver, A.; Theory of Linear and Integer Programming; Wiley 1986

• Groetschel, M., Lovasz, L., Schrijver, A.; Geometric Algorithms and Combinatorial Optimization, Springer 1988

Übung

• Exercise 1: AMPL, AMPL-Guide, new language features, example files steel.mod and steel.dat, NEOS
• Exercise 2: CPLEX Manual, cplextest.cxx, makefile.cplex, cpxtest.lp
  Initial cutting stock relaxation: cutstock0.cxx, simple test data file: custstock.dat
• Exercise 3: Standard Template Library links: SGI Reference, C/C++ Reference
  Header file with knapsack prototype: knapsack.hxx
  Implementation: knapsack.cxx
• Exercise 4:
  Makefile with linking and dependencies: makefile.cutstock
  Example column generation output for custstock.dat: cutstock1.log
  A debugger on Linux is ddd. For debugging compile with -g and call: ddd your_program
  Implementation: cutstock1.cxx
• Exercise 5: LEDA
  Example: ledagraph.cxx, makefile.leda
  Interface: random_2D_graph.hxx, random_2D_graph.cxx
  Implementation: makefile.r2Dgraph, leda_r2Dgraph.cxx
• Exercise 6: One-Tree Relaxation by a subgradient algorithm.
  Use the graph generator of Exercise 5 as input.
  Interface: Lagrange_Onetree.hxx, makefile.onetree
  Within this routine you may use the One-Tree routine onetree.hxx, onetree.cxx.
  After each call to the Interface, display the primal solution.
  Implementation of Lagrange_Onetree: Lagrange_Onetree.cxx
• Exercise 7: complete exercise 6: compute the One-Tree relaxation by a subgradient algorithm.
  Implementation of the main program: leda_onetree.cxx
• Exercise 8: Replace in this code the subgradient method by a bundle method (together with primal aggregation).
  Load and install the callable library ConicBundle.
  Suggestion: Use multiple inheritance, e.g.
     class OnetreeFunction: public FunctionOracle, public Lagrange_Onetree{...};
  makefile.cb_onetree
  
• Exercise 9: Complete Exercise 8.
  Implementation: cb_onetree.cxx
• Exercise 10: Polymake; it has a tutorial. Note: Polymake uses a homogeneous represenation.
  E.g. Give vertices of the cube via a file cube.poly; call "polymake cube.poly FACETS"; call "polymake cube.poly VISUAL" for 3D rendering.
  Use Matlab or C(++) to generate the vertices of the STSP on the complete graph with n vertices (n small!), generate all facets by using polymake.
  Use Matlab to check if and which facets are violated by some fractional solution.
  Matlab Code for generating all vertices: set variable $n$ to the number of nodes and call script stsp.m (the script uses the function stsp_recursion.m), then call stsp_write.m, which writes the points to the file "stsp.poly" for use with polymake.
• Exercise 11: Implement the ellipsoid method in Matlab.
• Exercise 12: Implement the continuous fraction method for approximating real numbers.
• Exercise 13: Use SEDUMI (an SDP-package building on MATLAB) to set up the semidefinite relaxation for Max-Cut and implement the rounding method of Goemans and Williamson.