This paper introduces a computational method for generating metric Travelling Salesperson Problem (TSP) instances having a large integrality gap. The method is based on the solution of an NP-hard problem, called IH-OPT, that takes in input a fractional solution of the Subtour Elimination Problem (SEP) on a TSP instance and compute a TSP instance having … Read more
In this paper, we present a novel scheduling problem, the stem cell culturing problem (SCP), which is identified in an attempt to improve the productivity of a manufacturing system producing a commercialized autologous stem cell therapeutic product for treating an incurable disease. For a given therapeutic product along with the corresponding manufacturing process, which is … Read more
In this work, we consider the integrated problem of locomotive scheduling and driver rostering in rail freight companies. Our aim is to compute an optimal simultaneous assignment of locomotives and drivers to the trains listed in a given order book. Mathematically, this leads to the combination of a set-packing problem with compatibility constraints and a … Read more
Cliques and their generalizations are frequently used to model “tightly knit” clusters in graphs and identifying such clusters is a popular technique used in graph-based data mining. One such model is the $s$-club, which is a vertex subset that induces a subgraph of diameter at most $s$. This model has found use in a variety … Read more
The s-clubs model cohesive social subgroups as vertex subsets that induce subgraphs of diameter at most s. In defender-attacker settings, for low values of s, they can represent tightly-knit communities whose operation is undesirable for the defender. For instance, in online social networks, large communities of malicious accounts can effectively propagate undesirable rumors. In this … Read more
This paper explores new solution approaches for the graph partitioning problem. While the classic formulations for graph partitioning are compact, they either suffer from a poor relaxation, symmetry, or contain a cubic number of constraints regardless of the graph density. These shortcomings often result in poor branch-and-bound performance. We approach this problem from perspective of … Read more
Real-world problems are often nonconvex and involve integer variables, representing vexing challenges to be tackled using state-of-the-art solvers. We introduce a mathematical identity-based reformulation of a class of polynomial integer nonlinear optimization (PINLO) problems using a technique that linearizes polynomial functions of separable and bounded integer variables of any degree. We also introduce an alternative … Read more
The eps-constraint method is a well-known scalarization technique used for multiobjective optimization. We explore how to properly define the step size parameter of the method in order to guarantee its exactness when dealing with problems having two nonlinear objective functions and integrality constraints on the variables. Under specific assumptions, we prove that the number of … Read more
This work introduces a complex variant of the timetabling problem, which is motivated by the case of Italian schools. The new requirements enforce to (i) provide the same idle times for teachers, (ii) avoid consecutive \emph{heavy} days, (iii) limit daily multiple lessons for the same class, (iv) introduce shorter time units to differentiate entry and … Read more
A total coloring of a graph G = (V, E) is an assignment of colors to vertices and edges such that neither two adjacent vertices nor two incident edges get the same color, and, for each edge, the end-points and the edge itself receive different colors. Any valid total coloring induces a partition of the … Read more