14 citations · 30 across the 20 of their papers we have counts for
24 papers
A characterization of maximal inhomogeneous-quadratic-free sets
Gonzalo Muñoz, Joseph Paat, Felipe Serrano
The intersection cut framework is a versatile tool for generating valid inequalities in optimization. Its main ingredients are so-called -free sets: convex sets whose interiors…
The column number for 3-modular matrices
Joseph Paat, Zach Walsh, Luze Xu
An integer-valued matrix is -modular if each submatrix has determinant at most in absolute value. The c…
Characterizing unimodular laminar hypergraphs via forbidden subhypergraphs
Marco Caoduro, Meike Neuwohner, Joseph Paat
The incidence matrix of a graph is totally unimodular if and only if the graph is bipartite, i.e., it contains no odd cycles. We extend the characterization of total unimodularity…
The MIP Workshop 2023 Computational Competition on Reoptimization
Suresh Bolusani, Mathieu Besançon, Ambros Gleixner +5
This paper describes the computational challenge developed for a computational competition held in 2023 for the anniversary of the Mixed Integer Programming Work…
Extended formulations for the integer hull of strictly -modular cographic polyhedral cones
Joseph Paat, Zach Walsh, Luze Xu
Conforti et al. give a compact extended formulation for a class of bimodular-constrained integer programs, namely those that model the stable set polytope of a graph with no disjoi…
On the column number and forbidden submatrices for -modular matrices
Joseph Paat, Ingo Stallknecht, Zach Walsh +1
An integer matrix is -modular if the determinant of each submatrix of has absolute value at mo…
Proximity and flatness bounds for linear integer optimization
Marcel Celaya, Stefan Kuhlmann, Joseph Paat +1
We develop a technique that can be applied to provide improved upper bounds for two important questions in linear integer optimization. - Proximity bounds: Given an optimal vertex…
A characterization of maximal homogeneous-quadratic-free sets
Gonzalo Muñoz, Joseph Paat, Felipe Serrano
The intersection cut framework was introduced by Balas in 1971 as a method for generating cutting planes in integer optimization. In this framework, one uses a full-dimensional con…
Compressing Branch-and-Bound Trees
Gonzalo Muñoz, Joseph Paat, Álinson S. Xavier
A branch-and-bound (BB) tree certifies a dual bound on the value of an integer program. In this work, we introduce the tree compression problem (TCP): Given a BB tree T that certif…
A Colorful Steinitz Lemma with Applications to Block Integer Programs
Timm Oertel, Joseph Paat, Robert Weismantel
The Steinitz constant in dimension is the smallest value such that for any norm on and for any finite zero-sum sequence in the unit ball, the sequence…
Improving the Cook et al. Proximity Bound Given Integral Valued Constraints
Marcel Celaya, Stefan Kuhlmann, Joseph Paat +1
Consider a linear program of the form , where is an integral matrix. In 1986 Cook, Gerards, Schrijver, and Tardos proved that, given an op…
Polynomial upper bounds on the number of differing columns of -modular integer programs
Jon Lee, Joseph Paat, Ingo Stallknecht +1
We study integer-valued matrices with bounded determinants. Such matrices appear in the theory of integer programs (IP) with bounded determinants. For example, Artmann et al. showe…
Constructing lattice-free gradient polyhedra in dimension two
Joseph Paat, Miriam Schlöter, Emily Speakman
Lattice-free gradient polyhedra can be used to certify optimality for mixed-integer convex minimization models. We consider how to construct these polyhedra for unconstrained model…
Improving proximity bounds using sparsity
Jon Lee, Joseph Paat, Ingo Stallknecht +1
We refer to the distance between optimal solutions of integer programs and their linear relaxations as proximity. In 2018, Eisenbrand and Weismantel proved that proximity is indepe…
Sparsity of integer solutions in the average case
Timm Oertel, Joseph Paat, Robert Weismantel
We examine how sparse feasible solutions of integer programs are, on average. Average case here means that we fix the constraint matrix and vary the right-hand side vectors. For a…
The distributions of functions related to parametric integer optimization
Timm Oertel, Joseph Paat, Robert Weismantel
We consider the asymptotic distribution of the IP sparsity function, which measures the minimal support of optimal IP solutions, and the IP to LP distance function, which measures…
The Integrality Number of an Integer Program
Joseph Paat, Miriam Schlöter, Robert Weismantel
We introduce the integrality number of an integer program (IP) in inequality form. Roughly speaking, the integrality number is the smallest number of integer constraints needed to…
Distances of optimal solutions of mixed-integer programs
Joseph Paat, Robert Weismantel, Stefan Weltge
A classic result of Cook et al. (1986) bounds the distances between optimal solutions of mixed-integer linear programs and optimal solutions of the corresponding linear relaxations…
Approximation of corner polyhedra with families of intersection cuts
Gennadiy Averkov, Amitabh Basu, Joseph Paat
We study the problem of approximating the corner polyhedron using intersection cuts derived from families of lattice-free sets in . In particular, we look at the prob…
Extreme functions with an arbitrary number of slopes
Amitabh Basu, Michele Conforti, Marco Di Summa +1
For the one dimensional infinite group relaxation, we construct a sequence of extreme valid functions that are piecewise linear and such that for every natural number , th…
The structure of the infinite models in integer programming
Amitabh Basu, Michele Conforti, Marco Di Summa +1
The infinite models in integer programming can be described as the convex hull of some points or as the intersection of halfspaces derived from valid functions. In this paper we st…
Non-unique lifting of integer variables in minimal inequalities
Amitabh Basu, Santanu S. Dey, Joseph Paat
We explore the lifting question in the context of cut-generating functions. Most of the prior literature on this question focuses on cut-generating functions that have the unique l…
Knot mosaic tabulation
Hwa Jeong Lee, Lewis D. Ludwig, Joseph S. Paat +1
In 2008, Lomonaco and Kauffman introduced a knot mosaic system to define a quantum knot system. A quantum knot is used to describe a physical quantum system such as the topology or…
Operations that preserve the covering property of the lifting region
Amitabh Basu, Joe Paat
We contribute to the theory for minimal liftings of cut-generating functions. In particular, we give three operations that preserve the so-called covering property of certain struc…