Paper Search Console

Home Search Page About Contact

Journal Title

Title of Journal: Math Program

Search In Journal Title:

Abbravation: Mathematical Programming

Search In Journal Abbravation:

Publisher

Springer-Verlag

Search In Publisher:

DOI

10.1016/0041-008x(84)90101-7

Search In DOI:

ISSN

1436-4646

Search In ISSN:
Search In Title Of Papers:

On the exact separation of mixed integer knapsack

Authors: Ricardo Fukasawa Marcos Goycoolea
Publish Date: 2009/06/06
Volume: 128, Issue: 1-2, Pages: 19-41
PDF Link

Abstract

During the last decades much research has been conducted on deriving classes of valid inequalities for mixed integer knapsack sets which we call knapsack cuts Bixby et al The sharpest cut the impact of Manfred Padberg and his work MPS/SIAM Series on Optimization pp 309–326 2004 empirically observe that within the context of branchandcut algorithms to solve mixed integer programming problems the most important inequalities are knapsack cuts derived by the mixed integer rounding MIR procedure In this work we analyze this empirical observation by developing an algorithm to separate over the convex hull of a mixed integer knapsack set The main feature of this algorithm is a specialized subroutine for optimizing over a mixed integer knapsack set which exploits dominance relationships The exact separation of knapsack cuts allows us to establish natural benchmarks by which to evaluate specific classes of them Using these benchmarks on MIPLIB 30 and MIPLIB 2003 instances we analyze the performance of MIR inequalities Our computations which are performed in exact arithmetic are surprising In the vast majority of the instances in which knapsack cuts yield bound improvements MIR cuts alone achieve over 87 of the observed gain

Keywords:

References

.
Search In Abstract Of Papers:
Other Papers In This Journal:
  1. Submodular maximization meets streaming: matchings, matroids, and more
  2. Some computationally relevant group theoretic structures of fixed charge problems
  3. Applications of convex analysis within mathematics
  4. Large-scale semidefinite programs in electronic structure calculation
  5. A distributionally robust perspective on uncertainty quantification and chance constrained programming
  6. The factorization approach to large-scale linear programming
  7. Beyond symmetric Broyden for updating quadratic models in minimization without derivatives
  8. A spatial branch-and-cut method for nonconvex QCQP with bounded complex variables
  9. Breakpoint searching algorithms for the continuous quadratic knapsack problem
  10. Sandwich games
  11. Approximations of Nash equilibria
  12. Using cuts for mixed integer knapsack sets to generate cuts for mixed integer polyhedral conic sets
  13. A robust and efficient method for solving point distance problems by homotopy
  14. A nonmonotone GRASP
  15. Extreme point inequalities and geometry of the rank sparsity ball
  16. Primal-dual interior-point methods for PDE-constrained optimization
  17. A new branch-and-cut algorithm for the capacitated vehicle routing problem
  18. Single item lot-sizing with non-decreasing capacities
  19. Structural and algorithmic properties for parametric minimum cuts
  20. Simple integer recourse models: convexity and convex approximations
  21. A model of the coNP-complete non-Hamilton tour decision problem for directed graphs
  22. Iteration complexity analysis of block coordinate descent methods
  23. Error Bounds of Regularized Gap Functions for Nonsmooth Variational Inequality Problems
  24. Accelerating the cubic regularization of Newton’s method on convex problems
  25. Bundle methods for sum-functions with “easy” components: applications to multicommodity network design
  26. On the number of solutions to the linear comple-mentarity problem
  27. Time-consistent approximations of risk-averse multistage stochastic optimization problems
  28. PEBBL: an object-oriented framework for scalable parallel branch and bound
  29. PEBBL: an object-oriented framework for scalable parallel branch and bound
  30. The capacitated max k -cut problem
  31. Critical extreme points of the 2-edge connected spanning subgraph polytope
  32. Nash equilibria in the two-player kidney exchange game
  33. On some properties and an application of the logarithmic barrier method
  34. Complementarity systems in optimization
  35. Analysis of infeasible-interior-point paths arising with semidefinite linear complementarity problems
Search Result: