Extended Formulations for Control Languages Defined by Finite-State Automata

Many discrete optimal control problems feature combinatorial constraints on the possible switching patterns, a common example being minimum dwell-time constraints. After discretizing to a finite time grid, for these and many similar types of constraints, it is possible to give a description of the convex hull of feasible (finite-dimensional) binary controls via extended formulations. In … Read more

Edge expansion of a graph: SDP-based computational strategies

Computing the edge expansion of a graph is a famously hard combinatorial problem for which there have been many approximation studies. We present two variants of exact algorithms using semidefinite programming (SDP) to compute this constant for any graph. The first variant uses the SDP relax- ation first to reduce the search space considerably. One … Read more

Solving the three-dimensional open-dimension rectangular packing problem: a constraint programming model

In this paper, we address the three-dimensional open-dimension rectangular packing problem (3D-ODRPP). This problem addresses a set of rectangular boxes of given dimensions and a rectangular container of open dimensions. The objective is to pack all boxes orthogonally into the container while minimizing the container volume. Real-world applications of the 3D-ODRPP arise in production systems … Read more

Maximizing a Monotone Submodular Function Under an Unknown Knapsack Capacity

Consider the problem of maximizing a nondecreasing submodular function defined on a set of weighted items under an unknown knapsack capacity. Assume items are packed sequentially into the knapsack and the knapsack capacity is accessed through an oracle that answers whether an item fits into the currently packed knapsack. If an item is tried to … Read more

A Subspace Minimization Barzilai-Borwein Method for Multiobjective Optimization Problems

Nonlinear conjugate gradient methods have recently garnered significant attention within the multiobjective optimization community. These methods aim to maintain consistency in conjugate parameters with their single-objective optimization counterparts. However, the preservation of the attractive conjugate property of search directions remains uncertain, even for quadratic cases, in multiobjective conjugate gradient methods. This loss of interpretability of … Read more

The if-then Polytope: Conditional Relations over Multiple Sets of Binary Variables

Inspired by its occurrence as a substructure in a stochastic railway timetabling model, we study in this work a special case of the bipartite boolean quadric polytope. It models conditional relations across three sets of binary variables, where selections within two “if” sets imply a choice in a corresponding “then” set. We call this polytope … Read more

The Multi-Stop Station Location Problem: Exact Approaches

The multi-stop station location problem (MSLP) aims to place stations such that a set of trips is feasible with respect to length bounds while minimizing cost. Each trip consists of a sequence of stops that must be visited in a given order, and a length bound that controls the maximum length that is possible without … Read more

New cuts and a branch-cut-and-price model for the Multi Vehicle Covering Tour Problem

\(\) The Multi-Vehicle Covering Tour Problem (m-CTP) involves a graph in which the set of vertices is partitioned into a depot and three distinct subsets representing customers, mandatory facilities, and optional facilities. Each customer is linked to a specific subset of optional facilities that define its coverage set. The goal is to determine a set … Read more