## Stable Set Polytopes with High Lift-and-Project Ranks for the Lovász-Schrijver SDP Operator

 We study the lift-and-project rank of the stable set polytopes of graphs with respect to the Lovász-Schrijver SDP operator $$\text{LS}_+$$, with a particular focus on a search for relatively small graphs with high $$\text{LS}_+$$-rank (the least number of iterations of the $$\text{LS}_+$$ operator on the fractional stable set polytope to compute … Read more

## The Hamiltonian p-median Problem: Polyhedral Results and Branch-and-Cut Algorithm

 In this paper we study the Hamiltonian $$p$$-median problem, in which a weighted graph on $$n$$ vertices is to be partitioned into $$p$$ simple cycles of minimum total weight. We introduce two new families of valid inequalities for a formulation of the problem in the space of natural edge variables. Each one of the … Read more

## A Combinatorial Flow-based Formulation for Temporal Bin Packing Problems

We consider two neighboring generalizations of the classical bin packing problem: the temporal bin packing problem (TBPP) and the temporal bin packing problem with fire-ups (TBPP-FU). In both cases, the task is to arrange a set of given jobs, characterized by a resource consumption and an activity window, on homogeneous servers of limited capacity. To … Read more

## Temporal Bin Packing with Half-Capacity Jobs

Motivated by applications in cloud computing, we study a temporal bin packing problem with jobs that occupy half of a bin’s capacity. An instance is given by a set of jobs, each with a start and end time during which it must be processed, i.e., assigned to a bin. A bin can accommodate two jobs … Read more

## On Aligning Non-Order-Associated Binary Decision Diagrams.

Recent studies employ collections of binary decision diagrams (BDDs) to solve combinatorial optimization problems. This paper focuses on the problem of optimally aligning two BDDs, i.e., transforming them to enforce a common order of variables while keeping the total size of the diagrams as small as possible. We address this problem, which is known to … Read more

## Dendrograms, Minimum Spanning Trees and Feature Selection

Feature selection is a fundamental process to avoid overfitting and to reduce the size of databases without significant loss of information that applies to hierarchical clustering. Dendrograms are graphical representations of hierarchical clustering algorithms that for single linkage clustering can be interpreted as minimum spanning trees in the complete network defined by the database. In … Read more

## CliSAT: a SAT-based exact algorithm for hard maximum clique problems

Given a graph, the maximum clique problem (MCP) asks for determining a complete subgraph with the largest possible number of vertices. We propose a new exact algorithm, called CliSAT, to solve the MCP to proven optimality. This problem is of fundamental importance in graph theory and combinatorial optimization due to its practical relevance for a … Read more

## An Efficient Tabu Search Algorithm for the Tool Indexing Problem

In this paper, we look at the tool indexing problem in which a single copy of each tool is allowed in the tool magazine. We develop problem specific methods to search the neighborhood efficiently and design a Tabu Search algorithm based on them. Computational experiments show that our algorithm is competent. Citation Indian Institute of … Read more

## Absolute regret of implicitly defined sets for combinatorial optimization problems

We consider combinatorial optimization problems with interval uncertainty in the cost vector. Recently a new approach was developed to deal with such uncertainties: instead of a single one absolute robust solution, obtained by solving a min max problem, a set of cardinality predefined and minimal absolute regret, obtained by solving a min max min problem, … Read more

## Facets of the Total Matching Polytope for bipartite graphs

The Total Matching Polytope generalizes the Stable Set Polytope and the Matching Polytope. In this paper, we give the perfect formulation for Trees and we derive two new families of valid inequalities, the balanced biclique inequalities which are always facet-defining and the non-balanced lifted biclique inequalities obtained by a lifting procedure, which are facet-defining for … Read more