A dual heuristic for mixed integer programming

DOI10.1016/J.ORL.2015.05.007MaRDI QIDQ1785392zbMATH OpenOpenAlexFDO

Authors Yaxian Li, Özlem Ergun, G. L. Nemhauser

Publication date 28 September 2018

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

Full work available at URL https://doi.org/10.1016/j.orl.2015.05.007

zbMATH Keywords

branch-and-bounddual heuristicknapsackrelaxations

Mathematics Subject Classification ID

Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Solving a mixed integer program by fathoming dual programs
• A monotonic, dual-based bounding procedure for integer programs
• Dual formulations and subgradient optimization strategies for linear programming relaxations of mixed-integer programs
• New convergent heuristics for 0-1 mixed integer programming
• Rounding and propagation heuristics for mixed integer programming

Cites work

• A genetic algorithm for the multidimensional knapsack problem
• Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions
• Exploring relaxation induced neighborhoods to improve MIP solutions
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• Local branching
• The feasibility pump
• Using diversification, communication and parallelism to solve mixed-integer linear programs

Cited in

(12)

• A hybrid primal heuristic for finding feasible solutions to mixed integer programs
• A monotonic, dual-based bounding procedure for integer programs
• A first look at picking dual variables for maximizing reduced cost fixing
• Pivot and shift -- a mixed integer programming heuristic
• An empirical evaluation of walk-and-round heuristics for mixed integer linear programs
• A feasibility pump heuristic for general mixed-integer problems
• Duality in {MIP} by branch-and-cut: generating dual price functions using branch-and-cut
• Solving a mixed integer program by fathoming dual programs
• A simple effective heuristic for embedded mixed-integer quadratic programming
• On the existence of duality gaps for mixed integer programming
• Chapter 9: An MPEC based heuristic
• An iterative time‐bucket refinement algorithm for a high‐resolution resource‐constrained project scheduling problem

Describes a project that uses

Uses Software

• FEASPUMP

This page was built for publication: A dual heuristic for mixed integer programming

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