Integer Programming

Computing Feasible Points of Bilevel Problems with a Penalty Alternating Direction Method

  • Thomas Kleinert
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , , ,

    Bilevel problems are highly challenging optimization problems that appear in many applications of energy market design, critical infrastructure defense, transportation, pricing, etc. Often, these bilevel models are equipped with integer decisions, which makes the problems even harder to solve. Typically, in such a setting in mathematical optimization one develops primal heuristics in order to obtain … Read more

    Snow Plow Route Optimization: A Constraint Programming Approach

  • Joris Kinable
  • Willem-Jan van Hoeve
  • Stephen F. Smith
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Integer Programming

    Many cities have to cope with annual snowfall, but are struggling to manage their snow plowing activities efficiently. Despite the fact that winter road maintenance has been the subject of many research papers over the last 3 decades, very few practical decision support systems have been developed to deal with the complex decision problems involved … Read more

    A switching cost aware rounding method for relaxations of mixed-integer optimal control problems

  • Felix Bestehorn
  • Christoph Hansknecht
  • Christian Kirches
  • Paul Manns
    • Categories (Mixed) Integer Nonlinear Programming, Systems governed by Differential Equations Optimization Tags ,

    This article investigates a class of Mixed-Integer Optimal Control Problems (MIOCPs) with switching costs. We introduce the problem class of Minimal-Switching-Cost Optimal Control Problems (MSCP) with an objective function that consists of two summands, a continuous term depending on the state vector and an encoding of the discrete switching costs. State vectors of Mixed-Integer Optimal … Read more

    Avoiding redundant columns by adding classical Benders cuts to column generation subproblems

  • Marco E. Lübbecke
  • Stephen J. Maher
  • Jonas T. Witt
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    When solving the linear programming (LP) relaxation of a mixed-integer program (MIP) with column generation, columns might be generated that are not needed to express any integer optimal solution of the MIP. Such columns are called strongly redundant and the dual bound obtained by solving the LP relaxation is potentially stronger if these columns are … Read more

    Clairvoyant Restarts in Branch-and-Bound Search Using Online Tree-Size Estimation

  • Daniel Anderson
  • Gregor Hendel
  • Pierre Le Bodic
  • Merlin Viernickel
    • Categories (Mixed) Integer Linear Programming

    We propose a simple and general online method to measure the search progress within the Branch-and-Bound algorithm, from which we estimate the size of the remaining search tree. We then show how this information can help solvers algorithmically at runtime by designing a restart strategy for Mixed-Integer Programming (MIP) solvers that decides whether to restart … Read more

    A Framework for Peak Shaving Through the Coordination of Smart Homes

  • Miguel F. Anjos
  • Michael David de Souza Dutra
  • Sébastien Le Digabel
    • Categories (Mixed) Integer Linear Programming, Energy, Scheduling

    In demand–response programs, aggregators balance the needs of generation companies and end-users. This work proposes a two-phase framework that shaves the aggregated peak loads while maintaining the desired comfort level for users. In the first phase, the users determine their planned consumption. For the second phase, we develop a bilevel model with mixed-integer variables and … Read more

    Risk Aversion to Parameter Uncertainty in Markov Decision Processes with an Application to Slow-Onset Disaster Relief

  • Simge Küçükyavuz
  • Merve Merakli
    • Categories Integer Programming, Stochastic Programming, Supply Chain Management Tags , , , , ,

    In classical Markov Decision Processes (MDPs), action costs and transition probabilities are assumed to be known, although an accurate estimation of these parameters is often not possible in practice. This study addresses MDPs under cost and transition probability uncertainty and aims to provide a mathematical framework to obtain policies minimizing the risk of high long-term … Read more

    A Computational Comparison of Optimization Methods for the Golomb Ruler Problem

  • Burak Kocuk
  • Willem-Jan van Hoeve
    • Categories Integer Programming Tags , ,

    The Golomb ruler problem is defined as follows: Given a positive integer n, locate n marks on a ruler such that the distance between any two distinct pair of marks are different from each other and the total length of the ruler is minimized. The Golomb ruler problem has applications in information theory, astronomy and … Read more

    Identifying the Optimal Value Function of a Negative Markov Decision Process: An Integer Programming Approach

  • Amin Dehghanian
    • Categories (Mixed) Integer Linear Programming, Dynamic Programming Tags , , ,

    Mathematical programming formulation to identify the optimal value function of a negative Markov decision process (MDP) is non-convex, non-smooth, and computationally intractable. Also note that other well-known solution methods of MDP do not work properly for a negative MDP. More specifically, the policy iteration diverges, and the value iteration converges but does not provide an … Read more

    Algorithms for the circle packing problem based on mixed-integer DC programming

  • Yoshiko Ikebe
  • Satoru Masuda
  • Takayuki Okuno
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences Tags , ,

    Circle packing problems are a class of packing problems which attempt to pack a given set of circles into a container with no overlap. In this paper, we focus on the circle packing problem proposed by L{\’o}pez et.al. The problem is to pack circles of unequal size into a fixed size circular container, so as … Read more