BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Program Committee
DTSTART;VALUE=DATE-TIME:20210524T150000Z
DTEND;VALUE=DATE-TIME:20210524T153000Z
DTSTAMP;VALUE=DATE-TIME:20240329T075557Z
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;VALUE=DATE-TIME:20210524T153000Z
DTEND;VALUE=DATE-TIME:20210524T160000Z
DTSTAMP;VALUE=DATE-TIME:20240329T075557Z
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;VALUE=DATE-TIME:20210524T160000Z
DTEND;VALUE=DATE-TIME:20210524T163000Z
DTSTAMP;VALUE=DATE-TIME:20240329T075557Z
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;VALUE=DATE-TIME:20210524T164500Z
DTEND;VALUE=DATE-TIME:20210524T184500Z
DTSTAMP;VALUE=DATE-TIME:20240329T075557Z
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;VALUE=DATE-TIME:20210525T150000Z
DTEND;VALUE=DATE-TIME:20210525T153000Z
DTSTAMP;VALUE=DATE-TIME:20240329T075557Z
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;VALUE=DATE-TIME:20210525T160000Z
DTEND;VALUE=DATE-TIME:20210525T163000Z
DTSTAMP;VALUE=DATE-TIME:20240329T075557Z
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;VALUE=DATE-TIME:20210525T164500Z
DTEND;VALUE=DATE-TIME:20210525T171500Z
DTSTAMP;VALUE=DATE-TIME:20240329T075557Z
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;VALUE=DATE-TIME:20210525T171500Z
DTEND;VALUE=DATE-TIME:20210525T174500Z
DTSTAMP;VALUE=DATE-TIME:20240329T075557Z
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;VALUE=DATE-TIME:20210525T174500Z
DTEND;VALUE=DATE-TIME:20210525T181500Z
DTSTAMP;VALUE=DATE-TIME:20240329T075557Z
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;VALUE=DATE-TIME:20210525T181500Z
DTEND;VALUE=DATE-TIME:20210525T184500Z
DTSTAMP;VALUE=DATE-TIME:20240329T075557Z
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;VALUE=DATE-TIME:20210526T150000Z
DTEND;VALUE=DATE-TIME:20210526T153000Z
DTSTAMP;VALUE=DATE-TIME:20240329T075557Z
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;VALUE=DATE-TIME:20210526T153000Z
DTEND;VALUE=DATE-TIME:20210526T160000Z
DTSTAMP;VALUE=DATE-TIME:20240329T075557Z
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;VALUE=DATE-TIME:20210526T160000Z
DTEND;VALUE=DATE-TIME:20210526T163000Z
DTSTAMP;VALUE=DATE-TIME:20240329T075557Z
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;VALUE=DATE-TIME:20210526T164500Z
DTEND;VALUE=DATE-TIME:20210526T171500Z
DTSTAMP;VALUE=DATE-TIME:20240329T075557Z
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;VALUE=DATE-TIME:20210526T171500Z
DTEND;VALUE=DATE-TIME:20210526T174500Z
DTSTAMP;VALUE=DATE-TIME:20240329T075557Z
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;VALUE=DATE-TIME:20210526T173500Z
DTEND;VALUE=DATE-TIME:20210526T181500Z
DTSTAMP;VALUE=DATE-TIME:20240329T075557Z
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;VALUE=DATE-TIME:20210527T171500Z
DTEND;VALUE=DATE-TIME:20210527T174500Z
DTSTAMP;VALUE=DATE-TIME:20240329T075557Z
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;VALUE=DATE-TIME:20210526T181500Z
DTEND;VALUE=DATE-TIME:20210526T190000Z
DTSTAMP;VALUE=DATE-TIME:20240329T075557Z
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;VALUE=DATE-TIME:20210527T150000Z
DTEND;VALUE=DATE-TIME:20210527T153000Z
DTSTAMP;VALUE=DATE-TIME:20240329T075557Z
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;VALUE=DATE-TIME:20210527T160000Z
DTEND;VALUE=DATE-TIME:20210527T163000Z
DTSTAMP;VALUE=DATE-TIME:20240329T075557Z
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;VALUE=DATE-TIME:20210525T153000Z
DTEND;VALUE=DATE-TIME:20210525T160000Z
DTSTAMP;VALUE=DATE-TIME:20240329T075557Z
UID:MIP2021/33
DESCRIPTION:Title: Conic Mixed-Binary Sets: Convex Hull Characterizations and Applications
a>\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;VALUE=DATE-TIME:20210527T174500Z
DTEND;VALUE=DATE-TIME:20210527T181500Z
DTSTAMP;VALUE=DATE-TIME:20240329T075557Z
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;VALUE=DATE-TIME:20210527T153000Z
DTEND;VALUE=DATE-TIME:20210527T160000Z
DTSTAMP;VALUE=DATE-TIME:20240329T075557Z
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;VALUE=DATE-TIME:20210527T164500Z
DTEND;VALUE=DATE-TIME:20210527T171500Z
DTSTAMP;VALUE=DATE-TIME:20240329T075557Z
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