×

zbMATH — the first resource for mathematics

Convex integer maximization via Graver bases. (English) Zbl 1284.05026
Summary: We present a new algebraic algorithmic scheme to solve convex integer maximization problems of the following form, where \(c\) is a convex function on \(\mathbb R^d\) and \(w_{1}x,\dots ,w_dx\) are linear forms on \(\mathbb R^n\), \[ \max\{c(w_1x,\dots , w_dx): Ax = b, x \in \mathbb N^n\}. \] This method works for arbitrary input data \(A,b,d,w_{1},\dots ,w_{d},c\). Moreover, for fixed \(d\) and several important classes of programs in variable dimension, we prove that our algorithm runs in polynomial time. As a consequence, we obtain polynomial time algorithms for various types of multi-way transportation problems, packing problems, and partitioning problems in variable dimension.

MSC:
05A17 Combinatorial aspects of partitions of integers
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Software:
4ti2
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] D. Bertisimas, R. Weismantel, Optimization over integers, Dynamic Ideas, 2005
[2] Thomas, R.R., Algebraic methods in integer programming, ()
[3] Mayr, E.W, Some complexity results for polynomial ideals, J. complex., 13, 303-325, (1997) · Zbl 1033.12008
[4] Sturmfels, B., Gröbner bases and convex polytopes, (1995), American Mathematical Soc. Providence, RI
[5] Onn, S.; Rothblum, U.G., Convex combinatorial optimization, Disc. comp. geom., 32, 549-566, (2004) · Zbl 1179.90289
[6] De Loera, J.A.; Hemmecke, R.; Onn, S.; Weismantel, R., \(N\)-fold integer programming, Discrete optim., 5, 231-241, (2008) · Zbl 1151.90025
[7] De Loera, J.A.; Onn, S., The complexity of three-way statistical tables, SIAM J. comput., 33, 819-836, (2004) · Zbl 1101.68996
[8] De Loera, J.A; Onn, S., All linear and integer programs are slim 3-way transportation programs, SIAM J. optim., 17, 806-821, (2006) · Zbl 1128.90041
[9] De Loera, J.A; Onn, S., Markov bases of three-way tables are arbitrarily complicated, J. symbolic comput., 41, 173-181, (2006) · Zbl 1120.62043
[10] Y. Berstein, S. Onn, The Graver complexity of integer programming, Ann. Combin. (in press) · Zbl 1231.90295
[11] Hoşten, S.; Sullivant, S., A finiteness theorem for Markov bases of hierarchical models, J. combin. theory ser. A, 114, 2, 311-321, (2007) · Zbl 1111.62053
[12] Santos, F.; Sturmfels, B., Higher Lawrence configurations, J. combin. theory ser. A, 103, 151-164, (2003) · Zbl 1036.52018
[13] Gritzmann, P.; Sturmfels, B., Minkowski addition of polytopes: complexity and applications to Gröbner bases, SIAM J. discrete math., 6, 246-269, (1993) · Zbl 0798.68157
[14] Onn, S.; Schulman, L.J., The vector partition problem for convex objective functions, Math. oper. res., 26, 583-590, (2001) · Zbl 1073.90535
[15] Graver, J.E., On the foundation of linear and integer programming I, Math. prog., 9, 207-226, (1975) · Zbl 0323.90035
[16] Hemmecke, R., On the positive sum property and the computation of graver test sets, Math. prog., 96, 247-269, (2003) · Zbl 1059.90108
[17] 4ti2 team: 4ti2-A software package for algebraic, geometric and combinatorial problems on linear spaces. Available at: www.4ti2.de
[18] Sturmfels, B.; Thomas, R.R, Variation of cost functions in integer programming, Math. program., 77, 357-387, (1997) · Zbl 0888.90125
[19] Hwang, F.K.; Onn, S.; Rothblum, U.G., A polynomial time algorithm for shaped partition problems, SIAM J. optim., 10, 70-81, (1999) · Zbl 0955.90118
[20] Aoki, S.; Takemura, A., Minimal basis for connected Markov chain over \(3 \times 3 \times K\) contingency tables with fixed two-dimensional marginals, Austr. new zeal. J. stat., 45, 229-249, (2003) · Zbl 1064.62068
[21] Balinski, M.L.; Rispoli, F.J., Signature classes of transportation polytopes, Math. prog. ser. A, 60, 127-144, (1993) · Zbl 0783.90078
[22] Cox, L.H., Bounds on entries in 3-dimensional contingency tables, (), 21-33 · Zbl 1051.68625
[23] Cox, L.H., On properties of multi-dimensional statistical tables, J. statist. planning inference, 117, 251-273, (2003) · Zbl 1021.62108
[24] Duncan, G.T; Fienberg, S.E.; Krishnan, R.; Padman, R.; Roehrig, S.F., Disclosure limitation methods and information loss for tabular data, ()
[25] Queyranne, M.; Spieksma, F.C.R., Approximation algorithms for multi-index transportation problems with decomposable costs, Discrete app. math., 76, 239-253, (1997) · Zbl 0883.90094
[26] Vlach, M., Conditions for the existence of solutions of the three-dimensional planar transportation problem, Discrete appl. math., 13, 61-78, (1986) · Zbl 0601.90105
[27] Yemelichev, V.A.; Kovalev, M.M.; Kravtsov, M.K., Polytopes, graphs and optimisation, (1984), Cambridge University Press Cambridge · Zbl 0523.52002
[28] Barnes, E.R.; Hoffman, A.J.; Rothblum, U.G., Optimal partitions having disjoint convex and conic hulls, Math. prog., 54, 69-86, (1992) · Zbl 0751.90068
[29] Boros, E.; Hammer, P.L., On clustering problems with connected optima in Euclidean spaces, Discrete math., 75, 81-88, (1989) · Zbl 0665.62062
[30] Fukuda, F.; Onn, S.; Rosta, V., An adaptive algorithm for vector partitioning, J. global optim., 25, 305-319, (2003) · Zbl 1047.90057
[31] F.K. Hwang, U.G. Rothblum, Partitions: Optimality and Clustering, World Scientific, London, (in preparation) · Zbl 1244.90003
[32] Pardalos, P.M.; Rendl, F.; Wolkowicz, H., The quadratic assignment problem: A survey and recent developments, (), 1-42 · Zbl 0817.90059
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.