BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Program Committee DTSTART:20210524T150000Z DTEND:20210524T153000Z DTSTAMP:20260414T203609Z UID:MIP2021/1 DESCRIPTION:Title: Opening Remarks + Gather Demo\nby Program Committee as part of Mixed I nteger Programming Workshop 2021\n\nAbstract: TBA\n LOCATION:https://researchseminars.org/talk/MIP2021/1/ END:VEVENT BEGIN:VEVENT SUMMARY:Daniel Bienstock (Columbia University) DTSTART:20210524T153000Z DTEND:20210524T160000Z DTSTAMP:20260414T203609Z UID:MIP2021/2 DESCRIPTION:Title: Progress on polynomial optimization\nby Daniel Bienstock (Columbia Uni versity) as part of Mixed Integer Programming Workshop 2021\n\n\nAbstract\ nIn this talk I will describe ongoing work on polynomial optimization prob lems (POPs)\, from a discrete optimization perspective\, that is to say\, using techniques motivated by mixed-integer programming. In particular I will primarily focus on methods for producing solutions\, and on the feasi bility of such solutions. The current "king of the hill" for computing so lutions to POPs are filter methods relying on logarithmic barrier algorith ms\, implemented in codes such as IPOPT or KNITRO. Instead we will focus on techniques based on integer programming -- such techniques are not yet competitive with the solvers just mentioned\, but may soon yield competiti ve algorithms. \n\nIf time permits\, I will also describe joint work (wit h Chen Chen and Gonzalo Munoz) on techniques for obtaining lower bounds fo r POPs based on classical cutting-plane techniques\, such as intersection cuts.\n LOCATION:https://researchseminars.org/talk/MIP2021/2/ END:VEVENT BEGIN:VEVENT SUMMARY:Boshi Yang (Clemson University) DTSTART:20210524T160000Z DTEND:20210524T163000Z DTSTAMP:20260414T203609Z UID:MIP2021/3 DESCRIPTION:Title: Quadratic Programs with Non-intersecting Constraints\nby Boshi Yang (C lemson University) as part of Mixed Integer Programming Workshop 2021\n\n\ nAbstract\nLet F be a set defined by quadratic constraints. Understanding the structure of the lifted closed convex hull of C(F) is crucial to solve quadratically constrained quadratic programs related to F. In this talk\, we discuss the relationship between C(F) and C(G)\, where G results by ad ding non-intersecting quadratic constraints to F. We prove that C(G) can b e represented as the intersection of C(F) and some half spaces defined by the added constraints. Our result generalizes an existing result for bound ed F. As a byproduct\, we provide a complete description of the asymptotic cones of sets defined by a single quadratic equality.\n LOCATION:https://researchseminars.org/talk/MIP2021/3/ END:VEVENT BEGIN:VEVENT SUMMARY:Students DTSTART:20210524T164500Z DTEND:20210524T184500Z DTSTAMP:20260414T203609Z UID:MIP2021/4 DESCRIPTION:Title: Poster Session\nby Students as part of Mixed Integer Programming Works hop 2021\n\nAbstract: TBA\n\non gather.town\n LOCATION:https://researchseminars.org/talk/MIP2021/4/ END:VEVENT BEGIN:VEVENT SUMMARY:Jon Lee (University of Michigan) DTSTART:20210525T150000Z DTEND:20210525T153000Z DTSTAMP:20260414T203609Z UID:MIP2021/5 DESCRIPTION:Title: Gaining or Losing Perspective for Piecewise-Linear Under-Estimators of Con vex Univariate Functions\nby Jon Lee (University of Michigan) as part of Mixed Integer Programming Workshop 2021\n\n\nAbstract\nWe study MINLO ( mixed-integer non-linear optimization) formulations of the disjunction x ∈ {0} ∪ [l\, u]\, where z is a binary indicator of x ∈ [l\,u] (0 ≤ l < u)\, and y "captures" f(x)\, which is assumed to be convex and posit ive on its domain [l\, u]\, but otherwise y=0 when x=0. This model is very useful in non-linear combinatorial optimization\, where there is a fixed cost of operating an activity at level x in the operating range [l\, u]\, and then there is a further (convex) variable cost f(x). In particular\, w e study relaxations related to the perspective transformation of a natural piecewise-linear under-estimator of f\, obtained by choosing linearizatio n points for f. Using 3-d volume (in (x\,y\,z)) as a measure of the tightn ess of a convex relaxation\, we investigate relaxation quality as a functi on of f\, l\, u\, and the linearization points chosen. We make a careful i nvestigation for convex power functions f(x) := xp\, p > 1. \n\nThis is j oint work with Daphne Skipper\, Emily Speakman\, and Luze Xu.\n LOCATION:https://researchseminars.org/talk/MIP2021/5/ END:VEVENT BEGIN:VEVENT SUMMARY:Sanjeeb Dash (IBM Research) DTSTART:20210525T160000Z DTEND:20210525T163000Z DTSTAMP:20260414T203609Z UID:MIP2021/7 DESCRIPTION:Title: Integer and linear programming methods for two problems in machine learnin g\nby Sanjeeb Dash (IBM Research) as part of Mixed Integer Programming Workshop 2021\n\n\nAbstract\nIn this talk we describe linear and integer programming based methods for two problems in statistics and machine learn ing. In the first part\, we focus on learning causal structures in the pre sence of latent variables\, which can be modeled as the problem of optimiz ing over the set of acyclic directed mixed graphs (containing directed and bidirected edges) defined on a set of nodes. We give an integer programmi ng formulation of this problem\, and the first algorithm to solve this pro blem to optimality (via branch-and-cut). In the second part of the talk\, we will describe a linear programming based approach to learning first-ord er logical rules for the knowledge graph link prediction problem.\nThis is joint work with Rui Chen\, Tian Gao\, and Joao Goncalves.\n LOCATION:https://researchseminars.org/talk/MIP2021/7/ END:VEVENT BEGIN:VEVENT SUMMARY:Ambros Gleixner (Zuse Institute Berlin and HTW Berlin) DTSTART:20210525T164500Z DTEND:20210525T171500Z DTSTAMP:20260414T203609Z UID:MIP2021/8 DESCRIPTION:Title: Exact mixed-integer programming: a status update on MIP solving without nu merical errors\nby Ambros Gleixner (Zuse Institute Berlin and HTW Berl in) as part of Mixed Integer Programming Workshop 2021\n\n\nAbstract\nThe presence of floating-point roundoff errors compromises the results of virt ually all fast mixed integer programming solvers available today. The last milestone achievement for the numerically exact solution of general mixed integer programs over the rational numbers dates back to the hybrid-preci sion branch-and-bound algorithm published by Cook\, Koch\, Steffy\, and Wo lter in 2013. In this talk\, we describe a substantial revision and extens ion of this framework that integrates symbolic presolving\, features an ex act repair step for solutions from primal floating-point heuristics\, empl oys a faster rational LP solver based on LP iterative refinement\, and is able to produce independently verifiable certificates of optimality. We s tudy the significantly improved performance and give insights into the com putational behavior of the new algorithmic components. This is joint work with Leon Eifler.\n LOCATION:https://researchseminars.org/talk/MIP2021/8/ END:VEVENT BEGIN:VEVENT SUMMARY:Gregor Hendel (Fair Isaac Germany GmbH) DTSTART:20210525T171500Z DTEND:20210525T174500Z DTSTAMP:20260414T203609Z UID:MIP2021/9 DESCRIPTION:Title: Estimating the Branch-and-Bound Search Tree Size\nby Gregor Hendel (Fa ir Isaac Germany GmbH) as part of Mixed Integer Programming Workshop 2021\ n\n\nAbstract\n"When will this run finish?" is undoubtedly a popular quest ion among users of branch-and-bound based mixed integer programming solver s.\n\nIn this talk\, we focus on online estimations of the final tree size during the search. We first review existing measures of the search progre ss such as the (in-)famous gap\, and introduce a new measure called leaf-f requency. We then discuss and compare the suitability of the individual me asures as predictors of the final tree size either by direct projection or by time series forecasting. Finally\, we combine these measures as input of a simple Machine Learning model\, which significantly outperforms the p rediction accuracy of all individual measures. \n\nThis work manifests as a new display column in SCIP 7.0 that displays the approximate search prog ress percentage\, which can be trained further to user instances of intere st.\n LOCATION:https://researchseminars.org/talk/MIP2021/9/ END:VEVENT BEGIN:VEVENT SUMMARY:Jannik Matuschke (KU Leuven) DTSTART:20210525T174500Z DTEND:20210525T181500Z DTSTAMP:20260414T203609Z UID:MIP2021/10 DESCRIPTION:Title: LP-based Approximation for Generalized Malleable Scheduling\nby Janni k Matuschke (KU Leuven) as part of Mixed Integer Programming Workshop 2021 \n\n\nAbstract\nIn malleable scheduling\, jobs can be executed simultaneou sly on multiple machines with the processing time depending on the number of allocated machines. Each job is required to be executed non-preemptivel y and in unison\, i.e.\, it has to occupy the same time interval on all it s allocated machines. In this talk\, we discuss a generalization of mallea ble scheduling\, in which a function f(S\, j) determines the processing ti me of job j on machine subset S. Under different discrete concavity assump tions on 1/f(S\,j)\, we show that the scheduling problem can be approximat ed by a considerably simpler assignment problem and derive LP-based approx imation algorithms.\nThis is joint work with Dimitris Fotakis and Orestis Papadigenopoulos.\n LOCATION:https://researchseminars.org/talk/MIP2021/10/ END:VEVENT BEGIN:VEVENT SUMMARY:Siqian Shen (University of Michigan) DTSTART:20210525T181500Z DTEND:20210525T184500Z DTSTAMP:20260414T203609Z UID:MIP2021/11 DESCRIPTION:Title: Sequential Competitive Facility Location: Exact and Approximate Algorithm s\nby Siqian Shen (University of Michigan) as part of Mixed Integer Pr ogramming Workshop 2021\n\n\nAbstract\nWe study a competitive facility loc ation problem (CFLP)\, in which two firms sequentially select locations of new facilities\, in order to maximize their market shares of customer dem and that follows a probabilistic choice model. This process is a Stackelbe rg game and admits a bilevel mixed-integer nonlinear program (MINLP) formu lation. Through integer programming methods\, we derive an equivalent\, si ngle-level MINLP reformulation. In addition\, we exploit the problem struc tures and derive two classes of valid inequalities\, one based on submodul arity and the other based on concave overestimation. We apply these inequa lities in a branch-and-cut algorithm to find a globally optimal solution t o CFLP. Furthermore\, we propose an approximation algorithm for solving CF LP that is computationally more effective. Notably\, this algorithm admits a constant approximation guarantee. Extensive numerical studies demonstra te that the exact algorithm can significantly accelerate the solving of CF LP on problem instances that have not been solved to optimality by existin g methods. The approximation algorithm can find near-optimal solutions eve n more quickly.\n\nThis is joint work with Mingyao Qi (Tsinghua U) and Rui wei Jiang (U of Michigan).\n LOCATION:https://researchseminars.org/talk/MIP2021/11/ END:VEVENT BEGIN:VEVENT SUMMARY:Amitabh Basu (Johns Hopkins University) DTSTART:20210526T150000Z DTEND:20210526T153000Z DTSTAMP:20260414T203609Z UID:MIP2021/12 DESCRIPTION:Title: Complexity of cutting plane and branch-and-bound algorithms\nby Amita bh Basu (Johns Hopkins University) as part of Mixed Integer Programming Wo rkshop 2021\n\n\nAbstract\nWe discuss the complexity of the two main ingre dients in integer optimization algorithms: cutting planes and branch-and-b ound. We prove upper and lower bounds on the efficiency of these algorithm s\, when efficiency is measured in terms of complexity of the LPs that are solved. More precisely\, we focus on the sparsity of the LPs and the numb er of LPs as measures of complexity. We also give general conditions under which combining branching and cutting into a branch-and-cut algorithm can do exponentially better than pure cutting planes or pure branch-and-bound . Time permitting\, some connections to mathematical logic and proof compl exity will be discussed.\n LOCATION:https://researchseminars.org/talk/MIP2021/12/ END:VEVENT BEGIN:VEVENT SUMMARY:Karthekeyan Chandrasekaran (UIUC) DTSTART:20210526T153000Z DTEND:20210526T160000Z DTSTAMP:20260414T203609Z UID:MIP2021/13 DESCRIPTION:Title: Improving the integrality gap for multiway cut\nby Karthekeyan Chandr asekaran (UIUC) as part of Mixed Integer Programming Workshop 2021\n\n\nAb stract\nIn the multiway cut problem\, we are given an undirected graph wit h non-negative edge weights and a collection of k terminals\, and the goal is to partition the vertices into k parts each containing exactly one ter minal so that the total weight of the edges crossing the partition is mini mized. The multiway cut problem for k>=3 is APX-hard. Assuming the unique games conjecture\, the approximability of this problem coincides with the integrality gap of an LP-relaxation\, known as the CKR relaxation. The CKR relaxation embeds the graph into a (k-1)-dimensional simplex. For arbitra ry k\, the best-known upper bound on the integrality gap is 1.2965 while t he previous best-known lower bound on the integrality gap was 1.2. In a re cent work\, we improved the lower bound to 1.20016 by constructing a 3-dim ensional simplex instance. In this talk\, I will present the main ideas un derlying the construction and the analysis of this instance.\n\nBased on j oint work with Kristof Berczi\, Tamas Kiraly\, and Vivek Madan.\n LOCATION:https://researchseminars.org/talk/MIP2021/13/ END:VEVENT BEGIN:VEVENT SUMMARY:Christopher Hojny (Eindhoven University of Technology) DTSTART:20210526T160000Z DTEND:20210526T163000Z DTSTAMP:20260414T203609Z UID:MIP2021/14 DESCRIPTION:Title: Computational Aspects of Relaxation Complexity\nby Christopher Hojny (Eindhoven University of Technology) as part of Mixed Integer Programming Workshop 2021\n\n\nAbstract\nThe relaxation complexity rc(X) of a set of i nteger 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 an important tool to investigate the existence of compact linear descr iptions of X. In this talk\, I will address computational aspects of relax ation complexity such as finding computable upper bounds on rc(X) or the e xact value of rc(X). For the latter\, I will show generic algorithmic appr oaches and provide explicit formulas for rc(X) for specific classes of set s X. \n\nThis is joint work with Gennadiy Averkov and Matthias Schymura.\n LOCATION:https://researchseminars.org/talk/MIP2021/14/ END:VEVENT BEGIN:VEVENT SUMMARY:Elias Khalil (Polytechnique Montréal) DTSTART:20210526T164500Z DTEND:20210526T171500Z DTSTAMP:20260414T203609Z UID:MIP2021/15 DESCRIPTION:Title: Revisiting Backdoors In Integer Programming\nby Elias Khalil (Polytec hnique Montréal) as part of Mixed Integer Programming Workshop 2021\n\n\n Abstract\nA backdoor is a small set of variables that leads to a certifica te branch-and-bound tree for a mixed-integer program: it suffices to branc h on the backdoor variables to solve an instance to global optimality or c onclude infeasibility. Experimental results by Dilkina et al. (2009) and F ischetti-Monaci (2011) have shown that many MILP instances from MIPLIB adm it backdoors of sizes 10-20\, which may lead to smaller branch-and-bound t rees if identified efficiently. We revisit the problem of finding small ba ckdoors to MILP problems from the perspective of reinforcement learning an d heuristic search and propose a new algorithm with some practical advanta ges over existing approaches.\n LOCATION:https://researchseminars.org/talk/MIP2021/15/ END:VEVENT BEGIN:VEVENT SUMMARY:Thiago Serra (Bucknell University) DTSTART:20210526T171500Z DTEND:20210526T174500Z DTSTAMP:20260414T203609Z UID:MIP2021/16 DESCRIPTION:Title: Scaling Up Exact Neural Network Compression by ReLU Stability\nby Thi ago Serra (Bucknell University) as part of Mixed Integer Programming Works hop 2021\n\n\nAbstract\nWe can compress a neural network while exactly pre serving its underlying functionality with respect to a given input domain if some of its neurons are stable. However\, current approaches to determi ne the stability of neurons require solving or finding a good approximatio n to multiple discrete optimization problems. In this talk\, we present an algorithm based on solving a single optimization problem to identify all stable neurons. Our approach is on median 21 times faster than the state-o f-art method\, which allows us to explore exact compression on deeper (5 x 100) and wider (2 x 800) networks within minutes. For classifiers trained under an amount of L1 regularization that does not worsen accuracy\, we c an remove up to 40% of the connections. \n\nThis talk is based on joint wo rk with Abhinav Kumar (Michigan State University) and Srikumar Ramalingam (Google Research).\n LOCATION:https://researchseminars.org/talk/MIP2021/16/ END:VEVENT BEGIN:VEVENT SUMMARY:Andrea Qualizza (Amazon) DTSTART:20210526T173500Z DTEND:20210526T181500Z DTSTAMP:20260414T203609Z UID:MIP2021/17 DESCRIPTION:Title: Discrete Optimization in Amazon Fulfillment\nby Andrea Qualizza (Amaz on) as part of Mixed Integer Programming Workshop 2021\n\n\nAbstract\nMIP plays a crucial role to support several decisions within the scope of my o rganization\, Amazon Fulfillment Optimization. In this talk I will present a couple of problems spanning real-time and tactical planning models. \n\ nI will start with a problem that we solve millions of times per day: how to fulfill each order striving to maximize customer experience and ensure fast delivery while keeping our costs low. I will then discuss our approac h to improve Amazon Logistics efficiency by exploiting delivery densificat ion opportunities and solving routing and demand assignment models togethe r.\n LOCATION:https://researchseminars.org/talk/MIP2021/17/ END:VEVENT BEGIN:VEVENT SUMMARY:Aleksandr Kazachkov (University of Florida) DTSTART:20210527T171500Z DTEND:20210527T174500Z DTSTAMP:20260414T203609Z UID:MIP2021/23 DESCRIPTION:Title: Strengthening V-polyhedral disjunctive cuts\nby Aleksandr Kazachkov ( University of Florida) as part of Mixed Integer Programming Workshop 2021\ n\n\nAbstract\nThe V-polyhedral framework is a recent approach for generat ing disjunctive cutting planes for mixed-integer linear programs. Unlike t he lift-and-project method\, which requires the construction of a computat ionally demanding higher-dimensional formulation\, V-polyhedral disjunctiv e cuts can be computed via a linear program in the same dimension as the o riginal problem. However\, without the values of the extra variables used for lift-and-project cuts\, one cannot directly apply a posteriori cut str engthening techniques such as monoidal strengthening. We show how the valu es of those extra variables can be computed efficiently\, and thereby lay the groundwork for strengthening arbitrary valid disjunctive cuts. We pres ent computational experiments with this idea on V-polyhedral disjunctive c uts.\n LOCATION:https://researchseminars.org/talk/MIP2021/23/ END:VEVENT BEGIN:VEVENT SUMMARY:All DTSTART:20210526T181500Z DTEND:20210526T190000Z DTSTAMP:20260414T203609Z UID:MIP2021/27 DESCRIPTION:Title: Business Meeting\nby All as part of Mixed Integer Programming Worksho p 2021\n\nAbstract: TBA\n LOCATION:https://researchseminars.org/talk/MIP2021/27/ END:VEVENT BEGIN:VEVENT SUMMARY:Noriyoshi Sukegawa (Tokyo University of Science) DTSTART:20210527T150000Z DTEND:20210527T153000Z DTSTAMP:20260414T203609Z UID:MIP2021/28 DESCRIPTION:Title: Recent Advances in Diameter of Polyhedra\nby Noriyoshi Sukegawa (Toky o University of Science) as part of Mixed Integer Programming Workshop 202 1\n\n\nAbstract\nThe diameter of polyhedra has attracted attention for yea rs due to its connection with the complexity of the simplex algorithm. In particular\, giving sharp bounds on the diameter in terms of specified par ameters is a central topic in mathematical optimization and computational geometry. In this talk\, we will survey some recent results on the diamete r of polyhedra with emphasis on those for lattice polytopes. A lattice pol ytope means a polytope whose vertices are drawn from {0\,1\,...\,k}d (name ly\, here\, k and d are the parameters). It is known since the 1990s that the diameter of lattice polytopes behaves as Θ(k2/3) in dimension 2. We g ive an explicit expression for the diameter of lattice zonotopes in fixed dimension for infinitely many k\, which implies that the diameter of latti ce polytopes behaves as Ω(kd/(d+1)) in dimension d. This talk is based on joint work with Antoine Deza and Lionel Pournin.\n LOCATION:https://researchseminars.org/talk/MIP2021/28/ END:VEVENT BEGIN:VEVENT SUMMARY:Jamie Haddock (UCLA) DTSTART:20210527T160000Z DTEND:20210527T163000Z DTSTAMP:20260414T203609Z UID:MIP2021/30 DESCRIPTION:Title: The Minimum Euclidean-Norm Point on a Convex Polytope: Wolfe's Combinator ial Algorithm is Exponential\nby Jamie Haddock (UCLA) as part of Mixed Integer Programming Workshop 2021\n\n\nAbstract\nThe complexity of Philip Wolfe's method for the minimum Euclidean-norm point problem over a convex polytope has remained unknown since he proposed the method in 1974. The m ethod is important because it is used as a subroutine for one of the most practical algorithms for submodular function minimization. We present the first example that Wolfe's method takes exponential time. Additionally\, w e improve previous results to show that linear programming reduces in stro ngly-polynomial time to the minimum norm point problem over a simplex.\n LOCATION:https://researchseminars.org/talk/MIP2021/30/ END:VEVENT BEGIN:VEVENT SUMMARY:Fatma Kılınç-Karzan (Carnegie Mellon University) DTSTART:20210525T153000Z DTEND:20210525T160000Z DTSTAMP:20260414T203609Z UID:MIP2021/33 DESCRIPTION:Title: Conic Mixed-Binary Sets: Convex Hull Characterizations and Applications\nby Fatma Kılınç-Karzan (Carnegie Mellon University) as part of Mixe d Integer Programming Workshop 2021\n\n\nAbstract\nWe consider a general c onic mixed-binary set where each homogeneous conic constraint involves an affine function of independent continuous variables and an epigraph variab le associated with a nonnegative function\, $f_j$\, of common binary varia bles. Sets of this form naturally arise as substructures in a number of ap plications including mean-risk optimization\, chance-constrained problems\ , portfolio optimization\, lot-sizing and scheduling\, fractional programm ing\, variants of the best subset selection problem\, and distributionally robust chance-constrained programs. When all of the functions $f_j$s are submodular\, we give a convex hull description of this set that relies on characterizing the epigraphs of $f_j$s. Our result unifies and generalizes an existing result in two important directions. First\, it considers mult iple general convex cone constraints instead of a single second-order cone type constraint. Second\, it takes arbitrary nonnegative functions instea d of a specific submodular function obtained from the square root of an a ffine function. We close by demonstrating the applicability of our results in the context of a number of broad problem classes. This is joint work w ith Simge Kucukyavuz and Dabeen Lee.\n LOCATION:https://researchseminars.org/talk/MIP2021/33/ END:VEVENT BEGIN:VEVENT SUMMARY:Program Committee DTSTART:20210527T174500Z DTEND:20210527T181500Z DTSTAMP:20260414T203609Z UID:MIP2021/34 DESCRIPTION:Title: Poster Prize + Closing Remarks\nby Program Committee as part of Mixed Integer Programming Workshop 2021\n\nAbstract: TBA\n LOCATION:https://researchseminars.org/talk/MIP2021/34/ END:VEVENT BEGIN:VEVENT SUMMARY:Jesús A. De Loera (UC Davis) DTSTART:20210527T153000Z DTEND:20210527T160000Z DTSTAMP:20260414T203609Z UID:MIP2021/38 DESCRIPTION:Title: Extreme behavior in linear programs and the simplex method\nby Jesús A. De Loera (UC Davis) as part of Mixed Integer Programming Workshop 2021 \n\n\nAbstract\nLinear programs and the simplex method are at the core of mathematical optimization\, both in theory and in practice. \nToday plenty of fascinating open questions remain about the behavior of the simplex me thod.\n\nIn this lecture we introduce natural geometric-topological struct ure one can associate to the set of all possible monotone paths of a linea r program. Using this structure we are interested to find the extreme beha vior of LPs regarding the following questions: a) How long can the monoto ne paths on a linear program be? b) How many different monotone paths can there be on a linear program?\n\nWe report on some highlights from three recent papers\, the first joint work with Moise Blanchard (MIT) and Quenti n Louveaux (U. Liege)\, the second with Sean Kafer (U. Waterloo) and Laura Sanità (TU Eindhoven) and the third with Christos Athanasiadis (U. Athen s) and Zhenyang Zhang (U. California\, Davis).\nPapers are available at an d https://arxiv.org/abs/2002.00999\, https://arxiv.org/abs/1909.12863 and https://arxiv.org/abs/2001.09575\n LOCATION:https://researchseminars.org/talk/MIP2021/38/ END:VEVENT BEGIN:VEVENT SUMMARY:Jose Verschae (Pontificia Universidad Católica) DTSTART:20210527T164500Z DTEND:20210527T171500Z DTSTAMP:20260414T203609Z UID:MIP2021/40 DESCRIPTION:Title: Symmetry breaking inequalities: Geometry and Perspectives\nby Jose Ve rschae (Pontificia Universidad Católica) as part of Mixed Integer Program ming Workshop 2021\n\n\nAbstract\nBreaking symmetries is a popular way of speeding up the branch-and-bound method for symmetric integer programs. We study symmetry-breaking polyhedra\, more precisely\, fundamental domains. \n\nIn this talk\, I will introduce the necessary mathematical concepts to understand the implications of symmetries in polyhedral objects.\nIn part icular\, we will derive several general geometric properties of fundamenta l domains and how these geometric considerations can affect the power for breaking symmetries. I will also mention some recent results for construct ing more general fundamental domains ("On the Geometry of Symmetry Breakin g Inequalities" IPCO 2021). Finally\, I will focus on several open questio ns regarding fundamental domains\, their geometric properties\, and how th ey could help us better understand the capabilities and limitations of sym metry-breaking systems.\n\nThis is joint with Matías Villagra (U Columbia ) and Leonard von Niederhäusern (UOH & CMM).\n LOCATION:https://researchseminars.org/talk/MIP2021/40/ END:VEVENT END:VCALENDAR