We study the Knapsack Problem with Conflicts, a generalization of the Knapsack Problem in which a set of conflicts specifies pairs of items which cannot be simultaneously selected. In this work, we propose a novel combinatorial branch-and-bound algorithm for this problem based on an n-ary branching...
01a Articolo in rivista
-
-
A proper coloring of a given graph is an assignment of a positive integer number (color) to each vertex such that two adjacent vertices receive different colors. This paper studies the Minimum Sum Coloring Problem (MSCP), which asks for finding a proper coloring while minimizing the sum of the...
-
Given a graph G and an interdiction budget k∈N, the Edge Interdiction Clique Problem (EICP) asks to find a subset of at most k edges to remove from G so that the size of the maximum clique, in the interdicted graph, is minimized. The EICP belongs to the family of interdiction problems with the aim...
-
The family of critical node detection problems asks for finding a subset of vertices, deletion of which minimizes or maximizes a predefined connectivity measure on the remaining network. We study a problem of this family called the k-vertex cut problem. The problem asks for determining the minimum...
-
We study an extension of the classical Bin Packing Problem, where each item consumes the bin capacity during a given time window that depends on the item itself. The problem asks for finding the minimum number of bins to pack all the items while respecting the bin capacity at any time instant. A...
-
This paper addresses the problem of optimal planning of a liner service for a barge container shipping company. Given estimated weekly demands between pairs of ports, our goal is to determine the subset of ports to be called and the amount of containers to be shipped between each pair of ports, so...
-
Given a graph G and an interdiction budget k, the Maximum Clique Interdiction Problem asks to find a subset of at most k vertices to remove from G so that the size of the maximum clique in the remaining graph is minimized. This problem has applications in many areas, such as crime detection,...
-
We propose an exact lexicographic dynamic programming pricing algorithm for solving the Fractional Bin Packing Problem with column generation. The new algorithm is designed for generating maximal columns of minimum reduced cost which maximize, lexicographically, one of the measures of maximality we...
-
We study the maximum edge-weighted clique problem, a problem related to the maximum (vertex-weighted) clique problem which asks for finding a complete subgraph (i.e., a clique) of maximum total weight on its edges. The problem appears in a wide range of applications, including bioinformatics,...
-
We perform a theoretical and computational study of the classical linearisation techniques (LT) and we propose a new LT for binary quadratic problems (BQPs). We discuss the relations between the linear programming (LP) relaxations of the considered LT for generic BQPs. We prove that for a specific...