\(\) 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
\(\) 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
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
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
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
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
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
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
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
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