Convex integer optimization by constantly many linear counterparts

DOI10.1016/J.LAA.2014.01.007zbMATH Open1297.90087arXiv1208.5639OpenAlexW2963590392MaRDI QIDQ2451653FDOQ2451653

Authors: Michal Melamed, Shmuel Onn 

Publication date: 4 June 2014

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

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.

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

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

zbMATH Keywords

combinatorial optimizationprojectioninteger programmingmatroidtransportation problemstatistical table

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Higher Lawrence configurations.
• 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 finiteness theorem for Markov bases of hierarchical models
• \(N\)-fold integer programming
• Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases
• All Linear and Integer Programs Are Slim 3‐Way Transportation Programs
• Nonlinear discrete optimization. An algorithmic theory
• Convex combinatorial optimization
• 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
• Maximizing Classes of Two-Parameter Objectives Over Matroids
• Convex integer maximization via Graver bases
• A Polynomial Time Algorithm for Shaped Partition Problems
• Parametric nonlinear discrete optimization over well-described sets and matroid intersections
• Nonlinear Matroid Optimization and Experimental Design
• A polynomial-time algorithm for optimizing over \(N\)-fold 4-block decomposable integer programs

Cited In (5)

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

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)