combinatorial optimization

A regular perspective on solving the irregular strip packing problem with the dotted-board model: a mosaic approach and a divide-and-conquer strategy

Categories Combinatorial Optimization, Integer Programming Tags , , , ,

Since its introduction in 2013, the dotted-board model has been widely used by the cutting and packing research community to tackle irregular packing problems. However, despite its popularity, little research has aimed at improving its performance when solved via off-the-shelf integer programming solvers, beyond the known strategy of merging pairwise incompatibility constraints into clique constraints … Read more

Linearizable Instances of the Quadratic Minimum Spanning Tree Problem on 3-Connected Graphs

Categories 0-1 Programming, Combinatorial Optimization, Quadratic Programming Tags , , ,

An instance of the quadratic minimum spanning tree problem (QMSTP) is called linearizable if it can be rewritten as an instance of the linear minimum spanning tree problem in such a way that the objective function value is preserved at all feasible solutions. Previous work has shown that a sufficient condition for linearizability is that … Read more

On Spanning-Tree Integrality and a new Branching Rule for the Maximum Cut Problem

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

State-of-the-art exact methods for the Maximum Cut problem are based on solving linear and semidefinite programming relaxations embedded into a branch-and-bound algorithm. For linear programming formulations, it was shown recently that it is thereby sufficient to enforce the integrality of the variables associated with the edges of a spanning tree. Our first contribution is to … Read more

An Integer Programming Approach to Compute Lower Bounds for Ramsey Numbers Using Circulant Graphs

Categories Branch and Cut Algorithms, Combinatorial Optimization, Integer Programming Tags , , , ,

The Ramsey number R(m,n) is the smallest order at which every red-blue edge coloring of a complete graph must contain a blue clique (a complete subgraph) of size m or a red clique of size n. Determining these numbers exactly is extremely hard, and even certifying a lower bound requires exhibiting an explicit coloring that … Read more

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 three 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 any of the three upper bounds and the optimal value of the EWMCP is unbounded, showing that … Read more