Abstract We analyze integer programming formulations for determining the treewidth of a graph that are based on perfect elimination orderings. For the first time, we prove structural properties that explain their limitations in providing convenient lower bounds and show how the latter are constituted. Moreover, we investigate a flow metric approach that proved promising to achieve approximation guarantees for the pathwidth of a graph, and we show why these techniques cannot be carried over to improve the addressed treewidth formulations. In addition, we present two complementary formulations for treewidth that employ positional rather than relational variables. Via computational experiments, we provide an impression on the quality and proportionality of the lower bounds on the treewidth obtained with different relaxations of perfect elimination ordering formulations.

While the Maximum Cut Problem and Unconstrained Binary Quadratic Optimization are of high interest in the scientific community and gain increasing importance, state-of-the-art solvers for these problems are publicly available, yet not for sparse instances of larger scale. We present the novel solver McSparse to fill this gap. It is installed as an internet service similar to the well-known services Biq Mac and BiqCrunch. We explain details of the algorithmic innovations based on integer linear programming and polyhedral combinatorics leading to the branch-and-cut algorithm implemented in McSparse. Substantial improvements with respect to former such approaches are demonstrated and the sustained performance is compared to those of other state-of-the-art methods using a broad set of benchmark instances.

The exact solution of the NP-hard (nondeterministic polynomial-time hard) maximum cut problem is important in many applications across, for example, physics, chemistry, neuroscience, and circuit layout—which is also due to its equivalence to the unconstrained binary quadratic optimization problem. Leading solution methods are based on linear or semidefinite programming and require the separation of the so-called odd-cycle inequalities. In their groundbreaking research, F. Barahona and A. R. Mahjoub have given an informal description of a polynomial-time algorithm for this problem. As pointed out recently, however, additional effort is necessary to guarantee that the inequalities obtained correspond to facets of the cut polytope. In this paper, we shed more light on a so enhanced separation procedure and investigate experimentally how it performs in comparison with an ideal setting where one could even employ the sparsest, most violated, or geometrically most promising facet-defining odd-cycle inequalities. Summary of Contribution: This paper aims at a better capability to solve binary quadratic optimization or maximum cut problems and their various applications using integer programming techniques. To this end, the paper describes enhancements to a well-known algorithm for the central separation problem arising in this context; it is demonstrated experimentally that these enhancements are worthwhile from a computational point of view. The linear relaxations of the aforementioned problems are typically solved using fewer iterations and cutting planes than with a nonenhanced approach. It is also shown that the enhanced procedure is only slightly inferior to an ideal, enumerative, and, in practice, intractable global cutting-plane selection.

Solving the NP-hard Maximum Cut or Binary Quadratic Optimization Problem to optimality is important in many applications including Physics, Chemistry, Neuroscience, and Circuit Layout. The leading approaches based on linear/semidefinite programming require the separation of so-called odd-cycle inequalities for solving relaxations within their associated branch-and-cut frameworks. In their groundbreaking work, F. Barahona and A.R. Mahjoub have given an informal description of a polynomial-time separation procedure for the odd-cycle inequalities. Since then, the odd-cycle separation problem has broadly been considered solved. However, as we reveal, a straightforward implementation is likely to generate inequalities that are not facet-defining and have further undesired properties. Here, we present a more detailed analysis, along with enhancements to overcome the associated issues efficiently. In a corresponding experimental study, it turns out that these are worthwhile, and may speed up the solution process significantly.

We present an exact approach to the General Offset Assignment problem arising in the domain of address code generation for application specific and digital signal processors. General Offset Assignment is composed of two subproblems, namely to find a permutation of variables in memory and to select a responsible address register for each access to one of these variables. Our method is a combination of established techniques to solve both subproblems using integer linear programming. To the best of our knowledge, it is the first approach capable of solving almost all instances of the established OffsetStone benchmark set to global optimality within reasonable time. We provide a first comprehensive evaluation of the quality of several state-of-the-art heuristics relative to the optimal solutions.