We study the lift-and-project relaxations of the stable set polytope of graphs generated by \( \text{LS}_+ \), the SDP lift-and-project operator devised by Lovász and Schrijver. In particular, we focus on searching for \( \ell \)-minimal graphs, which are graphs on $3\ell$ vertices whose stable set polytope has rank \( \ell \) with respect to … Read more
We study weighted, capacitated cost-sharing games on parallel-link networks, also known as bin packing games. We focus on an integer-splittable variant in which items of varying sizes can be divided into integer units and assigned to bins with heterogeneous capacities and costs. Although this setting has practical relevance, it remains largely unexplored in the context … Read more
Optimization problems with norm-bounding constraints appear in various applications, from portfolio optimization to machine learning, feature selection, and beyond. A widely used variant of these problems relaxes the norm-bounding constraint through Lagrangian relaxation and moves it to the objective function as a form of penalty or regularization term. A challenging class of these models uses … Read more
A polytope $P\subseteq [0,1]^n$ is said to have the \emph{persistency} property if for every vector $c\in \R^{n}$ and every $c$-optimal point $x\in P$, there exists a $c$-optimal integer point $y\in P\cap \{0,1\}^n$ such that $x_i = y_i$ for each $i \in \{1,\dots,n\}$ with $x_i \in \{0,1\}$. In this paper, we consider a relaxation of the … Read more
The Chance-Constrained Parallel Machine Scheduling Problem (CC-PMSP) assigns jobs with uncertain processing times to machines, ensuring that each machine’s availability constraints are met with a certain probability. We present a decomposition approach where the master problem assigns jobs to machines, and the subproblems schedule the jobs on each machine while verifying the solution’s feasibility under … Read more
In the continuous time service network design problem, a freight carrier decides the path of shipments in their network as well as the dispatch times of the vehicles transporting the shipments. State-of-the-art algorithms to solve this problem are based on the dynamic discretization discovery framework. These algorithms solve a relaxation of the problem using a … Read more
We study the Regularized A-Optimal Design (RAOD) problem, which selects a subset of \(k\) experiments to minimize the inverse of the Fisher information matrix, regularized with a scaled identity matrix. RAOD has broad applications in Bayesian experimental design, sensor placement, and cold-start recommendation. We prove its NP-hardness via a reduction from the independent set problem. … Read more
We address the Undirected Team Orienteering Arc Routing Problem (UTOARP). In this problem, demand is placed at some edges of a given undirected graph and served demand edges produce a profit. Feasible routes must start and end at a given depot and there is a time limit constraint on the maximum duration of each route. … Read more
Positive spanning sets (PSSs) are families of vectors that span a given linear space through non-negative linear combinations. Despite certain classes of PSSs being well understood, a complete characterization of PSSs remains elusive. In this paper, we explore a relatively understudied relationship between positive spanning sets and strongly edge-connected digraphs, in that the former can … Read more
In this work, we present the first 2-index stage-based formulation for the Flying Sidekick Traveling Salesman Problem (FSTSP). Additionally, we propose a Construct-Merge-Solve & Adapt (CMSA) algorithm designed to generate high-quality feasible solutions. Experimental results demonstrate that the proposed algorithm consistently produces good solutions in a fraction of the time required by state-of-the-art mixed-integer linear … Read more