search

pbvoting / pabutools

A complete set of tools to work with participatory budgeting elections.
https://pbvoting.github.io/pabutools/
GNU General Public License v3.0
7 stars 12 forks source link

[Feature suggestion] Implement non-ILP algorithm for welfare maximization #9

Open DominikPeters opened 11 months ago

DominikPeters commented 11 months ago

At the moment, the max welfare rule is implemented by an ILP. But one could also solve it using a dynamic program. This could be helpful for controlling the tie-breaking. In addition, I'm too lazy to include an ILP solver in my pref.tools version, so for that a pure python approach would also be useful.

(I don't think it's urgent, but it could be a student task.)

Simon-Rey commented 11 months ago

Yes, I agree with that!

Simon-Rey commented 8 months ago

Btw, what about simply using the Google OR tools? https://developers.google.com/optimization/reference/python/algorithms/pywrapknapsack_solver#knapsack_multidimension_branch_and_bound_solver

Simon-Rey commented 7 months ago

A primal/dual approach has now been implemented: https://pbvoting.github.io/pabutools/usage/rules.html#additive-utilitarian-welfare-maximiser by Stefan Haas.

Simon-Rey commented 7 months ago

Let me know if you need more @DominikPeters. It currently does not support irresolute outcomes.