xgillard
commented
3 years ago Hi, Thanks for your interest in my crate :-) I do believe that ddo might be useable in your case (but don't resent me if I'm wrong: there are a lot of details in your problem description so I might have skipped something).
Basically I would proceed as follow (this is where you should tell me if I forgot/skipped some details of your problem).
The structure describing a problem instance should maintain all the "shared" information.
struct Problem {
instrument_type: Vec<Instrument>, // for each variable the corresponding instrument type
compatibility_score: HashMap<(Instrument, Synthetizer), usize>, // compatibility score of pairing the given istrument on the given synthtizer
polyphony_limits: Vec<usize>, // used to build your initial state
}The structure of the state attached to a node should be something like
struct State {
poyphony_limit: Vec<usize>, // for each synthetizer, this field maintains the remaining "capacity" which can be used
}- You should have one variable per source channel (function nb_vars() returns N)
- You can easily impose all your feasibility constraints using the "domain()" method from the Problem.
- When you need to merge items (to compute the relaxation), you can do so by simply taking the maximum remaining capacity of a state.
I'll craft a sample solver for your problem so that you can get a more accurate idea of what I meant.
If you need some references to get a clearer view of what ddo can do, you might be interested in reading one of these papers:
- http://public.tepper.cmu.edu/jnh/BDDBBpost.pdf
- https://www.ijcai.org/Proceedings/2020/0757.pdf (this one presents ddo. It's very short and covers about the same as the readme)
- https://arxiv.org/abs/2104.11951 (to be published. This one tells you that you might want to spend a bit of time to define a rough upper bound (= very fast problem specific bounding) as that can lead to significan perf improvement)
Boscop
Hi, thanks for making this crate :) Is it suitable for solving the Assignment Problem but which is modified to allow one "destination" to be assigned to multiple "sources"? And there are also limits, it's not the case that it can be reduced to a balanced assignment problem and then leftover sources are assigned to their best-matching destination: In my use case (a hobby project) I want to do midi channel routing between up to N source channels (which each have an assigned GM instrument and a certain ADSR envelope and a certain maximum concurrent voices (their effective polyphony)) and M (often <=N but can be larger, too) destination channels (synthesizers), that each have a max polyphony limit and also a ADSR envelope and there is a certain compatibility score for each pairing of the possible 128 midi instruments and each of the synthesizers (because not every synth can play the timbre of every instrument). Without the polyphony limit, I could just treat it as an assignment problem (calculating the score of each pairing by only taking into account instrument and envelope compatibility) and use this crate to solve it, and then assign leftover source channels to their best-matching destination channel. But with the polyphony limit, considering each pair score in isolation is not valid, because the polyphony of a destination is used up by all sources, so they are competing in a knapsack-like way. This means that the global configuration has to be considered/scored as a whole. Not sure what kind of name this problem has, or which algorithm would be best. N and M are both up to 16, and it's important to find the best matching in the shortest time possible. Do you know which algorithm/approach (or existing crate) is most suitable for this? :)
I never used MDDs but I would read up about them, if this crate is suitable / if this problem can be modeled with them :)