Christopher Hojny

Eindhoven University of Technology

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Trends

Author Order

Document Type

Co-Authors

Marc E. Pfetsch

Technical University of Darmstadt

Jasper van Doornmalen

Eindhoven University of Technology

Gennadiy Averkov

Brandenburg University of Technology Cottbus-Senftenberg

Thorsten Koch

Zuse Institute Berlin

Ksenia Bestuzheva

Zuse Institute Berlin

Leon Eifler

Zuse Institute Berlin

Yuji Shinano

Zuse Institute Berlin

Ambros Gleixner

Zuse Institute Berlin

Matthias Schymura

Brandenburg University of Technology Cottbus-Senftenberg

Katrin Halbig

Friedrich-Alexander-Universität Erlangen-Nürnberg

Cooperative Institutions

Zuse Institute Berlin

Eindhoven University of Technology

Technische Universität Berlin

Friedrich-Alexander-Universität Erlangen-Nürnberg

University of Twente

Technical University of Darmstadt

RWTH Aachen University

Center for Discrete Mathematics and Theoretical Computer Science

Universität Trier

KU Leuven

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Field

A Unified Framework for Symmetry Handling

arXiv (Cornell University) (2022)

Jasper van Doornmalen Christopher Hojny

Handling symmetries in optimization problems is essential for devising efficient solution methods. In this article, we present a general framework that captures many of the already existing symmetry handling methods. While these methods are mostly discussed independently from each other, our framework allows to apply different methods simultaneously and thus outperforming their individual effect. Moreover, most existing symmetry handling methods only apply to binary variables. Our framework allows to easily generalize these methods to general variable types. Numerical experiments confirm that our novel framework is superior to the state-of-the-art symmetry handling methods as implemented in the solver SCIP on a broad set of instances.

Solver

State variable

10.48550/arxiv.2211.01295

Cite

Citations (0)

Handling Sub-symmetry in Integer Programming using Activation Handlers

AIRO Springer series/AIRO Springer Series (2024)

Christopher Hojny T Tom Verhoeff Sten Wessel

10.1007/978-3-031-46826-1_8

Cite

Citations (0)

Enabling Research through the SCIP Optimization Suite 8.0

ACM Transactions on Mathematical Software (2023)

Ksenia Bestuzheva Mathieu Besançon Wei‐Kun Chen Antonia Chmiela Tim Donkiewicz

The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP . The focus of this article is on the role of the SCIP Optimization Suite in supporting research. SCIP ’s main design principles are discussed, followed by a presentation of the latest performance improvements and developments in version 8.0, which serve both as examples of SCIP ’s application as a research tool and as a platform for further developments. Furthermore, this article gives an overview of interfaces to other programming and modeling languages, new features that expand the possibilities for user interaction with the framework, and the latest developments in several extensions built upon SCIP .

Presentation (obstetrics)

10.1145/3585516

Cite

Citations (33)

Computational Aspects of Relaxation Complexity: Possibilities and Limitations

arXiv (Cornell University) (2021)

Gennadiy Averkov Christopher Hojny Matthias Schymura

The relaxation complexity $\mathrm{rc}(X)$ of the set of integer points $X$ contained in a polyhedron is the smallest number of facets of any polyhedron $P$ such that the integer points in $P$ coincide with $X$. It is a useful tool to investigate the existence of compact linear descriptions of $X$. In this article, we derive tight and computable upper bounds on $\mathrm{rc}_{\mathbb{Q}}(X)$, a variant of $\mathrm{rc}(X)$ in which the polyhedra $P$ are required to be rational, and we show that $\mathrm{rc}(X)$ can be computed in polynomial time if $X$ is 2-dimensional. Further, we investigate computable lower bounds on $\mathrm{rc}(X)$ with the particular focus on the existence of a finite set $Y \subseteq \mathbb{Z}^d$ such that separating $X$ and $Y \setminus X$ allows us to deduce $\mathrm{rc}(X) \geq k$. In particular, we show for some choices of $X$ that no such finite set $Y$ exists to certify the value of $\mathrm{rc}(X)$, providing a negative answer to a question by Weltge (2015). We also obtain an explicit formula for $\mathrm{rc}(X)$ for specific classes of sets $X$ and present the first practically applicable approach to compute $\mathrm{rc}(X)$ for sets $X$ that admit a finite certificate.

