(Mixed) Integer Nonlinear Programming

A Two-Stage Stochastic Integer Programming Approach to Integrated Staffing and Scheduling with Application to Nurse Management

  • Kibaek Kim
  • Sanjay Mehrotra
    • Categories (Mixed) Integer Nonlinear Programming, Scheduling, Stochastic Programming Tags , , , , ,

    We study the problem of integrated staffing and scheduling under demand uncertainty. The problem is formulated as a two-stage stochastic integer program with mixed-integer recourse. The here-and-now decision is to find initial staffing levels and schedules, well ahead in time. The wait-and-see decision is to adjust these schedules at a time epoch closer to the … Read more

    Active Set Methods with Reoptimization for Convex Quadratic Integer Programming

  • Christoph Buchheim
  • Long Trieu
    • Categories (Mixed) Integer Nonlinear Programming, Convex Optimization, Quadratic Programming Tags , ,

    We present a fast branch-and-bound algorithm for solving convex quadratic integer programs with few linear constraints. In each node, we solve the dual problem of the continuous relaxation using an infeasible active set method proposed by Kunisch and Rendl to get a lower bound; this active set algorithm is well suited for reoptimization. Our algorithm … Read more

    Approximation of the Quadratic Knapsack Problem

  • Ulrich Pferschy
  • Joachim Schauer
    • Categories (Mixed) Integer Nonlinear Programming, Approximation Algorithms Tags , , , ,

    We study the approximability of the classical quadratic knapsack problem (QKP) on special graph classes. In this case the quadratic terms of the objective function are not given for each pair of knapsack items. Instead an edge weighted graph G = (V,E) whose vertices represent the knapsack items induces a quadratic profit p_ij for the … Read more

    Memory-Aware Parallelized RLT3 for Solving Quadratic Assignment Problems

  • Monique Guignard
  • Peter M. Hahn
  • Amir Roth
  • Matthew Saltzman
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Parallel Algorithms Tags , ,

    We present a coarse-grain (outer-loop) parallel implementation of RLT1/2/3 (Level 1, 2, and 3 Reformulation and Linearization Technique—in that order) bound calculations for the QAP within a branch-and-bound procedure. For a search tree node of size S, each RLT3 and RLT2 bound calculation iteration is parallelized S ways, with each of S processors performing O(S5) … Read more

    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

    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

    Mathematical Programming: Turing completeness and applications to software analysis

  • Leo Liberti
  • Fabrizio Marinelli
    • Categories (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering, Global Optimization Applications Tags , , ,

    Mathematical Programming is Turing complete, and can be used as a general-purpose declarative language. We present a new constructive proof of this fact, and showcase its usefulness by discussing an application to finding the hardest input of any given program running on a Minsky Register Machine. We also discuss an application of Mathematical Programming to … Read more

    Exact and Heuristic Approaches for Directional Sensor Control

  • Hans D Mittelmann
  • Domenico Salvagnin
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Control Applications Tags , , ,

    Directional sensors are gaining importance due to applications, in- cluding surveillance, detection, and tracking. Such sensors have a limited fi eld-of-view and a discrete set of directions they can be pointed to. The Directional Sensor Control problem (DSCP) consists in assigning a direction of view to each sensor. The location of the targets is known with … Read more

    The Freight Train Routing Problem

  • Ralf Borndœrfer
  • Armin Fügenschuh
  • Torsten Klug
  • Thilo Schang
  • Thomas Schlechte
  • Hanno Schülldorf
    • Categories (Mixed) Integer Nonlinear Programming, Network Optimization, Transportation Tags , , ,

    We consider the following freight train routing problem (FTRP). Given is a transportation network with fixed routes for passenger trains and a set of freight trains (requests), each defined by an origin and destination station pair. The objective is to calculate a feasible route for each freight train such that a sum of all expected … Read more

    On the Separation of Split Inequalities for Non-Convex Quadratic Integer Programming

  • Christoph Buchheim
  • Emiliano Traversi
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Quadratic Programming

    We investigate the computational potential of split inequalities for non-convex quadratic integer programming, first introduced by Letchford and further examined by Burer and Letchford. These inequalities can be separated by solving convex quadratic integer minimization problems. For small instances with box-constraints, we show that the resulting dual bounds are very tight; they can close a … Read more