For more than 20 years, single-leader multi-follower (SLMF) problems have been treated as a more difficult class of problems in comparison to bilevel optimization. In this work we challenge this common belief, studying whether SLMF problems can be reformulated as equivalent bilevel optimization problems. We consider both optimistic and pessimistic formulations. For the optimistic case … Read more
A pruning-aware adaptive gradient method is proposed which classifies the variables in two sets before updating them using different strategies. This technique extends the “relevant/irrelevant” approach of Ding (2019) and Zimmer et al. (2022) and allows a posteriori sparsification of the solution of model parameter fitting problems. The new method is proved to be convergent … Read more
We close three open problems in the separation complexity of valid inequalities for the knapsack polytope. Specifically, we establish that the separation problems for extended cover inequalities, (1,k)-configuration inequalities, and weight inequalities are all NP-complete. We also give a number of special cases where the separation problem can be solved in polynomial time. ArticleDownload View … Read more