Certificates of optimality for mixed integer linear programming using generalized subadditive generator functions

DOI10.1155/2016/5017369MaRDI QIDQ1748494zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Kevin K. H. Cheung, Babak Moazzez

Publication date 11 May 2018

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

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1155/2016/5017369

Mathematics Subject Classification ID

Linear programming (90C05) Mixed integer programming (90C11) Combinatorial optimization (90C27)

Review text

Summary: We introduce generalized subadditive generator functions for mixed integer linear programs. Our results extend \textit{D. Klabjan}'s work [Eur. J. Oper. Res. 183, No. 2, 525--545 (2007; Zbl 1166.90012)] from pure integer programs with nonnegative entries to general MILPs. These functions suffice to achieve strong subadditive duality. Several properties of the functions are shown. We then use this class of functions to generate certificates of optimality for MILPs. We have performed a computational test study on knapsack problems to investigate the efficiency of the certificates.

Recommendations

• Sufficient global optimality conditions for general mixed integer nonlinear programming problems
• Certificates of linear mixed integer infeasibility
• scientific article; zbMATH DE number 3889293
• On Subadditive Duality for Conic Mixed-integer Programs
• On sublinear inequalities for mixed integer conic programs
• scientific article; zbMATH DE number 4112378
• scientific article; zbMATH DE number 3887448
• Procedures for optimization problems with a mixture of bounds and general linear constraints
• Dual formulations and subgradient optimization strategies for linear programming relaxations of mixed-integer programs
• Method for solving generalized convex nonsmooth mixed-integer nonlinear programming problems

Cites work

• A hybrid branch-and-bound approach for exact rational mixed-integer programming
• Certification of an optimal TSP tour through 85,900 cities
• Duality for mixed-integer linear programs
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• Integer programming duality: Price functions and sensitivity analysis
• Integrated methods for optimization
• Lifting, tilting and fractional programming revisited
• Minimal inequalities
• On the existence of optimal solutions to integer and mixed-integer programming problems
• Some continuous functions related to corner polyhedra, II
• Stability, parametric, and postoptimality analysis of discrete optimization problems
• Subadditive approaches in integer programming
• The value function of an integer program

Cited in

(3)

• Coordination of manufacturing and engineering activities during product transitions
• Generator subadditive functions for mixed-integer programs
• Satisfiability modulo theories for verifying MILP certificates

Describes a project that uses

Uses Software

• Cbc

This page was built for publication: Certificates of optimality for mixed integer linear programming using generalized subadditive generator functions

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