Noticias en español
The Burial of Coupling Constraints in Linear Bilevel Optimization.
Abstract: It has been common sense in (linear) bilevel optimization that problems with coupling constraints are more difficult to tackle than those without such constraints. While the modeling capabilities in terms of the feasible sets are indeed richer because coupling constraints allow to model disconnected feasible sets, complexity theory did not see any difference between problems with our without coupling constraints. In this talk, we show that there is no difference at all when one considers optimal solutions instead of just feasible points. For the case of optimistic bilevel...
Read MoreColour-bias perfect matchings in hypergraphs.
Abstract: We study conditions under which an r-edge-coloured k-uniform hypergraph has a perfect matching that contains substantially more than n/(kr) monochromatic edges. Our main result solves this problem for perfect matchings under minimum degree conditions, which answers recent questions of Gishboliner, Glock and Sgueglia. This is joint work with Hiêp Hàn, Richard Lang, João Pedro Marciano, Matías Pavez-Signé, Andrew Treglown, and Camila Zárate-Guerén.
Read MoreA strongly polynomial algorithm for the minimum-cost generalized flow problem.
Abstract: We give a strongly polynomial algorithm for minimum cost generalized flow, and hence for optimizing any linear program with at most two non-zero entries per row, or at most two non-zero entries per column. Our result can be viewed as progress towards understanding whether all linear programs can be solved in strongly polynomial time, also referred to as Smale’s 9th problem. Our approach is based on the recent primal-dual interior point method (IPM) due to Allamigeon, Dadush, Loho, Natura and Végh (FOCS ’22). They show that the number of iterations needed by the IPM can...
Read MoreOptimizing Throughput and Makespan of Queuing Systems by Information Design.
Abstract: We study the optimal provision of information for two natural performance measures of queuing systems: throughput and makespan. A set of parallel links (queues) is equipped with deterministic capacities and stochastic travel times where the latter depend on a realized scenario, and the number of scenarios is assumed to be constant. A continuum of flow particles (users) arrives at the system at a constant rate. A system operator knows the realization of the scenario and may (partially) reveal this information via a public signaling scheme to the flow particles. Upon arrival, the...
Read MoreBidding problems in European deregulated electricity markets.
Abstract: In this talk, we consider a bidding problem in European deregulated electricity markets. The goal of this problem is to maximize the profit of a Generation Company (GC) by choosing the best possible bids to propose to a Market Operator (MO) whose tasks is to minimize the daily price of electricity for the retailers. This problem has many challenging features to consider such as unit commitment for the GC, a market clearing system for the MO and demand and productions capacities are subject to increasing uncertainty due to renewable energies. Most studies in the literature try to...
Read MoreSet Selection with Uncertain Weights: Non-Adaptive Queries and Thresholds.
.Abstract: We study set selection problems where the weights are uncertain. Instead of its exact weight, only an uncertainty interval containing its true weight is available for each element. In some cases, some solutions are universally optimal; i.e., they are optimal for every weight that lies within the uncertainty intervals. However, it may be that no universally optimal solution exists, unless we are revealed additional information on the precise values of some elements. In the minimum cost admissible query problem, we are tasked to (non-adaptively) find a minimum-cost subset of...
Read More