Convex integer optimization by constantly many linear counterparts

DOI10.1016/J.LAA.2014.01.007MaRDI QIDQ2451653zbMATH OpenOpenAlexFDO

Authors Michal Melamed, Shmuel Onn

Publication date 4 June 2014

Published in Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial optimizationinteger programmingmatroidprojectionstatistical tabletransportation problem

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27)

Abstract: In this article we study convex integer maximization problems with composite objective functions of the form $f(Wx)$, where $f$ is a convex function on $R^d$ and $W$ is a $dimesn$ matrix with small or binary entries, over finite sets $$ of integer points presented by an oracle or by linear inequalities. Continuing the line of research advanced by Uri Rothblum and his colleagues on edge-directions, we introduce here the notion of {em edge complexity} of $S$, and use it to establish polynomial and constant upper bounds on the number of vertices of the projection $conv(WS)$ and on the number of linear optimization counterparts needed to solve the above convex problem. Two typical consequences are the following. First, for any $d$, there is a constant $m(d)$ such that the maximum number of vertices of the projection of any matroid $Ssubset{0,1}^n$ by any binary $dimesn$ matrix $W$ is $m(d)$ regardless of $n$ and $S$; and the convex matroid problem reduces to $m(d)$ greedily solvable linear counterparts. In particular, $m(2)=8$. Second, for any $d,l,m$, there is a constant $t(d;l,m)$ such that the maximum number of vertices of the projection of any three-index $limesmimesn$ transportation polytope for any $n$ by any binary $dimes(limesmimesn)$ matrix $W$ is $t(d;l,m)$; and the convex three-index transportation problem reduces to $t(d;l,m)$ linear counterparts solvable in polynomial time.

Recommendations

• Convex integer maximization via Graver bases
• Convex discrete optimization
• Integer convex minimization by mixed integer linear optimization
• Cones of Matrices and Set-Functions and 0–1 Optimization
• scientific article; zbMATH DE number 16720

Cites work

• \(N\)-fold integer programming
• A finiteness theorem for Markov bases of hierarchical models
• A lower bound for the Graver complexity of the incidence matrix of a complete bipartite graph
• A polynomial oracle-time algorithm for convex integer minimization
• A Polynomial Time Algorithm for Shaped Partition Problems
• A polynomial-time algorithm for optimizing over N-fold 4-block decomposable integer programs
• All Linear and Integer Programs Are Slim 3‐Way Transportation Programs
• Convex combinatorial optimization
• Convex integer maximization via Graver bases
• Higher Lawrence configurations.
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• Maximizing Classes of Two-Parameter Objectives Over Matroids
• 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
• Nonlinear discrete optimization. An algorithmic theory
• Nonlinear Matroid Optimization and Experimental Design
• Optimal partitions having disjoint convex and conic hulls
• Parametric nonlinear discrete optimization over well-described sets and matroid intersections

Cited in

(5)

• Convex integer maximization via Graver bases
• The relationship between integer and real solutions of constrained convex programming
• The vertices of primitive zonotopes
• Primitive zonotopes
• A linear optimization oracle for zonotope computation

This page was built for publication: Convex integer optimization by constantly many linear counterparts

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