Loading...
Organizing Committee
University of California, Davis
McMaster University
Otto-von-Guericke Universität Magdeburg
RWTH Aachen University
Bocconi University of Milan
Georgia Tech
Abstract
Combinatorial optimization is an active research field in mathematics, with an immense range of applications. This workshop will bring together researchers and leading experts interested in the mathematical foundations of combinatorial optimization algorithms to discuss new tools and methods, in particular regarding the use of algebraic, analytical, and geometric techniques. Special emphasis will be given on polyhedral methods, since they are at the core of several groundbreaking combinatorial optimization results developed in recent years.
Loading...
Loading participant list in background...
Workshop Schedule
Monday, March 27, 2023
8:30 - 8:50 AM EDT
Check In
11th Floor Collaborative Space
8:50 - 9:00 AM EDT
Welcome
11th Floor Lecture Hall
Brendan Hassett, ICERM/Brown University
9:00 - 9:45 AM EDT
Interior point methods are not worse than Simplex
11th Floor Lecture Hall
Speaker
Daniel Dadush, Centrum Wiskunde & Informatica
Session Chair
Jesús De Loera, University of California, Davis
Abstract
Whereas interior point methods provide polynomial-time linear programming algorithms, the running time bounds depend on bit-complexity or condition measures that can be unbounded in the problem dimension. This is in contrast with the classical simplex method that always admits an exponential bound. We introduce a new polynomial-time path-following interior point method where the number of iterations also admits a combinatorial upper bound O(2^n n^{1.5} log n) for an n-variable linear program in standard form. This complements previous work by Allamigeon, Benchimol, Gaubert, and Joswig (SIAGA 2018) that exhibited a family of instances where any path-following method must take exponentially many iterations.
The number of iterations of our algorithm is at most O(n^{1.5} log n) times the number of segments of any piecewise linear curve in the wide neighborhood of the central path. In particular, it matches the number of iterations of any path following interior point method up to this polynomial factor. The overall exponential upper bound derives from studying the ‘max central path’, a piecewise-linear curve with the number of pieces bounded by the total length of n shadow vertex simplex paths.
This is joint work with Xavier Allamigeon (INRIA / Ecole Polytechnique), Georg Loho (U. Twente), Bento Natura (LSE), Laszlo Vegh (LSE).
The number of iterations of our algorithm is at most O(n^{1.5} log n) times the number of segments of any piecewise linear curve in the wide neighborhood of the central path. In particular, it matches the number of iterations of any path following interior point method up to this polynomial factor. The overall exponential upper bound derives from studying the ‘max central path’, a piecewise-linear curve with the number of pieces bounded by the total length of n shadow vertex simplex paths.
This is joint work with Xavier Allamigeon (INRIA / Ecole Polytechnique), Georg Loho (U. Twente), Bento Natura (LSE), Laszlo Vegh (LSE).
10:00 - 10:30 AM EDT
Coffee Break
11th Floor Collaborative Space
10:30 - 11:15 AM EDT
Partitioning over submodular structures
11th Floor Lecture Hall
Speaker
Karthekeyan Chandrasekaran, University of Illinois Urbana-Champaign
Session Chair
Jesús De Loera, University of California, Davis
Abstract
In submodular k-partitioning problems, the input is a submodular set function (given via an evaluation oracle) along with a fixed positive integer k (e.g., k = 2, 3, 4, …) and the goal is to partition the ground set into k non-empty parts so as to minimize certain natural objectives of interest. Submodular k-partitioning generalizes partitioning problems over several interesting structures including graphs and hypergraphs. The case of 2-partitioning corresponds to the classic and well-studied submodular minimization problem which is polynomial-time solvable. In this talk, I will outline recent progress towards polynomial-time solvability of submodular k-partitioning for fixed constant integers k >= 3.
11:30 AM - 12:15 PM EDT
The Polyhedral Structure of Graphical Designs
11th Floor Lecture Hall
Speaker
Catherine Babecki, University of Washington, Seattle
Session Chair
Jesús De Loera, University of California, Davis
Abstract
A graphical design is a quadrature rule for a graph inspired by classical numerical integration on the sphere. Broadly speaking, that means a graphical design is a relatively small subset of graph vertices chosen to capture the global behavior of functions from the vertex set to the real numbers. We first motivate and define graphical designs for graphs with positive edge weights. Through Gale duality, we exhibit a combinatorial bijection between graphical designs and the faces of certain polytopes associated to a graph, called eigenpolytopes. This polytope connection has a variety of beautiful consequences, including a proof of existence, an upper bound on the cardinality of a graphical design, methods to compute, optimize, and organize graphical designs, the existence of random walks with improved convergence rates, and complexity results for associated computational problems. This talk is based on work with Rekha Thomas, Stefan Steinerberger and David Shiroma.
12:30 - 2:30 PM EDT
Lunch/Free Time
2:30 - 3:15 PM EDT
Two New Algorithms for Set Covering
11th Floor Lecture Hall
Speaker
Anupam Gupta, Carnegie Mellon University
Session Chair
Yuri Faenza, Columbia University
Abstract
In the set covering problem we are given a set system, and we want to find a subcollection with few sets whose union is the entire universe. This problem is NP-hard to approximate to better than (ln n). Moreover we know matching algorithms which are achieved by both greedy and relax-and-round based algorithms. In this talk I will give two more algorithms which achieve the same guarantee (asymptotically), one based on local search, and another based on a learning-based framework (which also works in an online setting with random arrivals).
These results are based on joint works with Greg Kehne, Euiwoong Lee, Roie Levin, and Jason Li.
3:30 - 4:00 PM EDT
Coffee Break
11th Floor Collaborative Space
4:00 - 4:45 PM EDT
Alternating Linear Minimization: Revisiting von Neumann’s alternating projections
11th Floor Lecture Hall
Speaker
Sebastian Pokutta, Zuse Institute Berlin (ZIB)
Session Chair
Yuri Faenza, Columbia University
Abstract
In 1933 von Neumann proved a beautiful result that one can compute a point in the intersection of two convex sets (under suitable assumptions) by alternating projections, i.e., successively projecting on one set and then the other. This algorithm assumes that one has access to projection operators for both sets. Here we consider the much weaker setup where we have only access to linear minimization oracles over the convex sets and present an algorithm to find a point in the intersection of two convex sets. Moreover, we provide a modification of the algorithm to minimize a linear function over the intersection and discuss further extensions.
5:00 - 6:30 PM EDT
Reception
11th Floor Collaborative Space
Tuesday, March 28, 2023
9:00 - 9:45 AM EDT
Reusing Cuts in Iterative Projections over Submodular Polytopes
11th Floor Lecture Hall
Speaker
Swati Gupta, Georgia Tech
Session Chair
Karthekeyan Chandrasekaran, University of Illinois Urbana-Champaign
Abstract
Optimization algorithms such as projected Newton's method, FISTA, mirror descent and its variants enjoy near-optimal regret bounds and convergence rates, but suffer from a computational bottleneck of computing projections"" in potentially each iteration (e.g.,
O(T^{0.5}) regret of online mirror descent). On the other hand, conditional gradient variants solve a linear optimization in each iteration, but result in suboptimal rates (e.g.,
OT^{0.75}) regret of online Frank-Wolfe). Motivated by this trade-off in runtime v/s convergence rates, we consider iterative projections of close-by points over widely-prevalent submodular base polytopes B(f). We develop a toolkit to speed up the computation of projections using both discrete and continuous perspectives. We subsequently adapt the away-step Frank-Wolfe algorithm to use this information and enable early termination.
10:00 - 10:30 AM EDT
Coffee Break
11th Floor Collaborative Space
10:30 - 11:15 AM EDT
Clique Trees and Disjunctive Constraints
11th Floor Lecture Hall
Speaker
Illya Hicks, Rice University
Session Chair
Karthekeyan Chandrasekaran, University of Illinois Urbana-Champaign
Abstract
In this talk, we explore the concept of combinatorial disjunctive constraints (CDC) and their properties. In particular, we examine when one can build small ideal mixed-integer programming (MIP) formulations using CDCs and their linkages to clique trees. We also show that generalized special ordered sets (SOS k) can be modeled by CDCs with ties to clique trees.
11:30 AM - 12:15 PM EDT
Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack
11th Floor Lecture Hall
Speaker
Stefan Weltge, Technical University of Munich
Session Chair
Karthekeyan Chandrasekaran, University of Illinois Urbana-Champaign
Abstract
Standard mixed-integer programming formulations for the stable set problem on n-node graphs require n integer variables. We prove that this is almost optimal: We give an explicit family of stable set polytopes of n-node graphs for which every polynomial-size formulation requires Ω(n / log^2 n) integer variables. By a polyhedral reduction we obtain an analogous result for n-item knapsack polytopes. This improves the previously known bounds of Ω(√n / log n) by Cevallos, Weltge & Zenklusen (SODA 2018). To this end, we extend a result of Göös, Jain & Watson (FOCS 2016, SIAM J. Comput. 2018) showing that the linear extension complexity of stable set polytopes of some n-node graphs is 2^(Ω(n / log n)). We show that the same bound holds for ɛ/n-approximations of these polytopes, for some constant ɛ > 0. On this way, we simplify several of their original arguments to obtain a proof that is accessible to a broader community. For instance, our proof does not require reductions to certain CSP problems or the notion of Karchmer-Wigderson games. This is joint work with Jamico Schade and Makrand Sinha.
12:30 - 2:00 PM EDT
Networking Lunch
Lunch/Free Time - 11th Floor Collaborative Space
2:00 - 2:45 PM EDT
Arc connectivity and submodular flows in digraphs
11th Floor Lecture Hall
Speaker
Ahmad Abdi, London School of Economics
Session Chair
Steffen Borgwardt, University of Colorado Denver
Abstract
Given a digraph D, and an integer k>=1, a k-arc-connected flip is an arc subset whose reversal makes the digraph (strongly) k-arc-connected. The main result of this work introduces a sufficient condition for the existence of a k-arc-connected flip that is also a submodular flow for a crossing submodular function.
The main result has several applications to graph orientations and combinatorial optimization. For instance, if the underlying graph of D is t-edge-connected for some integer t>=2, there exists a decomposition of the arc set into a k-arc-connected flip and a (t-k)-dijoin, for any integer k such that 1<=k<=t/2. This extends Nash-Williams’ weak orientation theorem, as well as proves a weaker variant of Woodall’s conjecture on such digraphs.
The main result follows from a surprising sufficient condition for the existence of capacitated integral solutions to the intersection of two submodular flow systems. This result in turn has some applications for submodular optimization. For instance, in a weakly connected digraph, the intersection of two submodular flow systems defines an integral polyhedron.
Joint work with Gerard Cornuejols and Giacomo Zambelli.
3:00 - 3:45 PM EDT
Smoothed Analysis of the Simplex Method
11th Floor Lecture Hall
Speaker
Sophie Huiberts, Columbia University
Session Chair
Steffen Borgwardt, University of Colorado Denver
Abstract
Explaining why the simplex method is fast in practice, despite it taking exponential time in the theoretical worst case, continues to be a challenge. Smoothed analysis is a paradigm for addressing this question. During my talk I will present recent progress in the smoothed complexity of the simplex method, discussing both upper and lower bounds.
4:00 - 4:30 PM EDT
Coffee Break
11th Floor Collaborative Space
4:30 - 6:00 PM EDT
Wednesday, March 29, 2023
9:00 - 9:45 AM EDT
Degree Sequence Optimization and Sparse Integer Programming
11th Floor Lecture Hall
Speaker
Shmuel Onn, Technion - Israel Institute of Technology
Session Chair
Antoine Deza, McMaster University
Abstract
I will suggest several open problems on optimization over degree sequences of graphs and hypergraphs and over line sums of matrices; describe several recent partial results such as for convex functions, complete graphs, complete bipartite graphs and monotone matrices, and bounded tree width or depth; and outline some proof techniques, including our recent powerful theory of sparse integer programming in high dimensions, which will be explained.
10:00 - 10:30 AM EDT
Coffee Break
11th Floor Collaborative Space
10:30 - 11:15 AM EDT
Algorithmic, combinatorial, and geometric aspects of linear optimization
11th Floor Lecture Hall
Speaker
Lionel Pournin, University of Paris 13
Session Chair
Antoine Deza, McMaster University
Abstract
The simplex and interior point methods are currently the most computationally successful algorithms for linear optimization. While simplex methods follow an edge path, interior point methods follow the central path. The complexity of these methods is closely related to the combinatorial and geometric structures of the feasible region. Focusing on the analysis of worst-case constructions leading to computationally challenging instances, recently obtained lower bounds on the largest possible diameter of lattice polytopes will be presented. These bounds, via lattice zonotopes, are established using tools from combinatorics and number theory. This talk is based on joint work with Antoine Deza.
11:30 AM - 12:15 PM EDT
The Exact Bipartite Matching Polytope Has Exponential Extension Complexity
11th Floor Lecture Hall
Speaker
Ola Svensson, EPFL
Session Chair
Antoine Deza, McMaster University
Abstract
Given a graph with edges colored red or blue and an integer k, the exact perfect matching problem asks if there exists a perfect matching with exactly k red edges. There exists a randomized polylogarithmic-time parallel algorithm to solve this problem, dating back to the eighties, but no deterministic polynomial-time algorithm is known, even for bipartite graphs.
In this talk, we discuss known approaches and their limitations. In particular, we show that there is no sub-exponential-sized linear program that can describe the convex hull of exact matchings in bipartite graphs. In fact, we prove something stronger, that there is no sub-exponential-sized linear program to describe the convex hull of perfect matchings with an odd number of red edges. To prove our result, we devise an exponential set of valid constraints that we believe are interesting in their own right. In particular, we leave as an open problem whether they define the convex hull of perfect matchings with an odd number of red edges.
This is joint work with Xinrui Jia and Weiqiang Yuan
This is joint work with Xinrui Jia and Weiqiang Yuan
12:15 - 12:30 PM EDT
Group Photo (Immediately After Talk)
11th Floor Lecture Hall
12:30 - 2:30 PM EDT
Lunch/Free Time
2:30 - 3:15 PM EDT
Approximating Weighted Connectivity Augmentation Below Factor 2
11th Floor Lecture Hall
Speaker
Rico Zenklusen, ETH Zurich
Session Chair
Sophie Huiberts, Columbia University
Abstract
The Weighted Connectivity Augmentation Problem (WCAP) asks to augment the edge-connectivity of a graph by adding a min cost edge set among given candidate edges. It is among the most elementary network design problems for which no better-than-2 approximation has been known, whereas 2-approximations can easily be obtained through a variety of well-known techniques.
In this talk, I will discuss an approach showing that approximation factors below 2 are achievable for WCAP, ultimately leading to a (1.5+epsilon)-approximation. Our approach is based on a highly structured directed simplification of WCAP with planar optimal solutions. We show how one can successively improve solutions of this directed simplification by moving to mixed solutions, consisting of both directed and undirected edges. These insights can be leveraged in local search and relative greedy strategies, inspired by recent advances on the Weighted Tree Augmentation Problem, to obtain a (1.5+epsilon)-approximation.
This is joint work with Vera Traub.
3:30 - 4:00 PM EDT
Coffee Break
11th Floor Collaborative Space
4:00 - 4:45 PM EDT
Unit and distinct distances in typical norms
11th Floor Lecture Hall
Speaker
Lisa Sauermann, MIT
Session Chair
Sophie Huiberts, Columbia University
Abstract
Given n points in the plane, how many pairs among these points can have distance exactly 1? More formally, what is the maximum possible number of unit distances among a set of n points in the plane? This problem is a very famous and still largely open problem, called the Erdos unit distance problem. One can also study this problem for other norms on R^2 (or more generally on R^d for any dimension d) that are different from the Euclidean norm. This direction has been suggested in the 1980s by Ulam and Erdos and attracted a lot of attention over the years. We give an almost tight answer to this question for almost all norms on R^d (for any given d). Furthermore, for almost all norms on R^d, we prove an asymptotically tight bound for a related problem, the so-called Erdos distinct distances problem. Our proofs rely in part on arguments from polyhedral geometry (and some tools from matroid theory are also relevant). Joint work with Noga Alon and Matija Bucic.
Thursday, March 30, 2023
9:00 - 9:45 AM EDT
Understanding graphs locally
11th Floor Lecture Hall
Speaker
Annie Raymond, University of Massachusetts, Amherst
Session Chair
Mohit Singh, Georgia Tech
Abstract
Graphs are ubiquitous in modern applications---including some very large graphs. This leads one to wonder, "How can we understand such large graphs?" One prevalent idea is to observe them locally: to count how many times certain substructures appear. If one knows something about the number of some particular substructures in a graph, what can one say about the number of other substructures or about global properties of the graph in general? Such problems are at the heart of extremal graph theory. In this talk, we will discuss successes and challenges in proving inequalities involving these substructures. We will also encounter graph profiles, complicated objects that allow us to understand all polynomial inequalities involving some fixed set of substructures. This is joint work with Greg Blekherman, Mohit Singh, Rekha Thomas and Fan Wei.
10:00 - 10:30 AM EDT
Coffee Break
11th Floor Collaborative Space
10:30 - 11:15 AM EDT
Untangling near minimum cuts with applications in network design
11th Floor Lecture Hall
Speaker
Nathan Klein, University of Washington
Session Chair
Mohit Singh, Georgia Tech
Abstract
The structure of the set of global minimum cuts of a graph is well understood and is captured by a cactus, as proved by Dinitz, Karzanov, and Lomonosov in the 70s. However, even for small epsilon, the set of (1+epsilon) near minimum cuts has a significantly more complex structure. Benczúr and Goemans studied near minimum cuts starting in the late 90s and showed that they admit a so-called polygon representation.
In this talk I will show new algorithmically useful properties of this representation and demonstrate two applications in approximating network design problems.
11:30 AM - 12:15 PM EDT
The Subspace Flatness Conjecture and Faster Integer Programming
11th Floor Lecture Hall
Speaker
Thomas Rothvoss, University of Washington
Session Chair
Mohit Singh, Georgia Tech
Abstract
In a seminal paper, Kannan and Lov\'asz (1988) considered a quantity $\mu_{KL}(\Lambda,K)$ which denotes the best volume-based lower bound on the covering radius $\mu(\Lambda,K)$ of a convex body $K$ with respect to a lattice $\Lambda$. Kannan and Lov\'asz proved that $\mu(\Lambda,K) \leq n \cdot \mu_{KL}(\Lambda,K)$ and the Subspace Flatness Conjecture by Dadush (2012) claims a $O(\log n)$ factor suffices, which would match the lower bound from the work of Kannan and Lov\'asz.
We settle this conjecture up to a constant in the exponent by proving that $\mu(\Lambda,K) \leq O(\log^{7}(n)) \cdot \mu_{KL} (\Lambda,K)$.
Our proof is
based on the Reverse Minkowski Theorem due to Regev and Stephens-Davidowitz (2017).
Following the work of Dadush (2012, 2019), we obtain a $(\log n)^{O(n)}$-time randomized algorithm to solve integer programs in $n$ variables.
Another implication of our main result is a near-optimal flatness constant of $O(n \log^{8}(n))$.
This is joint work with Victor Reis.
12:30 - 2:30 PM EDT
Networking Lunch
Lunch/Free Time - 11th Floor Collaborative Space
2:30 - 3:15 PM EDT
Transshipments over time, submodular functions, and discrete Newton
11th Floor Lecture Hall
Speaker
Martin Skutella, TU Berlin
Session Chair
Annie Raymond, University of Massachusetts, Amherst
Abstract
The Quickest Transshipment Problem is to route flow as quickly as possible from sources with supplies to
sinks with demands in a network with capacities and transit times on the arcs. It is of fundamental
importance for numerous applications in areas such as logistics, traffic, evacuation, and
finance. More than 25 years ago, Hoppe and Tardos presented the first (strongly) polynomial-time algorithm for this
problem. Their approach, as well as subsequently derived algorithms with strongly polynomial running
time, is hardly practical as it relies on parametric submodular function minimization via Megiddo's
parametric search. We present considerably faster algorithms for the Quickest Transshipment Problem
that instead employ a subtle extension of the Discrete Newton Method.
This improves the previously best known running time of $\tilde{O}(m^4k^{14})$ to $\tilde O(m^2k^5+m^3k^3+m^3n)$,
where $n$ is the number of nodes, $m$ the number of arcs, and $k$ the number of source and sink nodes.
Furthermore, we show how to compute integral quickest transshipments in $\tilde O(m^2k^6+m^3k^4+m^3n)$ time.
This is joint work with Miriam Schlöter and Khai Van Tran.
This is joint work with Miriam Schlöter and Khai Van Tran.
3:30 - 4:00 PM EDT
Coffee Break
11th Floor Collaborative Space
4:00 - 4:45 PM EDT
Openly Disjoint Paths, Jump Systems, and Discrete Convexity
11th Floor Lecture Hall
Speaker
Satoru Iwata, University of Tokyo
Session Chair
Annie Raymond, University of Massachusetts, Amherst
Abstract
In 1978, Mader discovered a min-max theorem on the number of openly disjoint paths between terminals. Sadli and Sebo (2000) showed that the set of integer vectors in that appear as degree sequences of openly disjoint paths forms a jump system. In this talk, we describe an alternative proof of this fact by using a reduction to matroid matching, which was originally observed by Lovasz (1980). In addition, we show that a function on this jump system determined by the minimum total length of openly disjoint paths enjoys the M-convexity introduced by Murota (2006).
Friday, March 31, 2023
9:00 - 9:45 AM EDT
Thin trees for laminar families
11th Floor Lecture Hall
Speaker
Neil Olver, London School of Economics
Session Chair
Britta Peis, RWTH Aachen University
Abstract
In the strong form of the thin tree conjecture, formulated by Goddyn in 2004, we are given a k-edge-connected graph and wish to find a tree containing at most an O(1/k) fraction of the edges across every cut. This conjecture, if true, has a variety of implications in a number of areas such as graph theory and approximation algorithms. A natural relaxation of this problem is to find a tree with at most O(1/k) edges across a fixed collection of cuts, instead of all cuts. Via a simple reduction technique followed by iterative relaxation, we show that the thin tree conjecture is true for laminar families of cuts, resolving an open question of Olver and Zenklusen from 2013. Joint work with Nathan Klein.
10:00 - 10:30 AM EDT
Coffee Break
11th Floor Collaborative Space
10:30 - 11:15 AM EDT
Streaming algorithms for k-submodular maximization and ad allocation
11th Floor Lecture Hall
Speaker
Alina Ene, Boston University
Session Chair
Britta Peis, RWTH Aachen University
Abstract
Maximizing a monotone k-submodular function subject to cardinality constraints is a general model for several applications ranging from influence maximization with multiple products to sensor placement with multiple sensor types and online ad allocation. Due to the large problem scale in many applications and the online nature of ad allocation, a need arises for algorithms that process elements in a streaming fashion and possibly make online decisions. In this talk, we present a streaming algorithm for maximizing a monotone k-submodular function subject to a per-coordinate cardinality constraint attaining an approximation guarantee close to the state of the art guarantee in the offline setting. We also give a variant of the algorithm that is able to leverage machine learning predictions.
11:30 AM - 12:15 PM EDT
Non-Adaptive Matroid Prophet Inequalities
11th Floor Lecture Hall
Speaker
Kanstantsin Pashkovich, University of Waterloo
Session Chair
Britta Peis, RWTH Aachen University
Abstract
We consider the matroid prophet inequality problem. This problem has been
extensively studied in the case of adaptive mechanisms. In particular, there is
a tight 2-competitive mechanism for all matroids.
However, it is not known what classes of matroids admit non-adaptive
mechanisms with constant guarantee. Recently, it was shown that there are
constant-competitive non-adaptive mechanisms for graphic matroids. In this
talk, we show that various known classes of matroids admit constant-competitive
non-adaptive mechanisms.
12:30 - 2:30 PM EDT
Lunch/Free Time
2:30 - 3:15 PM EDT
Approximating Nash Social Welfare for Submodular Valuations
11th Floor Lecture Hall
Speaker
László Végh, London School of Economics
Session Chair
Gerard Cornuejols, Carnegie Mellon University
Abstract
The Nash social welfare (NSW) problem asks for an allocation of indivisible items to agents in order to maximize the geometric mean of agents’ valuations. This is a common objective for fair division, representing a balanced tradeoff between the often conflicting requirements of fairness and efficiency. The problem is NP-complete already for additive valuation functions. We present a simple, deterministic 4-approximation algorithm for the Nash Social Welfare problem under the general class submodular valuation functions. The previous best approximation factor was 380 via a randomized algorithm.
We also consider the asymmetric variant of the problem where the objective is to maximize the weighted geometric mean of agents’ valuations, and give a (α+2)e-approximation, where α is the ratio between largest weight and the average weight.
This is joint work with Jugal Garg, Edin Husić, Wenzheng Li, and Jan Vondrák.
3:30 - 4:15 PM EDT
Optimal Deployment of Electric Vehicle Charging Infrastructure via Bilevel Optimization
11th Floor Lecture Hall
Speaker
Miguel Anjos, University of Edinburgh
Session Chair
Gerard Cornuejols, Carnegie Mellon University
Abstract
The increase of electric vehicle (EV) adoption in recent years has correspondingly increased the importance of providing adequate charging infrastructure for EV users. For a charging service provider, the fundamental question is to determine the optimal location and sizing of charging stations with respect to a given objective and subject to budget and other practical constraints. One possible objective is to maximize EV adoption as part of a public policy on electric transportation. Alternatively, the objective may be to maximize the profit gained from providing this service, in which case the price of charging is also to be optimized. These problems are fundamentally combinatorial and frequently formulated using mixed-integer linear optimization. In this talk, the focus will be on the use of bilevel optimization in this area, in particular to more accurately capture the interactions between the charging service provider and the EV users.
4:30 - 5:00 PM EDT
Coffee Break
11th Floor Collaborative Space
