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