The role of rationality in integer-programming relaxations

For a finite set $X \subset \Z^d$ that can be represented as $X = Q \cap \Z^d$ for some polyhedron $Q$, we call $Q$ a relaxation of $X$ and define the relaxation complexity $\rc(X)$ of $X$ as the least number of facets among all possible relaxations $Q$ of $X$. The rational relaxation complexity $\rc_\Q(X)$ restricts … Read more

Complexity of cutting planes and branch-and-bound in mixed-integer optimization

We investigate the theoretical complexity of branch-and-bound (BB) and cutting plane (CP) algorithms for mixed-integer optimization. In particular, we study the relative efficiency of BB and CP, when both are based on the same family of disjunctions. We extend a result of Dash to the nonlinear setting which shows that for convex 0/1 problems, CP … Read more

Scanning integer points with lex-inequalities: A finite cutting plane algorithm for integer programming with linear objective

We consider the integer points in a unimodular cone K ordered by a lexicographic rule defined by a lattice basis. To each integer point x in K we associate a family of inequalities (lex-inequalities) that defines the convex hull of the integer points in K that are not lexicographically smaller than x. The family of … Read more

Optimal cutting planes from the group relaxations

We study quantitative criteria for evaluating the strength of valid inequalities for Gomory and Johnson’s finite and infinite group models and we describe the valid inequalities that are optimal for these criteria. We justify and focus on the criterion of maximizing the volume of the nonnegative orthant cut off by a valid inequality. For the … Read more

The structure of the infinite models in integer programming

The infinite models in integer programming can be described as the convex hull of some points or as the intersection of half-spaces derived from valid functions. In this paper we study the relationships between these two descriptions. Our results have implications for finite dimensional corner polyhedra. One consequence is that nonnegative continuous functions suffice to … Read more

Removing critical nodes from a graph: complexity results and polynomial algorithms for the case of bounded treewidth

We consider the problem of deleting a limited number of nodes from a graph in order to minimize a connectivity measure between the surviving nodes. We prove that the problem is $NP$-complete even on quite particular types of graph, and define a dynamic programming recursion that solves the problem in polynomial time when the graph … Read more

Branch and cut algorithms for detecting critical nodes in undirected graphs

In this paper we deal with the critical node problem, where a given number of nodes has to be removed from an undirected graph in order to maximize the disconnections between the node pairs of the graph. We propose an integer linear programming model with a non-polynomial number of constraints but whose linear relaxation can … Read more

Complexity of the Critical Node Problem over trees

In this paper we deal with the Critical Node Problem (CNP), i.e., the problem of searching for a given number K of nodes in a graph G, whose removal minimizes the number of connections between pairs of nodes in the residual graph. While the NP-completeness of this problem for general graphs has been already established … Read more