Jourdain Lamperski

Generalizing single-level relaxations for bilevel linear programs

Categories (Mixed) Integer Linear Programming, Bilevel Optimization Tags , ,

We consider a broad class of bilevel linear programs in which the follower’s decisions are all continuous, while the leader’s decisions may include integrality restrictions. Solving such problems to optimality is known to be NP-hard. A classical approach in bilevel optimization for constructing lower and upper bounds is based on a single-level relaxation, in which … Read more

An Oblivious Ellipsoid Algorithm for Solving a System of (In)Feasible Linear Inequalities

Categories Convex Optimization, Linear Programming, Nonsmooth Optimization Tags , , , ,

The ellipsoid algorithm is a fundamental algorithm for computing a solution to the system of m linear inequalities in n variables (P) when its set of solutions has positive volume. However, when (P) is infeasible, the ellipsoid algorithm has no mechanism for proving that (P) is infeasible. This is in contrast to the other two … Read more