Polyhedron

Finite set

10.48550/arxiv.2105.12509

Cite

Citations (0)

The Role of the Alphabet in Network Coding: An Optimization Approach

2022 IEEE Information Theory Workshop (ITW) (2023)

Christopher Hojny Altan B. Kılıç Alberto Ravagnani

We consider the problem of determining the one-shot, zero-error capacity of a coded, multicast network over a small alphabet. We introduce a novel approach to this problem based on a mixed-integer program, which computes the size of the largest unambiguous codebook for a given alphabet size. As an application of our approach, we recover, extend and refine various results that were previously obtained with case-by-case analyses or specialized arguments, giving evidence of the wide applicability of our approach. We also provide two simple ideas that reduce the complexity of our method for some families of networks. We conclude the paper by outlining a research program we wish to pursue to investigate the one-shot capacity of large networks affected by adversarial noise and, more generally, the role played by the alphabet size in network coding.

Linear network coding

10.1109/itw55543.2023.10161662

Cite

Citations (2)

Integrality of Linearizations of Polynomials over Binary Variables using Additional Monomials

arXiv (Cornell University) (2019)

Christopher Hojny Marc E. Pfetsch Matthias Walter

Polynomial optimization problems over binary variables can be expressed as integer programs using a linearization with extra monomials in addition to those arising in the given polynomial. We characterize when such a linearization yields an integral relaxation polytope, generalizing work by Del Pia and Khajavirad (SIAM Journal on Optimization, 2018) and Buchheim, Crama and Rodriguez-Heck (European Journal of Operations Research, 2019). We also present an algorithm that finds these extra monomials for a given polynomial to yield an integral relaxation polytope or determines that no such set of extra monomials exists. In the former case, our approach yields an algorithm to solve the given polynomial optimization problem as a compact LP, and we complement this with a purely combinatorial algorithm.

Complement

Monomial basis

Source

Cite

Citations (2)

The role of rationality in integer-programming relaxations

Mathematical Programming (2023)

Manuel Aprile Gennadiy Averkov Marco Di Summa Christopher Hojny

Abstract For a finite set $$X \subset \mathbb {Z}^d$$ X ⊂ Z d that can be represented as $$X = Q \cap \mathbb {Z}^d$$ X = Q ∩ Z d for some polyhedron Q , we call Q a relaxation of X and define the relaxation complexity $${\text {rc}}(X)$$ rc ( X ) of X as the least number of facets among all possible relaxations Q of X . The rational relaxation complexity $${\text {rc}}_\mathbb {Q}(X)$$ rc Q ( X ) restricts the definition of $${\text {rc}}(X)$$ rc ( X ) to rational polyhedra Q . In this article, we focus on $$X = \Delta _d$$ X = Δ d , the vertex set of the standard simplex, which consists of the null vector and the standard unit vectors in $$\mathbb {R}^d$$ R d . We show that $${\text {rc}}(\Delta _d) \le d$$ rc ( Δ d ) ≤ d for every $$d \ge 5$$ d ≥ 5 . That is, since $${\text {rc}}_\mathbb {Q}(\Delta _d)=d+1$$ rc Q ( Δ d ) = d + 1 , irrationality can reduce the minimal size of relaxations. This answers an open question posed by Kaibel and Weltge (Math Program 154(1):407–425, 2015). Moreover, we prove the asymptotic statement $${\text {rc}}(\Delta _d) \in O(\nicefrac {d}{\sqrt{\log (d)}})$$ rc ( Δ d ) ∈ O ( d log ( d ) ) , which shows that the ratio $$\nicefrac {{\text {rc}}(\Delta _d)}{{\text {rc}}_\mathbb {Q}(\Delta _d)}$$ rc ( Δ d ) rc Q ( Δ d ) goes to 0, as $$d \rightarrow \infty $$ d → ∞ .

10.1007/s10107-023-01994-w

Cite

Citations (1)

