random projections

Dimensionality Reduction in Bilevel Linear Programming

  • Eneko C. Clemente
  • Oleg A. Prokopyev
    • Categories Bilevel Optimization, Combinatorial Optimization, Polyhedra Tags , ,

    We consider bilevel programs that involve a leader, who first commits to a mixed-integer decision, and a follower, who observes this decision and then responds rationally by solving a linear program (LP). Standard approaches often reformulate these bilevel optimization problems as single-level mixed-integer programs by exploiting the follower’s LP optimality conditions. These reformulations introduce either … Read more

    Using the Johnson-Lindenstrauss lemma in linear and integer programming

  • Leo Liberti
  • Pierre-Louis Poirion
  • Ky Vu
    • Categories (Mixed) Integer Linear Programming, Linear Programming Tags , , ,

    The Johnson-Lindenstrauss lemma allows dimension reduction on real vectors with low distortion on their pairwise Euclidean distances. This result is often used in algorithms such as $k$-means or $k$ nearest neighbours since they only use Euclidean distances, and has sometimes been used in optimization algorithms involving the minimization of Euclidean distances. In this paper we … Read more