integer programming

Algorithms for stochastic lot-sizing problems with backlogging

  • Yongpei Guan
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , ,

    As a traditional model in the operations research and management science domain, lot-sizing problem is embedded in many application problems such as production and inventory planning and has been consistently drawing attentions from researchers. There is significant research progress on polynomial time algorithm developments for deterministic uncapacitated lot-sizing problems based on Wagner-and-Whitin property. However, in … Read more

    New Turnpike Theorems for the Unbounded Knapsack Problem

  • Ping H. Huang
  • Thomas L. Morin
    • Categories Combinatorial Optimization, Integer Programming Tags , , , ,

    We develop sharp bounds on turnpike theorems for the unbounded knapsack problem. Turnpike theorems specify when it is optimal to load at least one unit of the best item (i.e., the one with the highest “bang-for-buck” ratio) and, thus can be used for problem preprocessing. The successive application of the turnpike theorems can drastically reduce … Read more

    A p-Cone Sequential Relaxation Procedure for 0-1 Integer Programs

  • Samuel Burer
  • Jieqiu Chen
    • Categories 0-1 Programming, Global Optimization Theory, Second-Order Cone Programming Tags , , , ,

    Given a 0-1 integer programming problem, several authors have introduced sequential relaxation techniques — based on linear and/or semidefinite programming — that generate the convex hull of integer points in at most $n$ steps. In this paper, we introduce a sequential relaxation technique, which is based on $p$-order cone programming ($1 \le p \le \infty$). … Read more

    Size constrained graph partitioning polytope. Part I: Dimension and trivial facets

  • Martine Labbé
  • F. Aykut Özsoy
    • Categories 0-1 Programming, Polyhedra Tags , , , , ,

    We consider the problem of clustering a set of items into subsets whose sizes are bounded from above and below. We formulate the problem as a graph partitioning problem and propose an integer programming model for solving it. This formulation generalizes several well-known graph partitioning problems from the literature like the clique partitioning problem, the … Read more

    Size constrained graph partitioning polytope. Part II: Non-trivial facets

  • Martine Labbé
  • F. Aykut Özsoy
    • Categories 0-1 Programming, Polyhedra Tags , , , ,

    We consider the problem of clustering a set of items into subsets whose sizes are bounded from above and below. We formulate the problem as a graph partitioning problem and propose an integer programming model for solving it. This formulation generalizes several well-known graph partitioning problems from the literature like the clique partitioning problem, the … Read more

    Parallel Approximation, and Integer Programming Reformulation

  • Gabor Pataki
  • Mustafa Tural
    • Categories (Mixed) Integer Linear Programming, Integer Programming, Polyhedra Tags , , ,

    We analyze two integer programming reformulations of the n-dimensional knapsack feasibility problem without assuming any structure on the weight vector $a.$ Both reformulations have a constraint matrix in which the columns form a reduced basis in the sense of Lenstra, Lenstra, and Lov\’asz. The nullspace reformulation of Aardal, Hurkens and Lenstra has n-1 variables, and … Read more

    Lifting for Conic Mixed-Integer Programming

  • Alper Atamturk
  • Vishnu Narayanan
    • Categories (Mixed) Integer Nonlinear Programming, Integer Programming Tags , ,

    Lifting is a procedure for deriving valid inequalities for mixed-integer sets from valid inequalities for suitable restrictions of those sets. Lifting has been shown to be very effective in developing strong valid inequalities for linear integer programming and it has been successfully used to solve such problems with branch-and-cut algorithms. Here we generalize the theory … Read more

    New Formulations for Optimization Under Stochastic Dominance Constraints

  • James R. Luedtke
    • Categories Stochastic Programming Tags , , , ,

    Stochastic dominance constraints allow a decision-maker to manage risk in an optimization setting by requiring their decision to yield a random outcome which stochastically dominates a reference random outcome. We present new integer and linear programming formulations for optimization under first and second-order stochastic dominance constraints, respectively. These formulations are more compact than existing formulations, … Read more

    A new, solvable, primal relaxation for nonlinear integer programming problems with linear constraints

  • Monique Guignard
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization Tags , , , ,

    This paper describes a new primal relaxation for nonlinear integer programming problems with linear constraints. This relaxation, contrary to the standard Lagrangean relaxation, can be solved efficiently. It requires the solution of a nonlinear penalized problem whose linear constraint set is known only implicitly, but whose solution is made possible by the use of a … Read more

    On Test Sets for Nonlinear Integer Maximization

  • Shmuel Onn
  • Robert Weismantel
  • Jon Lee
    • Categories (Mixed) Integer Nonlinear Programming Tags , , , , ,

    A finite test set for an integer maximization problem enables us to verify whether a feasible point attains the global maximum. We establish in this paper several general results that apply to integer maximization problems with nonlinear objective functions. CitationOperations Research Letters 36 (2008) 439–443ArticleDownload View PDF