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

    Nonlinear Optimization over a Weighted Independence System

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

    We consider the problem of optimizing a nonlinear objective function over a weighted independence system presented by a linear-optimization oracle. We provide a polynomial-time algorithm that determines an r-best solution for nonlinear functions of the total weight of an independent set, where r is a constant that depends on certain Frobenius numbers of the individual … Read more

    On sublattice determinants in reduced bases

  • Gabor Pataki
  • Mustafa Tural
    • Categories Integer Programming, Other Topics Tags , , ,

    We prove several inequalities on the determinants of sublattices in LLL-reduced bases. They generalize the fundamental inequalities of Lenstra, Lenstra, and Lovasz on the length of the shortest vector, and show that LLL-reduction finds not only a short vector, but also sublattices with small determinants. We also prove new inequalities on the product of the … Read more

    Maximizing a Class of Submodular Utility Functions

  • Shabbir Ahmed
  • Alper Atamturk
    • Categories Branch and Cut Algorithms, Integer Programming Tags , , ,

    Given a finite ground set N and a value vector a in R^N, we consider optimization problems involving maximization of a submodular set utility function of the form h(S)= f (sum_{i in S} a_i), S subseteq N, where f is a strictly concave, increasing, differentiable function. This function appears frequently in combinatorial optimization problems when … Read more

    The Value Function of a Mixed-Integer Linear Program with a Single Constraint

  • Menal Guzelsoy
  • Ted K. Ralphs
    • Categories (Mixed) Integer Linear Programming

    The value function of a mixed-integer linear program (MILP) is a function that returns the optimal solution value as a function of the right-hand side. In this paper, we analyze the structure of the value function of a MILP with a single constraint. We show that the value function is uniquely determined by a finite … Read more

    A Polyhedral Approach to the Single Row Facility Layout Problem

  • André R. S. Amaral
  • Adam N. Letchford
    • Categories Combinatorial Optimization, Integer Programming Tags , ,

    The Single Row Facility Layout Problem (SRFLP) is the problem of arranging facilities of given lengths on a line, while minimizing a weighted sum of the distances between all pairs of facilities. The SRFLP is strongly NP-hard and includes the well-known linear arrangement problem as a special case. We perform the first ever polyhedral study … Read more

    Water Network Design by MINLP

  • Cristiana Bragalli
  • Claudia D'Ambrosio
  • Jon Lee
  • Andrea Lodi
  • Paolo Toth
    • Categories (Mixed) Integer Nonlinear Programming, Civil and Environmental Engineering

    We propose a solution method for a water-network optimization problem using a nonconvex continuous NLP (nonlinear programming) relaxation and a MINLP (mixed integer nonlinear programming) search. Our approach employs a relatively simple and accurate model that pays some attention to the requirements of the solvers that we employ. Our view is that in doing so, … Read more

    Disjunctive Cuts for Non-Convex Mixed Integer Quadratically Constrained Programs

  • Pierre Bonami
  • Jon Lee
  • Anureet Saxena
    • Categories (Mixed) Integer Nonlinear Programming, Constrained Nonlinear Optimization, Global Optimization Tags , , , ,

    This paper addresses the problem of generating strong convex relaxations of Mixed Integer Quadratically Constrained Programming (MIQCP) problems. MIQCP problems are very difficult because they combine two kinds of non-convexities: integer variables and non-convex quadratic constraints. To produce strong relaxations of MIQCP problems, we use techniques from disjunctive programming and the lift-and-project methodology. In particular, … Read more

    Disjunctive Decomposition for Two-Stage Stochastic Mixed-Binary Programs with Random Recourse

  • Lewis Ntaimo
    • Categories Cutting Plane Approaches, Stochastic Programming Tags , , , ,

    This paper introduces disjunctive decomposition for two-stage mixed 0-1 stochastic integer programs (SIPs) with random recourse. Disjunctive decomposition allows for cutting planes based on disjunctive programming to be generated for each scenario subproblem under a temporal decomposition setting of the SIP problem. A new class of valid inequalities for mixed 0-1 SIP with random recourse … Read more