On 4/26/20 10:23 AM, Caveman Al Toraboran wrote: >> >> That looks a lot like a linear programming problem, but package versions >> are discrete. So ignoring all of the details, it's believable that we >> have an integer programming problem, which is NP-complete. > > i'm dumb, and don't fully understand this, but i > think i found something interesting: > > [1] http://www.aimsciences.org/article/doi/10.3934/jimo.2014.10.557 > > i wonder, can gradient descent be used to find > optimal portage solution? didn't read beyond the > abstract in [1], but from the abstract it seems > doable (i.e. integer programming solvable by > gradient descent). anyone please correct me if > i'm wrong. >
I think something like this is the right approach in the long run. Right now, portage is using a bunch of heuristics in a totally unprincipled way to find a solution that works. If we can turn the dependency resolution problem into some abstract mathematical form, then solving it becomes "not our problem," and we can reap the benefits as new theoretical techniques are incorporated into the existing solvers (you wouldn't want to write your own).
