Full strong-branching (henceforth referred to as strong-branching) is a well-known variable selection rule that is known experimentally to produce significantly smaller branch-and-bound trees in comparison to all other known variable selection rules. In this paper, we attempt an analysis of the performance of the strong-branching rule both from a theoretical and a computational perspective. On … Read more
We present an algebraic characterization of perfect graphs, i.e., graphs for which the clique number and the chromatic number coincide for every induced subgraph. We show that a graph is perfect if and only if certain nonnegative polynomials associated with the graph are sums of squares. As a byproduct, we obtain several infinite families of … Read more
De Klerk and Pasechnik (2002) introduced the bounds $\vartheta^{(r)}(G)$ ($r\in \mathbb{N}$) for the stability number $\alpha(G)$ of a graph $G$ and conjectured exactness at order $\alpha(G)-1$: $\vartheta^{(\alpha(G)-1)}(G)=\alpha(G)$. These bounds rely on the conic approximations $\mathcal{K}_n^{(r)}$ by Parrilo (2000) for the copositive cone $\text{COP}_n$. A difficulty in the convergence analysis of $\vartheta^{(r)}$ is the bad behaviour … Read more
In this paper we study the rank of polytopes contained in the 0-1 cube with respect to $t$-branch split cuts and $t$-dimensional lattice cuts for a fixed positive integer $t$. These inequalities are the same as split cuts when $t=1$ and generalize split cuts when $t > 1$. For polytopes contained in the $n$-dimensional 0-1 … Read more
A small polygon is a polygon of unit diameter. The maximal width of an equilateral small polygon with $n=2^s$ vertices is not known when $s \ge 3$. This paper solves the first open case and finds the optimal equilateral small octagon. Its width is approximately $3.24\%$ larger than the width of the regular octagon: $\cos(\pi/8)$. … Read more
This paper introduces the multiphase course timetabling problem and presents mathematical formulations and effective solution algorithms to solve it in a real case study. Consider a pool of lessons and a number of students who are required to take a subset of these lessons to graduate. Each lesson consists of a predetermined and consecutive sequence … Read more
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 article we address the problem of finding lower bounds for small Ramsey numbers $R(m,n)$ using circulant graphs. Our constructive approach is based on finding feasible colorings of circulant graphs using Integer Programming (IP) techniques. First we show how to model the problem as a Stackelberg game and, using the tools of bilevel optimization, … Read more
In this paper, we compute the tightest possible bounds on the probability that the optimal value of a combinatorial optimization problem in maximization form with a random objective exceeds a given number, assuming only knowledge of the marginal distributions of the objective coefficient vector. The bounds are “extremal” since they are valid across all joint … 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