Syllabi

• Gérard Cornuéjols
  
  

  "Mixed integer programming"

  This tutorial will cover recent developments in integer programming, especially those related to the most successful approaches in current software. In particular it will emphasize the theory of valid inequalities for mixed integer linear programs. Branching rules, preprocessing and heuristics will also be discussed. The last lecture will cover new progress in integer nonlinear programming.

  Bibliographic references

  1. K. Andersen, G. Cornuéjols and Y. Li, Reduce-and-split cuts: Improving the performance of mixed integer Gomory cuts, Management Science 51 (2005) 1720-1732.

  2. E. Balas, Disjunctive programming, Annals of Discrete Mathematics 5  (1979) 3--51.

  3. E. Balas, S. Ceria and G. Cornuéjols, A lift-and-project cutting plane algorithm for mixed 0-1 programs, Mathematical Programming 58 (1993) 295--324.

  4. E. Balas and M. Perregaard, A Precise correspondence between lift-and-project cuts, simple disjunctive cuts and mixed integer Gomory cuts for 0-1 programming, Mathematical Programming B 94 (2003) 221--245.

  5. V. Chvatal, Edmonds polytopes and a hierarchy of combinatorial optimization, Discrete Mathematics 4 (1973) 305--337.

  6. W. Cook, R. Kannan and A. Schrijver, Chvatal closures for mixed integer pogramming problems, Mathematical Programming 47 (1990) 155--174.

  7. R.E. Gomory, An algorithm for integer solutions to linear programs, Recent Advances in Mathematical Programming, R.L. Graves and P. Wolfe eds., McGraw-Hill, New York (1963) 269--302.

  8. L. Lovasz and A. Schrijver, Cones of matrices and set-functions and 0-1 optimization, SIAM Journal of Optimization  1 (1991) 166--190.

  9. G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization}, Wiley, New York (1988).

  10. Schrijver, Theory of Linear and Integer Programming, Wiley, New York (1986).

   

• Sanjeeb Dash  - lecture notes
  
  

  Title: "Mixed integer rounding cuts and cyclic group polyhedra"

  Abstract: We study an important class of integer programming cutting planes, namely the mixed integer rounding (MIR) cuts, and discuss three aspects of these cuts.

  1. We review the equivalence of MIR cuts and split cuts, and give a mixed-integer program to separate an arbitrary point from the split closure of a polyhedron. Along the way, we give a short proof that the split closure of a polyhedron is a polyhedron, based on properties of MIR cuts.
  2. We show how to extend MIR cuts to what we call two-step MIR cuts and give a numerical study of two-step MIR cuts.
  3. We review the connection between MIR cuts and facets of the master cyclic group polyhedra of Ralph Gomory (1969). We review the use of these polyhedra in integer programming, and recent results on their facet structure. Based on the connection with MIR cuts, we analyze the strengh of Gomory mixed integer cuts (which are MIR cuts applied to simplex tableaus of LP relaxations) for a number of practical integer programming instances.

  Bibliographic references

  1. W. Cook, R. Kannan, and A. Schrijver, Chvatal closures for mixed integer programming problems, Mathematical Programming,  47, 155--174 (1990).

  2. S. Dash and O. Gunluk, Valid inequalities based on simple mixed-integer sets, Mathematical Programming,  105, 29--53 (2006).

  3. S. Dash and O. Gunluk, Valid inequalities based on the interpolation procedure, Mathematical Programming, v  106, 111-136 (2006).  

  4. S. Dash, O. Gunluk and M. Goycoolea. Two step MIR inequalities for mixed-integer programs. IBM Research Report RC23791, 2005.

  5. M. Fischetti, C. Saturni, Mixed-Integer Cuts from Cyclic Groups, Integer Programming and Combinatorial Optimization (M. Juenger and V. Kaibel eds.),  Lecture Notes in Computer Science 3509, Springer-Verlag Berlin Heidelberg, 1-11, 2005.

  6. M. Fischetti, A. Lodi, Optimizing over the first Chvatal closure, Integer Programming and Combinatorial Optimization (M. Juenger and V. Kaibel eds.),  Lecture Notes in Computer Science 3509,  Springer-Verlag Berlin Heidelberg, 12-22, 2005.

  7. R.E. Gomory, Some polyhedra related to combinatorial problems, Journal of Linear Algebra and its Applications,  2, 451--558 (1969).

  8. R.E. Gomory and E. Johnson, Some continuous functions related to corner polyhedra I,  Mathematical Programming,  3,  23--85 (1972).

  9. R.E. Gomory and E. Johnson, Some continuous functions related to corner polyhedra II,  Mathematical Programming,  3, 359--389 (1972).

  10. R.E. Gomory, E.L. Johnson, and L. Evans, Corner Polyhedra and their connection with cutting planes, Mathematical Programming,  96, 321--339 (2003).

