from Hacker News

Chess and solution pool with linear programming (2018)

by cpp_frog on 10/2/23, 1:50 PM with 3 comments

  • by brosco on 10/2/23, 7:57 PM

    More specifically, using mixed integer linear programming.

    I've never seen an MILP used this way, to characterize the entire feasible set (or "solution pool"). Is this one of the fastest ways to do so? The usual branch-and-bound type methods won't apply, since the solver has to enumerate every feasible solution.

    The CPLEX docs (https://www.ibm.com/docs/en/icos/22.1.1?topic=solutions-how-...) mention the potential slowness and also the numerical issues the author faces in the article.