combinatorial optimization

MILP models for the continuous Berth Allocation and Quay Crane Assignment Problem considering crane movement and setup times

  • Ramon Alvarez-Valdes
  • Juan F. Correcher
  • Federico Perea
    • Categories (Mixed) Integer Linear Programming, Scheduling, Transportation Tags , , ,

    In this technical report we present several Mixed Integer Linear Programming (MILP) models for the Berth Allocation and Quay Crane Assignment Problem (BACASP) considering crane movement and setup time (from now on: BACASP-S). First, we propose a MILP for the continuous-quay time-invariant BACASP in which both berthing time and position variables are continuous. Then, we … Read more

    Total Coloring and Total Matching: Polyhedra and Facets

  • Luca Ferrarini
  • Stefano Gualandi
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Cutting Plane Approaches Tags , , ,

    A total coloring of a graph G = (V, E) is an assignment of colors to vertices and edges such that neither two adjacent vertices nor two incident edges get the same color, and, for each edge, the end-points and the edge itself receive different colors. Any valid total coloring induces a partition of the … Read more

    Total Coloring and Total Matching: Polyhedra and Facets

  • Luca Ferrarini
  • Stefano Gualandi
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Polyhedra Tags , , ,

    A total coloring of a graph G = (V, E) is an assignment of colors to vertices and edges such that neither two adjacent vertices nor two incident edges get the same color, and, for each edge, the end-points and the edge itself receive a different color. Any valid total coloring induces a partition of … Read more

    Lower Bounds on the Size of General Branch-and-Bound Trees

  • Santanu S. Dey
  • Yatharth Dubey
  • Marco Molinaro
    • Categories 0-1 Programming, Branch and Cut Algorithms, Global Optimization Theory Tags , ,

    A \emph{general branch-and-bound tree} is a branch-and-bound tree which is allowed to use general disjunctions of the form $\pi^{\top} x \leq \pi_0 \,\vee\, \pi^{\top}x \geq \pi_0 + 1$, where $\pi$ is an integer vector and $\pi_0$ is an integer scalar, to create child nodes. We construct a packing instance, a set covering instance, and a … Read more

    An Exact Method for Assortment Optimization under the Nested Logit Model

  • Laurent Alfandari
  • Ivana Ljubić
  • Alborz Hassanzadeh
    • Categories Applications - OR and Management Sciences Tags , , , ,

    We study the problem of finding an optimal assortment of products maximizing the expected revenue, in which customer preferences are modeled using a Nested Logit choice model. This problem is known to be polynomially solvable in a specific case and NP-hard otherwise, with only approximation algorithms existing in the literature. For the NP-hard cases, we … Read more

    Matching Algorithms and Complexity Results for Constrained Mixed-Integer Optimal Control with Switching Costs

  • Felix Bestehorn
  • Christian Kirches
    • Categories (Mixed) Integer Nonlinear Programming, Approximation Algorithms Tags , , , ,

    We extend recent work on the performance of the combinatorial integral approximation decomposition approach for Mixed-Integer Optimal Control Problems (MIOCPs) in the presence of combinatorial constraints or switching costs on an equidistant grid. For the time discretized problem, we reformulate the emerging rounding problem in the decomposition approach as a matching problem on a bipartite … Read more

    The Non-Stop Disjoint Trajectories Problem

  • Benno Hoch
  • Frauke Liers
  • Sarah Neumann
  • Francisco Javier Zaragoza Martínez
    • Categories Combinatorial Optimization, Network Optimization Tags , , , , ,

    Consider an undirected network with traversal times on its edges and a set of commodities with connection requests from sources to destinations and release dates. The non-stop disjoint trajectories problem is to find trajectories that fulfill all requests, such that the commodities never meet. In this extension to the \NP-complete disjoint paths problem, trajectories must … Read more

    A branch-and-cut algorithm for the Edge Interdiction Clique Problem

  • Fabio Furini
  • Ivana Ljubić
  • Pablo San Segundo
  • Yanlu Zhao
    • Categories Combinatorial Optimization, Cutting Plane Approaches Tags , , ,

    Given a graph G and an interdiction budget k, the Edge Interdiction Clique Problem (EICP) asks to find a subset of at most k edges to remove from G so that the size of the maximum clique, in the interdicted graph, is minimized. The EICP belongs to the family of interdiction problems with the aim … Read more

    Γ-counterparts for robust nonlinear combinatorial and discrete optimization

  • Dennis Adelhütte
  • Frauke Liers
    • Categories Robust Optimization Tags , , , , ,

    Γ-uncertainties have been introduced for adjusting the degree of conservatism ofrobust counterparts of (discrete) linear optimization problems under interval uncertainty. Thisarticle’s contribution is a generalization of this approach to (mixed-integer) nonlinear optimizationproblems. We focus on the cases in which the uncertainty is linear but also derive formulationsfor the general case. We present cases where the … Read more

    One transfer per patient suffices: Structural insights about patient-to-room assignment

  • Christina Büsing
  • Sigrid Knust
  • Tabea Brandt
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization Tags , , ,

    While many heuristics have been proposed for the problem of patient-to-room assignment (PRA) with a large variety of different practical constraints, a thorough investigation of the problem’s structure itself has been neglected so far. Therefore, in this paper, we present insights about the basic, underlying combinatorial problem of PRA. At first we consider the problem … Read more