Convex integer maximization via Graver bases

DOI10.1016/J.JPAA.2008.11.033MaRDI QIDQ1017675zbMATH OpenOpenAlexFDO

Authors Jesús A. De Loera, Raymond Hemmecke, Shmuel Onn, Uriel G. Rothblum, Robert Weismantel

Publication date 12 May 2009

Published in Journal of Pure and Applied Algebra (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0609019

zbMATH Keywords

polynomial time algorithmsalgebraic algorithmic scheme

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial aspects of partitions of integers (05A17)

Abstract: We present a new algebraic algorithmic scheme to solve {em convex integer maximization} problems of the following form, where $c$ is a convex function on $R^d$ and $w_{1}x,\mathrm{...},w_{d}x$ are linear forms on $R^n$, ${\displaystyle }$max {c(w_1 x,...,w_d x): Ax=b, xin N^n} .${\displaystyle }$ This method works for arbitrary input data $A,b,d,w_1,\mathrm{...},w_d,c$. Moreover, for fixed $d$ and several important classes of programs in {em variable dimension}, we prove that our algorithm runs in {em 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.

Recommendations

• Graver basis and proximity techniques for block-structured separable convex integer minimization problems
• scientific article; zbMATH DE number 4209913
• Integer optimization on convex semialgebraic sets
• scientific article; zbMATH DE number 826948
• Integer convex minimization by mixed integer linear optimization
• scientific article; zbMATH DE number 4043617
• Convex integer optimization by constantly many linear counterparts
• The quadratic Graver cone, quadratic integer minimization, and extensions
• On Convex Minimization over Base Polytopes
• On boundedness of (quasi-)convex integer optimization problems

Cites work

• scientific article; zbMATH DE number 5379591 (Why is no real title available?)
• scientific article; zbMATH DE number 3828715 (Why is no real title available?)
• scientific article; zbMATH DE number 714526 (Why is no real title available?)
• scientific article; zbMATH DE number 2087727 (Why is no real title available?)
• A Polynomial Time Algorithm for Shaped Partition Problems
• A finiteness theorem for Markov bases of hierarchical models
• All Linear and Integer Programs Are Slim 3‐Way Transportation Programs
• An adaptive algorithm for vector partitioning
• Approximation algorithms for multi-index transportation problems with decomposable costs
• Conditions for the existence of solutions of the three-dimensional planar transportation problem
• Convex combinatorial optimization
• Encyclopedia of optimization. In 6 vols.
• Higher Lawrence configurations.
• Markov bases of three-way tables are arbitrarily complicated
• Minimal Basis for a Connected Markov Chain over 3 x 3 x K Contingency Tables with Fixed Two-Dimensional Marginals
• Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases
• On clustering problems with connected optima in Euclidean spaces
• On properties of multi-dimensional statistical tables
• On the foundations of linear and integer linear programming I
• On the positive sums property and the computation of Graver test sets
• Optimal partitions having disjoint convex and conic hulls
• Signature classes of transportation polytopes
• Some complexity results for polynomial ideals
• The Complexity of Three-Way Statistical Tables
• The Graver complexity of integer programming
• The vector partition problem for convex objective functions.
• Variation of cost functions in integer programming
• \(N\)-fold integer programming

Cited in

(10)

• Efficient edge-skeleton computation for polytopes defined by oracles
• Convex integer optimization by constantly many linear counterparts
• Graver basis and proximity techniques for block-structured separable convex integer minimization problems
• \(N\)-fold integer programming and nonlinear multi-transshipment
• Efficient solutions for weight-balanced partitioning problems
• The quadratic Graver cone, quadratic integer minimization, and extensions
• \(n\)-fold integer programming in cubic time
• Convex discrete optimization
• The power of pyramid decomposition in Normaliz
• Minimizing a Low-Dimensional Convex Function Over a High-Dimensional Cube

Describes a project that uses

Uses Software

• 4ti2

This page was built for publication: Convex integer maximization via Graver bases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1017675)