The Support of Integer Optimal Solutions

DOI10.1137/17M1162792zbMath1402.90091arXiv1712.08923OpenAlexW2963139252WikidataQ129432051 ScholiaQ129432051MaRDI QIDQ4577743

Timm Oertel, Friedrich Eisenbrand, Robert Weismantel, Jesús A. De Loera, Iskander M. Aliev

Publication date: 3 August 2018

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

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

zbMATH Keywords

support functioninteger linear programparse solution

Mathematics Subject Classification ID

Integer programming (90C10) Optimality conditions and duality in mathematical programming (90C46) Lattices and convex bodies (number-theoretic aspects) (11H06)

Related Items

Optimizing Sparsity over Lattices and Semigroups, On lattice point counting in \(\varDelta\)-modular polyhedra, On Lattice Width of Lattice-Free Polyhedra and Height of Hilbert Bases, On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems, The Distributions of Functions Related to Parametric Integer Optimization, Distance-Sparsity Transference for Vertices of Corner Polyhedra, One-variable logic meets Presburger arithmetic, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, Sparse representation of vectors in lattices and semigroups

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Huge tables and multicommodity flows are fixed-parameter tractable via unimodular integer Carathéodory
• On Siegel's lemma
• An integer analogue of Carathéodory's theorem
• On integer points in polyhedra
• Carathéodory bounds for integer cones
• Integer Programming with a Fixed Number of Variables
• Towards Efficient Satisfiability Checking for Boolean Algebra with Presburger Arithmetic
• Polynomiality for Bin Packing with a Constant Number of Item Types
• An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables
• Sparse Solutions of Linear Diophantine Equations
• Two-Variable First-Order Logic with Equivalence Closure