Liding Xu

Liding Xu

Ph.D student at LIX, École Polytechnique

Talks and presentations

MILP formulations for continuous set-covering on networks

February 21, 2023

Talks, ROADEF2023, Renne, France

Covering problems are well-studied in the domain of Location Science. When the location space is a network, the most frequent assumption is to consider the candidate facility locations, the points to be covered, or both, to be finite sets. In this work, we study the set-covering location problem when both candidate locations and demand points are continuous on a network. This variant generalizes several problems, including set-covering, and uncapacitated facility location problems. However, this problem has received little attention, and the scarce existing approaches have focused on particular cases, such as tree networks and integer covering radius. Here we study the general problem through an integer programming approach, and propose two MILP formulations for the problem with several reduction techniques. We implement the existing and new MILP formulations in JuMP modeling language. Our computational experiments show the strengths and limitations of our exact approach to both real-world and random networks. Our formulations are also tested against an existing exact method. slides

Intersection cuts meet submodularity: the good and the bad

January 13, 2023

Talks, Aussois workshop 2023, Aussois, France

Intersection cuts can tighten a polyhedral outer approximation of a non-convex set. We study intersection cuts for submodular and submodular-supermodular maximization problems. We construct corresponding S-free sets and propose a cut computation algorithm. We report our good and bad experiences with intersection cuts in max cut, maximization of Boolean multilinear functions, maximization of utility functions, and D-optimal design problems. We found experimentally and thus conjecture that intersection cuts hardly improve the polyhedral outer approximations of non-monotone submodular maximization problems and problems with convex MINLP problems. So, a new measure of cut efficiency in terms of the corner polyhedral relaxation is in need. This talk is based on a joint work with Leo Liberti. slides

On a Concept of a Generic Intersection Cut Callback

November 04, 2022

Talks, SCIP2022, Berlin, German

Intersection cut framework can generate valid linear inequalities for a nonconvex set $S$. The framework requires a corner polyhedron relaxation of $S$, and a convex $S$-free set, which does not contain any point of $S$ in its interior. In this talk, I will review the recent development of intersection cuts in MINLPs (e.g quadratic/polynomial programming and signomial programming), featuring the construction of a variety of $S$-free sets. On the other hand, implementation of intersection cut requires much knowledge of a solver’s data structure and numerical stability. Software engineering can help here, as the solver can encapsulate cut separation procedures and provides an intersection cut callback without need for symbolic representation of $S$. Then, the users only need to provide defining-variables, zero- and first-order oracle access to the $S$-free set. I will also discuss some limitations of intersection cuts and open problems. slides

(Three) Cutting Planes for Signomial Programming

September 07, 2022

Talks, HUGO2022, Szeged, Hungary

The generation of cutting planes is crucial in solving non-convex Mixed-Integer Nonlinear Programming problems to $\epsilon$-global optimality. In this work, we study the signomial-term set (the graph of a signomial term function) arising in the extended formulation of Signomial Programming, and we show that it suffices to consider the signomial-term set as the epigraph/hypograph of the associated signomial term function. We present a useful reformulation of the signomial-term set, written as the zero-sublevel set of the difference of two concave power functions. We propose three types of valid linear inequalities: intersection cuts and two types of outer approximation cuts. slides

An algorithmic toolkit for continuous set-covering on networks

July 04, 2022

Talks, EURO2022, Espoo, Finand

Covering problems are well-studied in the domain of Operations Research, and, in particular, Location Science. When the location space is a network, the most frequent assumption is to consider the candidate facility locations, the points to be covered, or both, to be discrete sets. In this talk, we study the set-covering location problem when both demand points and candidate locations are continuous sets on a network, and we propose several Mixed-Integer Linear Programming Formulations. CFLG.jl is an open-source software written in the Julia programming language for the continuous set cover problem, and these MILP formulations are implemented in CFLG.jl. CFLG.jl can be extended to model other covering problems on networks, such as discrete cover problems. We conduct the numerical experiment of CFLG.jl on several benchmarks and compare the performance of different MILP formulations. The results show that our formulations are more scalable than the existing formulation. slides

Optimal Location of Safety Landing Sites

July 12, 2021

(Virtual) Talks, EURO2021, Athens, Greece

In urban air mobility probelm, Vertical Take Off and Landing (VTOLs) vehicles are used to move passengers between vertiports. Safety landing sites (SLSs) cover the trajectory of VTOLs for emergency landings. We study the optimal placement of SLSs in UAM network under budget constraints on SLS installation. slides report

Optimal Location of Safety Landing Sites

April 28, 2021

(Virtual) Talks, ROADEF2021, Mulhouses, France

In urban air mobility probelm, Vertical Take Off and Landing (VTOLs) vehicles are used to move passengers between vertiports. Safety landing sites (SLSs) cover the trajectory of VTOLs for emergency landings. We study the optimal placement of SLSs in UAM network under budget constraints on SLS installation. slides