mixed-integer programming

Towards Simulation Based Mixed-Integer Optimization with Differential Equations

  • Martin Gugat
  • Günter Leugering
  • Martin Schmidt
  • Mathias Sirvent
  • David Wintergerst
  • Alexander Martin
    • Categories (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering, Systems governed by Differential Equations Optimization Tags , , , ,

    We propose a decomposition based method for solving mixed-integer nonlinear optimization problems with “black-box” nonlinearities, where the latter, e.g., may arise due to differential equations or expensive simulation runs. The method alternatingly solves a mixed-integer linear master problem and a separation problem for iteratively refining the mixed-integer linear relaxation of the nonlinearity. We prove that … Read more

    A Polyhedral Study on Chance Constrained Program with Random Right-Hand Side

  • Kai Huang
  • Bo Zeng
  • Ming Zhao
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Stochastic Programming Tags , , , , ,

    The essential structure of the mixed–integer programming formulation for chance–constrained program (CCP) is the intersection of multiple mixing sets with a $0-1$ knapsack. To improve our computational capacity on CCP, an underlying substructure, the (single) mixing set with a $0-1$ knapsack, has received substantial attentions recently. In this study, we consider a CCP problem with … Read more

    Solving Large Aircraft Landing Problems on Multiple Runways by Applying a Constraint Programming Approach

  • Amir Salehipour
    • Categories Applications - OR and Management Sciences Tags , ,

    Aircraft Landing Problem is to assign an airport’s runways to the arrival aircraft as well as to schedule the landing time of these aircraft. In this paper, due to the complexity of the problem, which is NP-hard, we develop an iterative-based heuristic by exploiting special characteristics of the problem. Computational results show the developed approach … Read more

    Generation of Feasible Integer Solutions on a Massively Parallel Computer

  • Utku Koc
  • Sanjay Mehrotra
    • Categories (Mixed) Integer Linear Programming Tags , ,

    We present an approach to parallelize generation of feasible solutions of mixed integer linear programs in distributed memory high performance computing environments. The approach combines a parallel framework with feasibility pump (FP) as the rounding heuristic. The proposed approach runs multiple FP instances with different starting so- lutions concurrently, while allowing them to share information. … Read more

    Facial reduction heuristics and the motivational example of mixed-integer conic optimization

  • Henrik A. Friberg
    • Categories Integer Programming, Linear, Cone and Semidefinite Programming Tags , ,

    Facial reduction heuristics are developed in the interest of added performance and reliability in methods for mixed-integer conic optimization. Specifically, the process of branch-and-bound is shown to spawn subproblems for which the conic relaxations are difficult to solve, and the objective bounds of linear relaxations are arbitrarily weak. While facial reduction algorithms already exist to … Read more

    A Multi-Objective approach to visualize proportions and similarities between individuals by rectangular maps

  • Emilio Carrizosa
  • Dolores Romero Morales
  • Vanesa Guerrero
    • Categories Applications - OR and Management Sciences Tags , , ,

    In this paper we address the problem of visualizing the proportions and the similarities attached to a set of individuals. We represent this information using a rectangular map, i.e., a subdivision of a rectangle into rectangular portions so that each portion is associated with one individual, their areas reflect the proportions, and the closeness between … Read more

    Data-Driven Patient Scheduling in Emergency Departments: A Hybrid Robust-Stochastic Approach

  • Shuangchi He
  • Melvyn Sim
  • Meilin Zhang
    • Categories Robust Optimization Tags , , , , ,

    Emergency care necessitates adequate and timely treatment, which has unfortunately been compromised by crowding in many emergency departments (EDs). To address this issue, we study patient scheduling in EDs so that mandatory targets imposed on each patient’s door-to-provider time and length of stay can be collectively met with the largest probability. Exploiting patient flow data … Read more

    A Computational Comparison of Symmetry Handling Methods for Mixed Integer Programs

  • Marc E. Pfetsch
  • Thomas Rehn
    • Categories (Mixed) Integer Linear Programming Tags , , , ,

    The handling of symmetries in mixed integer programs in order to speed up the solution process of branch-and-cut solvers has recently received significant attention, both in theory and practice. This paper compares different methods for handling symmetries using a common implementation framework. We start by investigating the computation of symmetries and analyze the symmetries present … Read more

    Partial outer convexification for traffic light optimization in road networks

  • Simone Göttlich
  • Andreas Potschka
  • Ute Ziegler
    • Categories (Mixed) Integer Nonlinear Programming, Optimization of Systems modeled by PDEs, Transportation Tags , , , ,

    We consider the problem of computing optimal traffic light programs for urban road intersections using traffic flow conservation laws on networks. Based on a Partial Outer Convexification approach, which has been successfully applied in the area of mixed-integer optimal control for systems of ordinary or differential algebraic equations, we develop a computationally tractable two-stage solution … Read more

    An Abstract Model for Branching and its Application to Mixed Integer Programming

  • Pierre Le Bodic
  • George L. Nemhauser
    • Categories (Mixed) Integer Linear Programming, Optimization Software Design Principles Tags , , , ,

    The selection of branching variables is a key component of branch-and-bound algorithms for solving Mixed-Integer Programming (MIP) problems since the quality of the selection procedure is likely to have a significant effect on the size of the enumeration tree. State-of-the-art procedures base the selection of variables on their “LP gains”, which is the dual bound … Read more