Exploiting symmetry in integer convex optimization using core points

DOI10.1016/J.ORL.2013.02.007MaRDI QIDQ2450624zbMATH OpenOpenAlexFDO

Authors Katrin Herr, Thomas Rehn, Achill Schürmann

Publication date 14 May 2014

Published in Operations Research Letters (Search for Journal in Brave)

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

zbMATH Keywords

symmetryinteger linear programscore setcore pointinteger convex optimization

Mathematics Subject Classification ID

Convex programming (90C25) Integer programming (90C10)

Abstract: We consider convex programming problems with integrality constraints that are invariant under a linear symmetry group. To decompose such problems we introduce the new concept of core points, i.e., integral points whose orbit polytopes are lattice-free. For symmetric integer linear programs we describe two algorithms based on this decomposition. Using a characterization of core points for direct products of symmetric groups, we show that prototype implementations can compete with state-of-the-art commercial solvers, and solve an open MIPLIB problem.

Recommendations

• Core sets and symmetric convex optimization
• On lattice-free orbit polytopes
• Algorithms for highly symmetric linear and integer programs
• Exploiting orbits in symmetric ILP
• Symmetry in integer linear programming

Cites work

• scientific article; zbMATH DE number 3650737 (Why is no real title available?)
• scientific article; zbMATH DE number 3137403 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• A computational comparison of symmetry handling methods for mixed integer programs
• Algorithms for highly symmetric linear and integer programs
• Classification of orthogonal arrays by integer programming
• Exploiting orbits in symmetric ILP
• Fundamental Domains for Integer Programs with Symmetries
• Geometry, complexity, and combinatorics of permutation polytopes
• Improving bounds on the football pool problem by integer programming and high-throughput computing
• Invariant Semidefinite Programs
• On the Volume of Lattice Polyhedra
• Orbital branching
• Packing and partitioning orbitopes
• SCIP: solving constraint integer programs
• Symmetry groups, semidefinite programs, and sums of squares
• Symmetry in mathematical programming

Cited in

(10)

• Exploiting symmetries in polyhedral computations
• Core sets and symmetric convex optimization
• Algorithms for highly symmetric linear and integer programs
• A computational comparison of symmetry handling methods for mixed integer programs
• Orbital shrinking: theory and applications
• On lattice-free orbit polytopes
• Equivalence of lattice orbit polytopes
• Polytopes associated with symmetry handling
• On the geometry of symmetry breaking inequalities
• On the geometry of symmetry breaking inequalities

Describes a project that uses

Uses Software

• CPLEX
• MIPLIB
• SCIP
• polymake
• Normaliz

This page was built for publication: Exploiting symmetry in integer convex optimization using core points

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