Convex integer maximization via Graver bases

DOI10.1016/J.JPAA.2008.11.033zbMATH Open1284.05026arXivmath/0609019OpenAlexW2033948588MaRDI QIDQ1017675FDOQ1017675

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)

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.

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

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

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)

Cites Work

• Approximation algorithms for multi-index transportation problems with decomposable costs
• Higher Lawrence configurations.
• On the foundations of linear and integer linear programming I
• The Graver complexity of integer programming
• A finiteness theorem for Markov bases of hierarchical models
• \(N\)-fold integer programming
• Title not available (Why is that?)
• Signature classes of transportation polytopes
• Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases
• The Complexity of Three-Way Statistical Tables
• All Linear and Integer Programs Are Slim 3‐Way Transportation Programs
• Variation of cost functions in integer programming
• Encyclopedia of optimization. In 6 vols.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Convex combinatorial optimization
• 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
• Optimal partitions having disjoint convex and conic hulls
• On clustering problems with connected optima in Euclidean spaces
• The vector partition problem for convex objective functions.
• A Polynomial Time Algorithm for Shaped Partition Problems
• Some complexity results for polynomial ideals
• On the positive sums property and the computation of Graver test sets
• Conditions for the existence of solutions of the three-dimensional planar transportation problem
• On properties of multi-dimensional statistical tables
• An adaptive algorithm for vector partitioning
• Title not available (Why is that?)

Cited In (10)

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

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)