Session: California to Amalfi Coast via Québec
Chair: Leo Liberti
Cluster: Interplay Between Continuous and Discrete Optimization
Talk 1: Fair and Accurate Regression: Relaxations, Heuristics and Exact Methods
Speaker: Anna Deza
Abstract: We consider the problem of fair regression which aims to train a machine learning model subject to fairness constraints or regularizers. While there is a large body of work addressing fair classification, the regression setting has received far less attention. Key to measuring popular fairness metrics is the use of indicators based on the intervals into which predictions fall. This poses a challenge as it makes the training problem non-convex and non-smooth. Most existing approaches avoid these hurdles by using convex proxies, approximations, and heuristics to produce fair models. We instead consider the exact fairness measures at hand and develop mixed-integer non-linear formulations for training fair models. We give a strong reformulation obtained by jointly convexifying the non-linear loss function of the model and indicators associated with each prediction. Solution times relative to the natural big-M formulation are substantially improved via the proposed reformulation. We provide an efficient coordinate descent algorithm to produce locally optimal fair models. Our numerical results show that the models produced by the relaxation alone have competitive statistical performance when compared to the state-of-the-art, achieving better accuracy-fairness trade-offs at a fraction of the time. Coordinate descent further improves upon the relaxed models. These results are consistent across synthetic and real datasets.
Talk 2: A bilevel approach for compensation and routing decisions in last-mile delivery
Speaker: Martina Cerulli
Abstract: In last-mile delivery logistics, peer-to-peer logistic platforms play an important role in connecting senders, customers, and independent carriers to fulfill delivery requests. Since the carriers are not under the platform’s control, the platform has to anticipate their reactions, while deciding how to allocate the delivery operations. In this work, we model this problem using bilevel programming. At the upper level, the platform decides how to assign the orders to the carriers together with the compensation paid for each accepted request; at the lower level, each carrier solves a profitable tour problem to determine which offered requests to accept, based on her own profit maximization. For the resulting bilevel formulation, we propose a single-level reformulation and an alternative formulation where the lower-level routing variables are projected out. A branch-and-cut algorithm is proposed to solve the bilevel models and extensive computational tests are performed to compare the proposed formulations and analyze solution characteristics.
Talk 3: A Polyhedral Study on L-Natural-Convex Minimization and Its Mixed-Integer Extension
Speaker: Kim Yu
Abstract: L-natural-convex functions are a class of nonlinear functions defined over integral domains. Such functions are not necessarily convex, but they display a discrete analogue of convexity. In this work, we explore the polyhedral structure of the epigraph of any L-natural-convex function and provide a class of valid inequalities. We show that these inequalities are sufficient to describe the epigraph convex hull completely, and we give an exact separation algorithm. We further examine a mixed-integer extension of this class of minimization problems and propose strong valid inequalities. We establish the connection between our results and the valid inequalities for some structured mixed-integer sets in the literature.
