Integer Programming

Monomial-wise Optimal Separable Underestimators for Mixed-Integer Polynomial Optimization

  • Christoph Buchheim
  • Claudia D'Ambrosio
    • Categories (Mixed) Integer Nonlinear Programming, Bound-constrained Optimization, Global Optimization

    In this paper we introduce a new method for solving box-constrained mixed-integer polynomial problems to global optimality. The approach, a specialized branch-and-bound algorithm, is based on the computation of lower bounds provided by the minimization of separable underestimators of the polynomial objective function. The underestimators are the novelty of the approach because the standard approaches … Read more

    Approximation Algorithms for the Incremental Knapsack Problem via Disjunctive Programming

  • Daniel Bienstock
  • Jay Sethuraman
  • Chun Ye
    • Categories 0-1 Programming, Approximation Algorithms Tags , ,

    In the \emph{incremental knapsack problem} ($\IK$), we are given a knapsack whose capacity grows weakly as a function of time. There is a time horizon of $T$ periods and the capacity of the knapsack is $B_t$ in period $t$ for $t = 1, \ldots, T$. We are also given a set $S$ of $N$ items … Read more

    Efficient upper and lower bounds for global mixed-integer optimal control

  • Mathieu Claeys
  • Sebastian Sager
  • Frédéric Messine
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Applications, Optimization of Simulated Systems

    We present a control problem for an electrical vehicle. Its motor can be operated in two discrete modes, leading either to acceleration and energy consumption, or to a recharging of the battery. Mathematically, this leads to a mixed-integer optimal control problem (MIOCP) with a discrete feasible set for the controls taking into account the electrical … Read more

    A Practical Iterative Algorithm for the Art Gallery Problem using Integer Linear Programming

  • Pedro J. de Rezende
  • Cid C. de Souza
  • D. C. Tozoni
    • Categories Combinatorial Optimization, Integer Programming Tags , , ,

    In the last few decades, the search for exact algorithms for known NP-hard geometric problems has intensified. Many of these solutions make use of Integer Linear Programming (ILP) modeling and rely on state of the art solvers, to be able to find optimal solutions for large instances in a matter of minutes. In this work, … Read more

    Finding Diverse Solutions of High Quality to Binary Integer Programs

  • Renata A. Konrad
  • Andrew C. Trapp
    • Categories 0-1 Programming, Multi-Criteria Optimization, Nonlinear Optimization

    Typical output from an optimization solver is a single optimal solution. At the same time, a set of high-quality and diverse solutions could be beneficial in a variety of contexts, for example problems involving imperfect information, or those for which the structure of high-quality solution vectors can reveal meaningful insights. In view of this, we … Read more

    Bin Packing and Related Problems: General Arc-flow Formulation with Graph Compression

  • Filipe Brandão
  • João Pedro Pedroso
    • Categories Dynamic Programming, Integer Programming, Polyhedra Tags , , ,

    We present an exact method, based on an arc-flow formulation with side constraints, for solving bin packing and cutting stock problems — including multi-constraint variants — by simply representing all the patterns in a very compact graph. Our method includes a graph compression algorithm that usually reduces the size of the underlying graph substantially without … Read more

    On the generation of cutting planes which maximize the bound improvement

  • Stefano Coniglio
  • Martin Tieves
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags ,

    We propose the bound-optimal cutting plane method. It is a new paradigm for cutting plane generation in Mixed Integer Programming allowing for the simultaneous generation of k cuts which, when added to the current Linear Programming elaxation, yield the largest bound improvement. By Linear Programming duality arguments and standard linearization techniques we show that, for … Read more

    Computing a Cournot Equilibrium in Integers

  • Michael J. Todd
    • Categories Applications - OR and Management Sciences, Integer Programming Tags

    We give an efficient algorithm for computing a Cournot equilibrium when the producers are confined to integers, the inverse demand function is linear, and costs are quadratic. The method also establishes existence, which follows in much more generality because the problem can be modelled as a potential game. Citation School of Operations Research and Information … Read more

    Strongly Agree or Strongly Disagree?: Rating Features in Support Vector Machines

  • Emilio Carrizosa
  • Dolores Romero Morales
  • Amaya Nogales-Gómez
    • Categories (Mixed) Integer Linear Programming, Data-Mining Tags , , , ,

    In linear classifiers, such as the Support Vector Machine (SVM), a score is associated with each feature and objects are assigned to classes based on the linear combination of the scores and the values of the features. Inspired by discrete psychometric scales, which measure the extent to which a factor is in agreement with a … Read more

    Mixed-Integer Rounding Enhanced Benders Decomposition for Multiclass Service System Staffing and Scheduling with Arrival Rate Uncertainty

  • Merve Bodur
  • James R. Luedtke
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Stochastic Programming Tags , , , ,

    We study server scheduling in multiclass service systems under stochastic uncertainty in the customer arrival volumes. Common practice in such systems is to first identify staffing levels, and then determine schedules for the servers that cover these targets. We propose a new stochastic integer programming model that integrates these two decisions, which can yield lower … Read more