combinatorial optimization

Attention Mechanisms in Physics-Inspired Graph Neural Networks for the Max-Cut Problem

Categories Combinatorial Optimization, Graphs and Matroids, Network Optimization Tags , , ,

Physics-Inspired Graph Neural Networks (PI-GNNs) reformulate MAX-CUT as QUBO energy minimization, training a GNN to produce soft binary node assignments without labeled data. The baseline PI-GCN uses static, degree-normalized aggregation, while its attention-augmented counterpart PI-GAT—built on GATv2—introduces additional hyperparameters whose effects remain uncharacterized. This paper addresses that gap through controlled experiments on five Gset benchmark … Read more

The colored knapsack problem: structural properties and exact algorithms

Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Dynamic Programming Tags , , , ,

We introduce and study a novel generalization of the classical Knapsack Problem (KP), called the Colored Knapsack Problem (CKP). In this problem, the items are partitioned into classes of colors and the packed items need to be ordered such that no consecutive items are of the same color. We establish that the problem is weakly … Read more

Robust combinatorial optimization problems under locally budgeted interdiction uncertainty against the objective function and covering constraints

Categories Combinatorial Optimization, Robust Optimization Tags ,

Recently robust combinatorial optimization problems with budgeted interdiction uncertainty affecting cardinality-based constraints or objective were considered by presenting, comparing and experimenting with compact formulations. In this paper we present a compact formulation for the case in which locally budgeted interdiction uncertainty affects the objective function and covering constraints simultaneously. ArticleDownload View PDF

Machine Learning Algorithms for Assisting Solvers for Decision Optimization Problems

Categories Applications - OR and Management Sciences, Integer Programming, Optimization in Data Science Tags , , , , , , , ,

Combinatorial decision problems lie at the intersection of Operations Research (OR) and Artificial Intelligence (AI), encompassing structured optimization tasks such as submodular selection, dynamic programming, planning, and scheduling. These problems exhibit exponential growth in decision complexity, driven by interdependent choices coupled through logical, temporal, and resource constraints.  Classical optimization frameworks—including integer programming, submodular optimization, and … Read more

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

Categories Graphs and Matroids, Integer Programming Tags , ,

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

Categories Combinatorial Optimization, Convex Optimization, Semi-definite Programming Tags , , , ,

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

Categories Combinatorial Optimization, Data Science Algorithms, Game Theory Tags , , ,

This paper develops a unified game-theoretical framework for data classification and network discovery based on pairwise influences in multivariate categorical choices. Data points, interpreted as individuals, are connected through a signed weighted graph and take values according to a voting rule that aggregates the influence of attractive (friend-like) and repulsive (enemy-like) neighbors. The framework consists … Read more

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

Categories (Mixed) Integer Nonlinear Programming, Network Optimization, Semi-definite Programming Tags , , , ,

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

Categories Approximation Algorithms, Combinatorial Optimization, Robust Optimization Tags , , , ,

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