Raymond Hemmecke

On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds-Karp to Bland and Beyond

  • Jesús A. De Loera
  • Raymond Hemmecke
  • Jon Lee
    • Categories (Mixed) Integer Linear Programming, Linear Programming Tags , , , , , , , , ,

    Motivated by Bland’s linear-programming generalization of the renowned Edmonds-Karp efficient refinement of the Ford-Fulkerson maximum-flow algorithm, we discuss three closely-related natural augmentation rules for linear and integer-linear optimization. In several nice situations, we show that polynomially-many augmentation steps suffice to reach an optimum. In particular, when using “discrete steepest-descent augmentations” (i.e., directions with the best … Read more

    Graver basis and proximity techniques for block-structured separable convex integer minimization problems

  • Raymond Hemmecke
  • Matthias Köppe
  • Robert Weismantel
    • Categories (Mixed) Integer Nonlinear Programming Tags , , , , , ,

    We consider N-fold 4-block decomposable integer programs, which simultaneously generalize N-fold integer programs and two-stage stochastic integer programs with N scenarios. In previous work [R. Hemmecke, M. Koeppe, R. Weismantel, A polynomial-time algorithm for optimizing over N-fold 4-block decomposable integer programs, Proc. IPCO 2010, Lecture Notes in Computer Science, vol. 6080, Springer, 2010, pp. 219–229], … Read more

    Nonlinear Integer Programming

  • Raymond Hemmecke
  • Matthias Köppe
  • Jon Lee
  • Robert Weismantel
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Tags

    Research efforts of the past fifty years have led to a development of linear integer programming as a mature discipline of mathematical optimization. Such a level of maturity has not been reached when one considers nonlinear systems subject to integrality requirements for the variables. This chapter is dedicated to this topic.  The primary goal is … Read more

    Pareto Optima of Multicriteria Integer Linear Programs

  • Jesús A. De Loera
  • Raymond Hemmecke
  • Matthias Köppe
    • Categories Integer Programming, Multi-Criteria Optimization

    We settle the computational complexity of fundamental questions related to multicriteria integer linear programs, when the dimensions of the strategy space and of the outcome space are considered fixed constants. In particular we construct: 1. polynomial-time algorithms to exactly determine the number of Pareto optima and Pareto strategies; 2. a polynomial-space polynomial-delay prescribed-order enumeration algorithm … Read more