• Fritz Eisenbrand - lecture notes
  
  

  "My favorite open problems in integer programming"

  The theory of integer programming has fascinated many mathematicians and computer scientists in the last 40 years. In this long history, many important problems have occurred, some of them still remain unsolved and challenge the community.

  In this tutorial we bring three classical open problems back to the forefront and we discuss some recent progress around them. These problems are:

  • Cutting Stock: What is the integrality gap of cutting stock? Can we solve cutting stock with a fixed number of item sizes?
  • Hilbert Bases: Can we recognize a Hilbert basis in polynomial time? Do we really need lattice basis reduction to do that in fixed dimension?
  • Complexity of integer programming: Is there a linear (incremental) algorithm for integer programming in fixed dimension?

  Bibliographic references

  1. Alexander Schrijver, Theory of Linear and Integer Programming, New York : Wiley, 1998.

  2. R. Motwani and P. Raghavan, Randomized Algorithms. New York: Cambridge Univ. Press, 1995.

  3. B. Gärtner and E. Welzl, Linear Programming Randomization and Abstract Frameworks, STACS 96 : 13th Annual Symposium on Theoretical Aspects of Computer Science, Grenoble, France, February 22-24, 1996 : proceedings, C. Puech and  R. Reischuk  (eds),  New York : Springer, 1996.

  4. R. Seidel, Small-dimensional linear programming and convex hulls made easy. Discrete & Computational Geometry, pages 423--433, 1991. Las Vegas algorithms for linear and integer programming when the dimension is small,  Journal of the ACM, 42 (2):488--499, 1995. Preliminary version in FOCS '88: Proceedings of the Twenty-ninth Annual IEEE Symposium on Foundations of Computer Science, 1988.

  5. S. Thomas McCormick, Scott R. Smallwood and Frits C. R. Spieksma, A Polynomial Algorithm for Multiprocessor Scheduling with  Two Job Lengths, Math. Oper. Res. 26 (1), 2001, 31-49. (http://dx.doi.org/10.1287/moor.26.1.31.10590)

  6. F. Eisenbrand, Fast integer programming in fixed dimension, In G. Di Battista and U. Zwick (eds.), Proceedings of the 11th Annual European Symposium on Algorithms, ESA' 2003, Springer, 2003, 196-207

  7. R. Kannan, Lattice Translates of a polytope and the Frobenius problem, Combinatorica, 12 (2) (1992) 161-177.

   

• Lisa Fleischer
   

  "Generalized congestion games"

  The societal value of a distribution of finite resources is frequently measured in terms of of aggregate utility. Decisions, however, are frequently controlled by noncooperative agents who try to maximize their own private utility. Papadimitriou coined the term "price of anarchy" to refer to the ratio of social utility achieved by selfish agents versus the optimal social utility. For the network routing game proposed by Wardrop in the 1950's to model traffic flow, the price of anarchy can be arbitrarily bad. We review these results, and then describe some solutions to prevent this bad outcome. These include charging users for network use; and managing a small portion of traffic wisely. Some of these results carry over to more general congestion games.

  Bibliographic references (tentative)

  1. D. Acemoglu and A. Ozdaglar. Competition and Efficiency in Congested Markets, Mathematics of Operations Research, 2006.
     B. Awerbuch, Y. Azar and A. Epstein. The price of routing unsplittable flow. Proc. STOC 2005, pp. 57-66.

  2. G. Christodoulou and E. Koutsoupias. The price of anarchy of finite congestion games.  STOC, 2005.

  3. R. Cole, Y. Dodis, T. Roughgarden. How Much Can Taxes Help Selfish Routing? EC 2003.

  4. R. Cominetti, J.R. Correa and N.E. Stier Moses. Network Games with Atomic Players. Manuscript 2006.

  5. J.R. Correa, A.S. Schulz and N.E. Stier Moses. On the Inefficiency of Equilibria in Congestion Games.IPCO 2005 pp. 167--181.

  6. J.R. Correa, A.S. Schulz, N.E. Stier Moses. Selfish Routing in Capacitated Networks,  Mathematics of Operations Research 29 (2004), 961-976.

  7. L. Fleischer, K. Jain, and M. Mahdian. Tolls for Heterogeneous Selfish Users in Multicommodity Networks and Generalized Congestion Games FOCS 2004.

  8. F. P. Kelly. Charging and rate control for elastic traffic, European Transactions on Telecommunications, 8, pp. 33-37, 1997.

  9. R. Johari, and J. N. Tsitsiklis. (2004). Efficiency loss in a network resource allocation game.

  10. H. Lin, T. Roughgarden,  E. Tardos, and A. Walkover. Braess's Paradox, Fibonacci Numbers, and Exponential Inapproximability. ICALP 2005.

  11. T. Roughgarden.  The Price of Anarchy is Independent of the Network Topology, Journal of Computer and System Sciences, 67(2) pp. 341--364, 2003.

  12. T. Roughgarden. Stackelberg Scheduling Strategies. SIAM Journal of Computing, 33(2), pp. 332--350.

  13. T. Roughgarden and E. Tardos. How Bad is Selfish Routing? Journal of the ACM, 49(2), pp. 236--259, March 2002.

   

• Michel Goemans
  
  

  "Approximation Algorithms"

  In this sequence of lectures, we will discuss the design and analysis of approximation algorithms guaranteed to deliver solutions within a certain degree of suboptimality for combinatorial optimization problems. We will describe general techniques to design them, including various rounding schemes for linear, convex or semidefinite programming relaxations, the use of local search methods, the use of integral characterizations and the embedding of finite metric spaces. We will also consider several different models, for example stochastic settings in which the realization of stochastic data gets revealed over time, incremental settings in which one needs to find a sequence of approximate solutions, or distributed settings in which players take decision selfishly. We will illustrate the methods on various combinatorial optimization problems.

  Bibliographic references

  1. Vijay Vazirani,  "Approximation Algorithms", Springer-Verlag, Berlin, 2001.

  2. Dorit S. Hochbaum, Editor, "Approximation Algorithms for NP-Hard Problems", PWS Publishing, 1997. 

  3. David B. Shmoys, "The design and analysis of approximation algorithms: Facility location as a case study". In: Trends in Optimization, AMS Proceedings of Symposia in Applied Mathematics 61, (S. Hosten, J. Lee, and R. Thomas, eds.), 2004, 85-97. Available for download at http://www.orie.cornell.edu/~shmoys/ams-survey.ps.

  4. Nati Linial, "Finite Metric Spaces - Combinatorics, Geometry and Algorithms", Proceedings of the International Congress of Mathematicians III, 573--586, Beijing, 2002. Available for download at http://www.cs.huji.ac.il/~nati/PAPERS/icm.ps.gz.

  5. Michel X. Goemans, "Semidefinite Programming in Combinatorial Optimization", Mathematical Programming, 79, 143--161, 1997.

  6. B. Dean, M.X. Goemans and J. Vondrak, "Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity", submitted to Mathematics of Operations Research. Available for download at http://www-math.mit.edu/~goemans/knapsack-journal.pdf

  7. Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, Maxim Sviridenko, "Tight approximation algorithms for maximum general assignment problems, Proceedings of the seventeenth annual ACM-SIAM Symposium on Discrete algorithms, 611--620, 2006.

  8. Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman, David P. Williamson, "A general approach for incremental approximation and hierarchical clustering",  Proceedings of the seventeenth annual ACM-SIAM Symposium on Discrete algorithms, 1147--1156, 2006.

   

• Yuri Kochetov  - lecture notes  1- 2-  3-  4-  5-
  
  

  "Facility location problems. Discrete models and local search methods"

  Discrete location theory is one of the dynamic areas of the operations research. We present the basic mathematical models in this field and their relationship and properties. Theory of PLS-complete problems, average case performance of the local improvement algorithm, and theory of fitness landscapes are reviewed. Also we present state-of-the-art methods based on the local search ideas and illustrate their behavior on difficult test instances. Finally, we discuss some open questions and promising directions for research.

  Bibliographic references

  1. E. Aarts,  J. K. Lenstra (eds.) Local Search in Combinatorial Optimization. Chichester: John Wiley & Sons, 1997.

  2. E. Angel, V. Zissimopoulos, On the classification of NP-complete problems in terms of their correlation coefficient. Discrete Applied Mathematics, 99,  261-277, 2000.

  3. F. Glover, M.Laguna, Tabu Search. Boston: Kluwer Acad. Publ. 1997.

  4. P. Hansen, N. Mladenovic. Variable neighborhood search: principles and applications. European J. Oper. Res., 130, 449-467, 2001.

  5. Yu. Kochetov, D. Ivanenko, Computationally difficult instances for the uncapacitated facility location problem. In: T. Ibaraki et al. (eds.) Metaheuristics: Progress as Real Solvers, Springer, 2005, 351-367.

  6. B. Korte, J. Vygen, Combinatorial Optimization: Theory and Algorithms. Springer, Third edition, 2006.

  7. T. Vredeveld, J.K. Lenstra, On local search for the generalized graph coloring problem, Operations Research Letters, 31 (4), 28-34, 2003.

   

• Bernhard Korte - Stephan Held - lecture notes 1- 2- 3-4- 5-
  
  

  "Making chips faster"

  In this series of lectures we will discuss how to minimize the cycle time of logic chips and microprocessors given already its physical realization by place and route. We basically use a minimum mean cycle approach. We also discuss how to generate a clocktree, i.e. to distribute the clock timing signals appropriately. By this approach one can reduce the cycle time in the range of 20%. To get such an improvement by faster technologies, one has to invest billions of dollars in new factories. Mathematical ideas need zero investment and gain the same.

  Bibliographic references

  1. Korte, B. and Vygen, J. Combinatorial Optimization: Theory and Algorithms. Springer, Berlin, 2006. (2nd ed. 2002, 1st ed. 2000, japanese ed. 2005).

  2. Held, S., Korte, B., Massberg, J., Ringe, M., and Vygen, J. Clock scheduling and clocktree construction for high performance asics. In Proceedings of the International Conference on Computer-Aided Design (2003), IEEE, pp. 232-239.

  3. Albrecht, C., Korte, B., Schietke, J., and Vygen, J. Maximum mean weight cycle in a digraph and minimizing cycle time of a logic chip. Discrete Applied Mathematics 123 (2002), 103-127.

  4. Albrecht, C., Korte, B., Schietke, J., and Vygen, J. Cycle time and slack optimization for VLSI-chips. Proceedings IEEE/ACM International Conference on Computer-Aided Design (1999), 232-238.

   

• Gleb Koshevoy
  
  

  "Discrete convexity and its applications in combinatorics and combinatorial optimization"

  We will explain what sets and functions on the lattice of all integer vectors in the n-dimensional space can be called convex. Contrary to the usual convexity in a vector space there is no a unique theory of convexity in the lattice of integers. Namely, there are many classes of subsets for which the separation theorem holds true. We present a classification of maximal classes (which do not possess any extension), which is done by using pure system, a generalization of unimodular. The so-called polymatroidal discretely concave functions, the most widespread among applications, are related to a certain unimodular system. Such functions naturally appear in mathematical economics, play an imporant role for solution the Horn problem, for describing submodule invariants over rings with discrete valuation, in Gelfand-Tzeitlin patterns and so on. Combinatorial algorithms for other systems will be explained and discussed (some of them are open problems).

  Bibliographic references

  1. V. Danilov,G.Koshevoy, Discrete Convexity and Unimodularity. I. Advances in Mathematics 189 (2004), 301-324.

  2. V. Danilov,G.Koshevoy, Discrete convexity and Hermitian matrices. Proc. V. A. Steklov Inst. Math.; Vol. 241 (2003), 68-90  (English translation in Proc. Steklov Inst. Math. 2003, no. 2 (241), 58-78

  3.  V. Danilov,G.Koshevoy, and C.Lang, Gross substitution, Discrete convexity, and Submodularity, Discrete and Applied Mathematics, 131:2 (2003), 283-298 4.

  4. V.Danilov,G.Koshevoy, and C.Lang, Substitutes and complements in two-sided market models,  Advances in Economic Theory (ed. M. Sertel and S.Koray), Springer-Verlag, Berlin (2003), 105-123.  

  5. V. Danilov,G.Koshevoy, and K.Murota,Discrete convexity and equilibria in economies with  indivisible goods and money, Math.Soc.Sci. 41 (2001), 251 -273.

  6. S. Fujishige: Submodular Functions and Optimization, Second Edition, Annals of Discrete Mathematics 58, Elsevier, Amsterdam, 2005.

  7. K. Murota K., Discrete convex analysis, SIAM Monography Series, 2003.

  8. R.T. Rockafellar,Convex analysis,Princeton University Press,Princeton,1970.

  9. A. Schrijver,Theory of Linear and Integer Programming,Wiley,Chichester,1986

   

• Shmuel Onn - lecture notes
  
  

  " Convex Discrete Optimization" 

  In this lecture series we introduce and study the convex combinatorial optimization problem and the convex integer programming problem, which are broad generalizations of their respective standard linear counterparts. We develop and use several tools form polyhedral geometry and algebra, some very recent, and combine them to obtain a strongly polynomial oracle-time algorithm for convex combinatorial optimization over any edge-well-behaved family, and a polynomial time algorithm for convex integer programming over any n-fold system. We discuss some of the many applications of our work, including to matroids, packing problems, partitioning problems, clustering, multiway transportation problems, and Grobner bases. Our work opens up new broad lines of research, such as the classification of edge-well-behaved families and the study of various relaxations, bounds, and approximations.

  Bibliographic references

  1. Gritzmann, P., Sturmfels, B.: Minkowski addition of polytopes : Complexity and applications to Grobner bases. SIAM J. Disc. Math. 6 (1993) 246—269.

  2. Onn, S., Schulman, L.J., The vector partition problem for convex objective functions. Math. Oper. Res. 26 (2001) 583—590.

  3. Schulz, A., Weismantel, R.: The complexity of generic primal algorithms for solving general integral programs. Math. Oper. Res. 27 (2002) 681—692

  4. Santos, F., Sturmfels, B.: Higher Lawrence configurations. J. Comb. Theory Ser. A 103 (2003) 151—164.

  5. Babson, E., Onn, S., Thomas, R.: The Hilbert zonotope and a polynomial time algorithm for universal Grobner bases. Adv. App. Math. 30 (2003) 529—544.

  6. Onn, S.: Convex matroid optimization. SIAM J. Disc. Math. 17 (2003) 249—253.

  7. De Loera, J., Onn, S.: All rational polytopes are transportation polytopes and all polytopal integer sets are contingency tables. Proc. 10th Ann. Math. Prog. Soc. Symp. Integ. Prog. Combin. Optim., (Columbia University, New York), Lec. Not. Comp. Sci., Springer, New York, 3064 (2004) 338—351.

  8. Onn, S., Rothblum, U.: Convex combinatorial optimization. Disc. Comp. Geom. 32 (2004) 549—566.

  9. De Loera, J., Hemmecke, R., Onn, S., Weismantel, R.: N-fold integer programming. Submitted.

  10. Convex integer programming. In preparation.

   

• Dieter Rautenbach - lecture notes: 1-  2-  3-  4-
  
  

  "Optimization and timing in VLSI design"

  The timing behaviour of a chip is a delicate matter and leads to some of the most challenging optimization problems that arise in VLSI design. We will discuss algorithms that either improve directly on the timing of a chip or improve on other aspects of a design such as placement or power consumption respecting the constraints imposed by the targeted timing. Among other things we will show how to restructure the logic of the chip in order to speed up specific signals and how to size all individual gates simultanoeusly and optimally to reduce their power consumption. The presented methods use discrete as well as continuous models.

  Bibliographic references

  1. Wegener, The complexity of Boolean functions, Wiley-Teubner Series in Computer Science. Stuttgart: B. G. Teubner;  Chichester etc.: John Wiley & Sons., 1987.

  2. J.E. Savage, Models of computation: exploring the power of computing, Reading, MA: Addison Wesley Longman, 1998.

  3. M. Minoux, Mathematical Programming: Theory and Algorithms, John Wiley & Sons, Chichester, England, 1986.

  4. R.E. Ladner and M.J. Fischer, Parallel prefix computation,  J. Assoc. Comput. Mach. 27 (1980), 831-838.

  5. R.B. Hitchcock, Timing Verification and the Timing Analysis Program, in Proc. 19th IEEE Design Automation Conference, 1982, 594-604.

  6. C.-P. Chen, C.C.N. Chu and D.F. Wong, Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation, in: Proceedings of the 1998 IEEE/ACM International Conference on Computer-aided Design, 1998, 617-624.

  7. W.-C. Yeh, C.-W. Jen, Generalized earliest-first fast addition algorithm, IEEE Trans. Computers, 52 (2003), 1233-1242.

  8. D. Rautenbach, C. Szegedy und J. Werber, Delay Optimization of Linear Depth Boolean Circuits with Prescribed Input Arrival Times, to appear in Journal of Discrete Algorithms.

   

• Najiba Sbihi
  
  

  "Mathematics of supply chain management"

  Supply chain management covers issues such as supply chain design; production, inventory, and transportation coordination; vehicle routing problems. This tutorial will provide an overview of the operations research models that are used in decision support systems for supply chain management. It will present the underlying mathematical tools. An industrial case and its solution method will be studied in detail.

  Bibliographic references

  1. V. Agrawal , X. Chao , S. Seshadri, Dynamic balancing of inventory in supply chains, European Journal of Operations research 159 (2004) 296–317.

  2. S. Chopra and P. Meindl, Supply Chain Management, Pearson Education International (2004).

  3. Daskin, M. S., L. V. Snyder, and R. T. Berger, Facility location in supply chain design, In "Logistics Systems: Design and Operation," A. Langevin and D. Riopel (eds.), Kluwer, 2005.

  4. S. David Wu & Hakan Golbasi, Multi-item, multi-facility supply chain planning: models, complexities and algorithms, Computational Optimization and Applications 28(2004) 325-356.

  5. A.G. De Kok and S.C. Graves (editors), Supply Chain Management: Design, Coordination and Operation, Elsevier (2003).

  6. L. Ozdamar, G. Barbarosoglu,  An integrated Lagrangean relaxation-simulated annealing approach to the multi-level multi-item capacitated lot sizing problem, Int. J. Production Economics 68 (2000) 319-331.

  7. H. Pirkul and V. Jayaraman, Planning and coordination of production and distribution facilities for multiple commodities, European Journal of Operations research 133 (2001) 394-408.

  8. D. Simchi-Levi, P. Kaminsky, and E. Simchi-Levi, Designing and Managing the Supply Chain, McGraw-Hill/Irwin (2002).

  9. T. Miller, Hierarchical operations and supply chain planning, Springer (2002).

  10. C. P. M. Van Hoesel and A. P. M. Wagelmans, Fully polynomial approximation schemes for single-item capacitated economic lot-sizing problem, Mathematics of Operations Research 26 (2001) 339-357.

   

• Jens Vygen - lecture notes
  
  

  "Combinatorial optimization in VLSI placement and routing"

  We discuss state-of-the-art algorithms for the classical problems in VLSI layout. Many techniques from combinatorial optimization, like minimum cost flows, Steiner trees, shortest paths and multicommodity flows appear as subproblems, but also more general problems have to be solved. All algorithms must be fast enough to deal with current and future orders of magnitude: approximately one billion transistors and ten million Steiner trees in graphs with several hundred billion vertices.

  Bibliographic references

  1. B. Korte, J. Vygen. Combinatorial Optimization: Theory and Algorithms. Springer, third edition 2006.

  2. J. Vygen. New Theoretical Results on Quadratic Placement. To appear in "Integration, the VLSI Journal".

  3. U. Brenner, J. Vygen. Worst-Case Ratios of Networks in the Rectilinear Plane. Networks 38 (2001), 126-139.

  4. J. Vygen. Algorithms for Large-Scale Flat Placement. Proceedings of the 34th Design Automation Conference, ACM 1997, 746-751.

  5. J. Vygen.Geometric quadrisection in linear time, with application to VLSI placement. Discrete Optimization 2 (2005), 362-390.

  6. U. Brenner, M. Struzyna. Faster and Better Global Placement By a New Transportation Algorithm. Proceedings of the 42nd Design Automation Conference, ACM 2005, 591-596.

  7. U. Brenner, J. Vygen. Legalizing a Placement with Minimum Total Movement. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 23 (2004), 1597-1613.

  8. A. Hetzel. A Sequential Detailed Router for Huge Grid Graphs. Design, Automation and Test in Europe, Proceedings, IEEE 1998, 332-338.

  9. C. Albrecht. Global Routing by New Approximation Algorithms for Multicommodity Flow. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems 20 (2001), 622-632.

  10. J. Vygen. Near-Optimum Global Routing with Coupling, Delay Bounds, and Power Consumption. In: Integer Programming and Combinatorial Optimization; Proceedings of the 10th International IPCO Conference;  LNCS 3064 (G. Nemhauser, D. Bienstock, eds.), Springer, Berlin 2004, pp. 308-324.

   

   

|  Back to Information |  Application  | SMS Home Page | 

© Université de Montréal