Strength of the Upper Bounds for the Edge-Weighted Maximum Clique Problem

We theoretically and computationally compare the strength of the two main upper bounds from the literature on the optimal value of the Edge-Weighted Maximum Clique Problem (EWMCP). We provide a set of instances for which the ratio between either of the two upper bounds and the optimal value of the EWMCP is unbounded. This result … Read more

Stable Set Polytopes with Rank |V(G)|/3 for the Lovász-Schrijver SDP Operator

We study the lift-and-project rank of the stable set polytope of graphs with respect to the Lovász–Schrijver SDP operator \( \text{LS}_+ \) applied to the fractional stable set polytope. In particular, we show that for every positive integer \( \ell \), the smallest possible graph with \( \text{LS}_+ \)-rank \( \ell \) contains \( 3\ell … Read more

A Generalized Voting Game for Categorical Network Choices

This paper presents a game-theoretical framework for data classification and network discovery, focusing on pairwise influences in multivariate choices. The framework consists of two complementary games in which individuals, connected through a signed weighted graph, exhibit network similarity. A voting rule captures the influence of an individual’s neighbors, categorized as attractive (friend-like) or repulsive (enemy-like), … Read more

Spanning and Splitting: Integer Semidefinite Programming for the Quadratic Minimum Spanning Tree Problem

In the quadratic minimum spanning tree problem (QMSTP) one wants to find the minimizer of a quadratic function over all possible spanning trees of a graph. We present a formulation of the QMSTP as a mixed-integer semidefinite program exploiting the algebraic connectivity of a graph. Based on this formulation, we derive a doubly nonnegative relaxation … Read more

Robust combinatorial optimization problems with knapsack constraints under interdiction uncertainty

We present an algorithm for finding near-optimal solutions to robust combinatorial optimization problems with knapsack constraints under interdiction uncertainty. We incorporate a heuristic for generating feasible solutions in a standard row generation approach. Experimental results are presented for set covering, simple plant location, and min-knapsack problems under a discrete-budgeted interdiction uncertainty set introduced in this … Read more

On the integrality gap of the Complete Metric Steiner Tree Problem via a novel formulation

In this work, we study the metric Steiner Tree problem on graphs focusing on computing lower bounds for the integrality gap of the bi-directed cut (BCR) formulation and introducing a novel formulation, the Complete Metric (CM) model, specifically designed to address the weakness of the BCR formulation on metric instances. A key contribution of our … 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 of … Read more

A Polyhedral Characterization of Linearizable Quadratic Combinatorial Optimization Problems

We introduce a polyhedral framework for characterizing instances of quadratic combinatorial optimization programs (QCOPs) that are linearizable, meaning that the quadratic objective can be equivalently rewritten as linear in such a manner that preserves the objective function value at all feasible solutions. In particular, we show that an instance is linearizable if and only if … Read more

Structural Insights and an IP-based Solution Method for Patient-to-room Assignment Under Consideration of Single Room Entitlements

Patient-to-room assignment (PRA) is a scheduling problem in decision support for large hospitals. This work proposes Integer Programming (IP) formulations for dynamic PRA, where either full, limited or uncertain information on incoming patients is available. The applicability is verified through a computational study. Results indicate that large, real world instances can be solved to a … Read more

Branch-and-Bound versus Lift-and-Project Relaxations in Combinatorial Optimization

In this paper, we consider a theoretical framework for comparing branch-and-bound with classical lift-and-project hierarchies. We simplify our analysis of streamlining the definition of branch-and-bound. We introduce “skewed $k$-trees” which give a hierarchy of relaxations that is incomparable to that of Sherali-Adams, and we show that it is much better for some instances. We also … Read more