Detecting and Handling Reflection Symmetries in Mixed-Integer (Nonlinear) Programming

arXiv (Cornell University) (2024)

Christopher Hojny

Symmetries in mixed-integer (nonlinear) programs (MINLP), if not handled appropriately, are known to negatively impact the performance of (spatial) branch-and-bound algorithms. Usually one thus tries to remove symmetries from the problem formulation or is relying on a solver that automatically detects and handles symmetries. While modelers of a problem can handle various kinds of symmetries, automatic symmetry detection and handling is mostly restricted to permutation symmetries. This article therefore develops techniques such that also black-box solvers can automatically detect and handle a broader class of symmetries. Inspired from geometric packing problems such as the kissing number problem, we focus on reflection symmetries of MINLPs. We develop a generic and easily applicable framework that allows to automatically detect reflection symmetries for MINLPs. To handle this broader class of symmetries, we discuss generalizations of state-of-the-art methods for permutation symmetries, and develop dedicated symmetry handling methods for special reflection symmetry groups. Our symmetry detection framework has been implemented in the open-source solver SCIP and we provide a comprehensive discussion of the implementation. The article concludes with a detailed numerical evaluation of our symmetry handling methods when solving MINLPs.

Reflection

10.48550/arxiv.2405.08379

Cite

Citations (0)

The SCIP Optimization Suite 7.0

Gerald Gamrath Daniel Anderson Ksenia Bestuzheva Wei‐Kun Chen Leon Eifler

The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming frame- work SCIP. This paper discusses enhancements and extensions contained in version 7.0 of the SCIP Optimization Suite. The new version features the parallel presolving library PaPILO as a new addition to the suite. PaPILO 1.0 simplifies mixed-integer linear op- timization problems and can be used stand-alone or integrated into SCIP via a presolver plugin. SCIP 7.0 provides additional support for decomposition algorithms. Besides im- provements in the Benders’ decomposition solver of SCIP, user-defined decomposition structures can be read, which are used by the automated Benders’ decomposition solver and two primal heuristics. Additionally, SCIP 7.0 comes with a tree size estimation that is used to predict the completion of the overall solving process and potentially trigger restarts. Moreover, substantial performance improvements of the MIP core were achieved by new developments in presolving, primal heuristics, branching rules, conflict analysis, and symmetry handling. Last, not least, the report presents updates to other components and extensions of the SCIP Optimization Suite, in particular, the LP solver SoPlex and the mixed-integer semidefinite programming solver SCIP-SDP.

Solver

Heuristics

Source

Cite

Citations (164)

Simple Iterative Methods for Linear Optimization over Convex Sets.

arXiv (Cornell University) (2020)

Daniel Dadush Christopher Hojny Sophie Huiberts Stefan Weltge

We give simple iterative methods for computing approximately optimal primal and dual solutions for the problem of maximizing a linear functional over a convex set $K$ given by a separation oracle. In contrast to prior work, our algorithms directly output primal and dual solutions and avoid a common requirement of binary search on the objective value. Under the assumption that $K$ contains a ball of radius $r$ and is contained inside the origin centered ball of radius $R$, using $O(\frac{R^4}{r^2 \varepsilon^2})$ iterations and calls to the oracle, our main method outputs a point $x \in K$ together with a non-negative combination of the inequalities outputted by the oracle and one inequality of the $R$-ball certifying that $x$ is an additive $\varepsilon$-approximate solution. In the setting where the inner $r$-ball is centered at the origin, we give a simplified variant which outputs a multiplicative $(1 + \varepsilon)$-approximate primal and dual solutions using $O(\frac{R^2}{r^2 \varepsilon^2})$ iterations and calls to the oracle. Similar results hold for packing type problems. Our methods are based on variants of the classical Von Neumann and Frank-Wolfe algorithms. Our algorithms are also easy to implement, and we provide an experimental evaluation of their performance on a testbed of maximum matching and stable set instances. We further compare variations of our method to the standard cut loop implemented using Gurobi.This comparison reveals that in terms of iteration count, our methods converge on average faster than the standard cut loop on our test set.

Ball (mathematics)

Source

Cite

Citations (0)