Integer Programming

Switching cost aware rounding for relaxations of mixed-integer optimal control problems: the two-dimensional case

  • Felix Bestehorn
  • Christoph Hansknecht
  • Christian Kirches
  • Paul Manns
    • Categories (Mixed) Integer Nonlinear Programming, Control Applications Tags ,

    This article is concerned with a recently proposed switching cost aware rounding (SCARP) strategy in the combinatorial integral decomposition for mixed-integer optimal control problems (MIOCPs). We consider the case of a control variable that is discrete-valued and distributed on a two-dimensional domain. While the theoretical results from the one-dimensional case directly apply to the multidimensional … Read more

    An Approximation Algorithm for Indefinite Mixed Integer Quadratic Programming

  • Alberto Del Pia
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory

    In this paper we give an algorithm that finds an epsilon-approximate solution to a mixed integer quadratic programming (MIQP) problem. The algorithm runs in polynomial time if the rank of the quadratic function and the number of integer variables are fixed. The running time of the algorithm is expected unless P=NP. In order to design … Read more

    Decomposition Methods for Global Solutions of Mixed-Integer Linear Programs

  • Kaizhao Sun
  • Wotao Yin
  • Mou Sun
    • Categories (Mixed) Integer Linear Programming, Global Optimization Tags , ,

    This paper introduces two decomposition-based methods for two-block mixed-integer linear programs (MILPs), which aim to take advantage of separable structures of the original problem by solving a sequence of lower-dimensional MILPs. The first method is based on the $\ell_1$-augmented Lagrangian method (ALM), and the second one is based on a modified alternating direction method of … Read more

    Cutting Plane Generation Through Sparse Principal Component Analysis

  • Santanu S. Dey
  • Aleksandr M. Kazachkov
  • Andrea Lodi
  • Gonzalo Muñoz
    • Categories Cutting Plane Approaches, Quadratic Programming Tags , , ,

    Quadratically-constrained quadratic programs (QCQPs) are optimization models whose remarkable expressiveness has made them a cornerstone of methodological research for nonconvex optimization problems. However, modern methods to solve a general QCQP fail to scale, encountering computational challenges even with just a few hundred variables. Specifically, a semidefinite programming (SDP) relaxation is typically employed, which provides strong … Read more

    Scaling Up Exact Neural Network Compression by ReLU Stability

  • Abhinav Kumar
  • Srikumar Ramalingam
  • Thiago Serra
    • Categories (Mixed) Integer Linear Programming, Applications - Science and Engineering, Combinatorial Optimization

    We can compress a neural network while exactly preserving its underlying functionality with respect to a given input domain if some of its neurons are stable. However, current approaches to determine the stability of neurons in networks with Rectified Linear Unit (ReLU) activations require solving or finding a good approximation to multiple discrete optimization problems. … Read more

    Learning Symbolic Expressions: Mixed-Integer Formulations, Cuts, and Heuristics

  • Prasanna Balaprakash
  • Sven Leyffer
  • Jongeun Kim
    • Categories (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering Tags , , ,

    In this paper we consider the problem of learning a regression function without assuming its functional form. This problem is referred to as symbolic regression. An expression tree is typically used to represent a solution function, which is determined by assigning operators and operands to the nodes. The symbolic regression problem can be formulated as … Read more

    A simulation-based optimization approach for the calibration of a discrete event simulation model of an emergency department

  • Alberto De Santis
  • Tommaso Giovannelli
  • Stefano Lucidi
  • Mauro Messedaglia
  • Massimo Roma
    • Categories Applications - OR and Management Sciences, Integer Programming, Optimization of Simulated Systems Tags , , , ,

    Accurate modeling of the patient flow within an Emergency Department (ED) is required by all studies dealing with the increasing and well-known problem of overcrowding. Since Discrete Event Simulation (DES) models are often adopted with the aim of assessing solutions for reducing the impact of this worldwide phenomenon, an accurate estimation of the service time … Read more

    A Bilevel Optimization Approach to Decide the Feasibility of Bookings in the European Gas Market

  • Martine Labbé
  • Martin Schmidt
  • Johannes Thürauf
  • Fränk Plein
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Robust Optimization Tags , , , ,

    The European gas market is organized as a so-called entry-exit system with the main goal to decouple transport and trading. To this end, gas traders and the transmission system operator (TSO) sign so-called booking contracts that grant capacity rights to traders to inject or withdraw gas at certain nodes up to this capacity. On a … Read more

    An exact price-cut-and-enumerate method for the capacitated multi-trip vehicle routing problem with time windows

  • Yu Yang
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Transportation Tags , , ,

    We consider the capacitated multi-trip vehicle routing problem with time windows (CMTVRPTW), where vehicles are allowed to make multiple trips. The ability to perform multiple trips is necessary for some real-world applications where the vehicle capacity, the trip duration, or the number of drivers or vehicles is limited. However, it substantially increases the solution difficulty … Read more

    On the Structure of Decision Diagram-Representable Mixed Integer Programs with Application to Unit Commitment

  • Hosseinali Salemi
  • Danial Davarnia
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Energy Tags , , ,

    Over the past decade, decision diagrams (DDs) have been used to model and solve integer programming and combinatorial optimization problems. Despite successful performance of DDs in solving various discrete optimization problems, their extension to model mixed integer programs (MIPs) such as those appearing in energy applications has been lacking. More broadly, the question on which … Read more