The relationship between locations and their connections can be sometimes modelled using a generalization of the vertex cover problem. In this talk, we will present a block decomposition algorithm for a variant of the problem and discuss some preliminary numerical results. The efficiency of this method will be compared to non-decomposition procedures on several computational experiments. Finally, we will also propose further improvements and research directions.

In some contexts, we can model the relationship between locations and their connections using some extensions of the vertex cover problem. In this talk, we revisit some of these extensions, provide preliminary results that can be used for solutions methods, and try to connect them with well-known polyhedra such as the boolean quadric polytope. We present computational results from a branch-and-cut algorithm in which we show the applicability of our proposals.

We are interested in determining the set of objective vectors under which the given integer solution stays optimal. The set of all such objective vectors forms the normal cone at the solution with respect to the integer hull. Since the integer hull is not known in general and expensive to calculate, we are looking for an efficient way to calculate such cones or rather its polar, the radial cone.

We present an approach which calculates all facet-defining inequalities of the radial cone. The algorithm combines existing algorithms modified to fit the purpose. Since we only require the existence of an optimization oracle, we can calculate the radial cone for all linear optimization problems over polyhedra, including mixed integer problems.

The general idea of our algorithm is to utilize an optimization oracle to calculate – preferably neighboring – solutions and incrementally extend a current sub cone of the radial cone with these solutions.
We will address the handling of potential problematic cases such as unbounded directions and non-full-dimensional polyhedra. Finally, we will use this algorithm to analyze the degeneracy of ILPs and present first computational results.

Given a finite set N of points in the plane called "terminals," the Euclidean Steiner tree problem seeks a set of line segments connecting all the terminals having minimum total Euclidean length. The shortest such tree usually requires additional Steiner points serving as junctions that reduce the total interconnect length. In an optimal tree, Steiner points always have degree 3, with incident line segments meeting at 120-degree angles. This classical NP-hard problem is one of the oldest optimization problems in all of mathematics.

We describe a recently solved instance containing 1,000,000 terminals uniformly distributed in the unit square. It has been called "the largest classical NP-hard problem instance ever solved to optimality."

This computational breakthrough resulted from mathematical analyses called "strength indicators," which provide a quantitative assessment of the computational "strength" of a given inequality with respect to the underlying polyhedron over which optimization is performed. These indicators revealed previously unknown properties of the Spanning Tree in Hypergraph Polytope which were exploited to remarkable computational advantage.