[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Convex Discrete Optimization

  • Reference work entry
Encyclopedia of Optimization

Introduction

The general linear discrete optimization problem can be posed as follows.

Linear discrete optimization. Given a set \( S\subseteq\mathbb{Z}^n \) of integer points and an integer vector \( w\in\mathbb{Z}^n \), find an \( x\in S \) maximizing the standard inner product \( wx:=\sum_{i=1}^nw_ix_i \).

The algorithmic complexity of this problem, which includes integer programming and combinatorial optimization as special cases, depends on the presentation of the set S of feasible points. In integer programming, this set is presented as the set of integer points satisfying a given system of linear inequalities, which in standard form is given by

$$ S\quad=\quad\{x\in\mathbb{N}^n:\ Ax=b\}\;, $$

where ℕ stands for the nonnegative integers, \( A\in\mathbb{Z}^{m\times n} \) is an \( m\times n \) integer matrix, and \( b\in\mathbb{Z}^m \) is an integer vector. The input for the problem then consists of \( A,b,w \). In combinatorial optimization, \( S\subseteq\{0,1\}^n \) is a set of \(...

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 1,529.50
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
GBP 2,028.40
Price includes VAT (United Kingdom)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Aho AV, Hopcroft JE, Ullman JD (1975) The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading

    Google Scholar 

  2. Allemand K, Fukuda K, Liebling TM, Steiner E (2001) A polynomial case of unconstrained zero-one quadratic optimization. Math Prog Ser A 91:49–52

    MATH  MathSciNet  Google Scholar 

  3. Alon N, Onn S (1999) Separable partitions. Discret Appl Math 91:39–51

    Article  MATH  MathSciNet  Google Scholar 

  4. Aoki S, Takemura A (2003) Minimal basis for connected Markov chain over 3 × 3 × K contingency tables with fixed two-dimensional marginals. Austr New Zeal J Stat 45:229–249

    Article  MATH  MathSciNet  Google Scholar 

  5. Babson E, Onn S, Thomas R (2003) The Hilbert zonotope and a polynomial time algorithm for universal Gröbner bases. Adv Appl Math 30:529–544

    Article  MATH  MathSciNet  Google Scholar 

  6. Balinski ML, Rispoli FJ (1993) Signature classes of transportation polytopes. Math Prog Ser A 60:127–144

    Article  MathSciNet  Google Scholar 

  7. Barnes ER, Hoffman AJ, Rothblum UG (1992) Optimal partitions having disjoint convex and conic hulls. Math Prog 54:69–86

    Article  MATH  MathSciNet  Google Scholar 

  8. Berstein Y, Onn S: Nonlinear bipartite matching. Disc Optim (to appear)

    Google Scholar 

  9. Boros E, Hammer PL (1989) On clustering problems with connected optima in Euclidean spaces. Discret Math 75:81–88

    Article  MATH  MathSciNet  Google Scholar 

  10. Chvátal V (1973) Edmonds polytopes and a hierarchy of combinatorial problems. Discret Math 4:305–337

    Article  MATH  Google Scholar 

  11. Cox LH (2003) On properties of multi-dimensional statistical tables. J Stat Plan Infer 117:251–273

    Article  MATH  Google Scholar 

  12. De Loera J, Hemmecke R, Onn S, Rothblum UG, Weismantel R: Integer convex maximization via Graver bases. E‑print: arXiv:math.CO/0609019. (submitted)

    Google Scholar 

  13. De Loera J, Hemmecke R, Onn S, Weismantel R: N-fold integer programming. Disc Optim (to appear)

    Google Scholar 

  14. De Loera J, Onn S (2004) All rational polytopes are transportation polytopes and all polytopal integer sets are contingency tables. In: Proc IPCO 10 – Symp on Integer Programming and Combinatoral Optimization, Columbia University, New York. Lec Not Comp Sci. Springer, 3064, pp 338–351

    Google Scholar 

  15. De Loera J, Onn S (2004) The complexity of three-way statistical tables. SIAM J Comput 33:819–836

    Article  MATH  MathSciNet  Google Scholar 

  16. De Loera J, Onn S (2006) All linear and integer programs are slim 3‑way transportation programs. SIAM J Optim 17:806–821

    Article  MATH  MathSciNet  Google Scholar 

  17. De Loera J, Onn S (2006) Markov bases of three-way tables are arbitrarily complicated. J Symb Comput 41:173–181

    Article  MATH  Google Scholar 

  18. Domingo-Ferrer J, Torra V (eds) (2004) Privacy in Statistical Databases. Proc. PSD 2004 – Int Symp Privacy in Statistical Databases, Barcelona, Spain. Lec Not Comp Sci. Springer, 3050

    Google Scholar 

  19. Doyle P, Lane J, Theeuwes J, Zayatz L (eds) (2001) Confidentiality, Disclosure and Data Access: Theory and Practical Applications for Statistical Agencies. North-Holland, Amsterdam

    Google Scholar 

  20. Edelsbrunner H, O'Rourke J, Seidel R (1986) Constructing arrangements of lines and hyperplanes with applications. SIAM J Comput 15:341–363

    Article  MATH  MathSciNet  Google Scholar 

  21. Edelsbrunner H, Seidel R, Sharir M (1991) On the zone theorem for hyperplane arrangements. In: New Results and Trends in Computer Science. Lec Not Comp Sci. Springer, 555, pp 108–123

    Google Scholar 

  22. Edmonds J (1971) Matroids and the greedy algorithm. Math Prog 1:127–136

    Article  MATH  MathSciNet  Google Scholar 

  23. Edmonds J, Karp RM (1972) Theoretical improvements in algorithmic efficiency of network flow problems. J Ass Comput Mach 19:248–264

    MATH  Google Scholar 

  24. Frank A, Tardos E (1987) An application of simultaneous Diophantine approximation in combinatorial optimization. Combinatorica 7:49–65

    Article  MATH  MathSciNet  Google Scholar 

  25. Fukuda K, Onn S, Rosta V (2003) An adaptive algorithm for vector partitioning. J Global Optim 25:305–319

    Article  MATH  MathSciNet  Google Scholar 

  26. Garey MR, Johnson DS (1979) Computers and Intractability. Freeman, San Francisco

    MATH  Google Scholar 

  27. Gilmore PC, Gomory RE (1961) A linear programming approach to the cutting-stock problem. Oper Res 9:849–859

    MATH  MathSciNet  Google Scholar 

  28. Graver JE (1975) On the foundation of linear and integer programming I. Math Prog 9:207–226

    Article  MATH  MathSciNet  Google Scholar 

  29. Gritzmann P, Sturmfels B (1993) Minkowski addition of polytopes: complexity and applications to Gröbner bases. SIAM J Discret Math 6:246–269

    Article  MATH  MathSciNet  Google Scholar 

  30. Grötschel M, Lovász L (1995) Combinatorial optimization. In: Handbook of Combinatorics. North-Holland, Amsterdam, pp 1541–1597

    Google Scholar 

  31. Grötschel M, Lovász L, Schrijver A (1993) Geometric Algorithms and Combinatorial Optimization, 2nd edn. Springer, Berlin

    MATH  Google Scholar 

  32. Grünbaum B (2003) Convex Polytopes, 2nd edn. Springer, New York

    Google Scholar 

  33. Harding EF (1967) The number of partitions of a set of n points in k dimensions induced by hyperplanes. Proc Edinburgh Math Soc 15:285–289

    MATH  MathSciNet  Google Scholar 

  34. Hassin R, Tamir A (1989) Maximizing classes of two-parameter objectives over matroids. Math Oper Res 14:362–375

    MATH  MathSciNet  Google Scholar 

  35. Hemmecke R (2003) On the positive sum property and the computation of Graver test sets. Math Prog 96:247–269

    Article  MATH  MathSciNet  Google Scholar 

  36. Hemmecke R, Hemmecke R, Malkin P (2005) 4ti2 Version 1.2–Computation of Hilbert bases, Graver bases, toric Gröbner bases, and more. http://www.4ti2.de/. Accessed Sept 2005

  37. Hoffman AJ, Kruskal JB (1956) Integral boundary points of convex polyhedra. In: Linear inequalities and Related Systems, Ann Math Stud 38. Princeton University Press, Princeton, pp 223–246

    Google Scholar 

  38. Hoşten S, Sullivant S (2007) A finiteness theorem for Markov bases of hierarchical models. J Comb Theory Ser A 114:311–321

    Article  MATH  Google Scholar 

  39. Hwang FK, Onn S, Rothblum UG (1999) A polynomial time algorithm for shaped partition problems. SIAM J Optim 10:70–81

    Article  MATH  MathSciNet  Google Scholar 

  40. Khachiyan LG (1979) A polynomial algorithm in linear programming. Sov Math Dok 20:191–194

    MATH  Google Scholar 

  41. Klee V, Kleinschmidt P (1987) The d-step conjecture and its relatives. Math Oper Res 12:718–755

    MATH  MathSciNet  Google Scholar 

  42. Klee V, Witzgall C (1968) Facets and vertices of transportation polytopes. In: Mathematics of the Decision Sciences, Part I, Stanford, CA, 1967. AMS, Providence, pp 257–282

    Google Scholar 

  43. Kleinschmidt P, Lee CW, Schannath H (1987) Transportation problems which can be solved by the use of Hirsch-paths for the dual problems. Math Prog 37:153–168

    Article  MATH  MathSciNet  Google Scholar 

  44. Lenstra AK, Lenstra HW Jr, Lovász L (1982) Factoring polynomials with rational coefficients. Math Ann 261:515–534

    Article  MATH  MathSciNet  Google Scholar 

  45. Lovàsz L (1986) An Algorithmic Theory of Numbers, Graphs, and Convexity. CBMS-NSF Ser App Math, SIAM 50:iv+91

    Google Scholar 

  46. Onn S (2006) Convex discrete optimization. Lecture Series, Le Séminaire de Mathématiques Supérieures, Combinatorial Optimization: Methods and Applications, Université de Montréal, Canada, June 2006. http://ie.technion.ac.il/~onn/Talks/Lecture_Series.pdf and at http://www.dms.umontreal.ca/sms/ONN_Lecture_Series.pdf. Accessed 19–30 June 2006

  47. Onn S (2003) Convex matroid optimization. SIAM J Discret Math 17:249–253

    Article  MATH  MathSciNet  Google Scholar 

  48. Onn S (2006) Entry uniqueness in margined tables. In: Proc. PSD 2006 – Symp. on Privacy in Statistical Databases, Rome, Italy. Lec Not Comp Sci. Springer, 4302, pp 94–101

    Google Scholar 

  49. Onn S, Rothblum UG (2004) Convex combinatorial optimization. Disc Comp Geom 32:549–566

    Article  MATH  MathSciNet  Google Scholar 

  50. Onn S, Schulman LJ (2001) The vector partition problem for convex objective functions. Math Oper Res 26:583–590

    Article  MATH  MathSciNet  Google Scholar 

  51. Onn S, Sturmfels B (1999) Cutting Corners. Adv Appl Math 23:29–48

    Article  MATH  MathSciNet  Google Scholar 

  52. Pistone G, Riccomagno EM, Wynn HP (2001) Algebraic Statistics. Chapman and Hall, London

    MATH  Google Scholar 

  53. Queyranne M, Spieksma FCR (1997) Approximation algorithms for multi-index transportation problems with decomposable costs. Disc Appl Math 76:239–253

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

    MATH  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  57. Schulz A, Weismantel R, Ziegler GM (1995) \( (0,1) \)-integer programming: optimization and augmentation are equivalent. In: Proc 3rd Ann Euro Symp Alg. Lec Not Comp Sci. Springer, 979, pp 473–483

    Google Scholar 

  58. Sturmfels B (1996) Gröbner Bases and Convex Polytopes. Univ Lec Ser 8. AMS, Providence

    Google Scholar 

  59. Tardos E (1986) A strongly polynomial algorithm to solve combinatorial linear programs. Oper Res 34:250–256

    MATH  MathSciNet  Google Scholar 

  60. Vlach M (1986) Conditions for the existence of solutions of the three-dimensional planar transportation problem. Discret Appl Math 13:61–78

    Article  MATH  MathSciNet  Google Scholar 

  61. Wallacher C, Zimmermann U (1992) A combinatorial interior point method for network flow problems. Math Prog 56:321–335

    Article  MathSciNet  Google Scholar 

  62. Yemelichev VA, Kovalev MM, Kravtsov MK (1984) Polytopes, Graphs and Optimisation. Cambridge University Press, Cambridge

    MATH  Google Scholar 

  63. Yudin DB, Nemirovskii AS (1977) Informational complexity and efficient methods for the solution of convex extremal problems. Matekon 13:25–45

    Google Scholar 

  64. Zaslavsky T (1975) Facing up to arrangements: face count formulas for partitions of space by hyperplanes. Memoirs Amer Math Soc 154:vii+102

    Google Scholar 

  65. Ziegler GM (1995) Lectures on Polytopes. Springer, New York

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Technion – Israel Institute of Technology, Haifa, Israel

    Shmuel Onn

Authors
  1. Shmuel Onn
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Chemical Engineering, Princeton University, Princeton, NJ, 08544-5263, USA

    Christodoulos A. Floudas

  2. Center for Applied Optimization, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL, 32611-6595, USA

    Panos M. Pardalos

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag

About this entry

Cite this entry

Onn, S. (2008). Convex Discrete Optimization . In: Floudas, C., Pardalos, P. (eds) Encyclopedia of Optimization. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-74759-0_94

Download citation

Publish with us

Policies and ethics

Search

Navigation