\(\) A short, simple, and self-contained proof is presented showing that $n$-th lifting for the max-cut-polytope is exact. The proof re-derives the known observations that the max-cut-polytope is the projection of a higher-dimensional regular simplex and that this simplex coincides with the $n$-th semidefinite lifting. An extension to reduce the dimension of higher order liftings … 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 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
We propose a successive generation of cutting inequalities for binary quadratic optimization problems. Multiple cutting inequalities are successively generated for the convex hull of the set of the optimal solutions $\subset \{0, 1\}^n$, while the standard cutting inequalities are used for the convex hull of the feasible region. An arbitrary linear inequality with integer coefficients … Read more
The computational performance of inductive linearizations for binary quadratic programs in combination with a mixed-integer programming solver is investigated for several combinatorial optimization problems and established benchmark instances. Apparently, a few of these are solved to optimality for the first time. Citation preprint (no internal series / number): University of Bonn, Germany June 11, 2021 … Read more
We propose a method to generate cutting-planes from multiple covers of knapsack constraints. The covers may come from different knapsack inequalities if the weights in the inequalities form a totally-ordered set. Thus, we introduce and study the structure of a totally-ordered multiple knapsack set. The valid multi-cover inequalities we derive for its convex hull have … Read more
Binary polynomial optimization is equivalent to the problem of minimizing a linear function over the intersection of the multilinear set with a polyhedron. Many families of valid inequalities for the multilinear set are available in the literature, though giving a polyhedral characterization of the convex hull is not tractable in general as binary polynomial optimization … 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
It is well-established that increased product visibility to shoppers leads to higher sales for retailers. In this study, we propose an optimization methodology which assigns product categories and subcategories to store locations and sublocations to maximize the overall visibility of products to shoppers. The methodology is hierarchically developed to meet strategic and tactical layout planning … Read more