This appears to be a knapsack / bin-packing problem, but I seem to have got stuck and could appreciate contributions.
Scenario 1: Tough (for me!) There is a one day conference with a set of (4 or more) sessions. The conference will be attended by a number of companies, each one being represented by a (1 or more) representatives.
Across sessions the number of representatives for each company will vary (and may be zero), with each individual having the same chance of being present as any other individual (so there is an increasing likelihood of a company being represented when it has more representatives).
There is a single row of seats in the conference. There are more than enough seats for the most popular session. (e.g., if the most popular session has 100 delegates, there could be 120 seats for the whole conference).
- A rep. belongs to one company
- A rep. must be seated in a session they are going to.
- A rep. must not change seats across consecutive sessions
- A rep. is assigned to one chair in each session they attend.
Goal To fit the constraints and priorities optimally. Example. 15 chairs, 4 companies (A-D), 4 sessions (S1-S4).
// Session attendees by company S1: A2 B6 C3 D3 S2: A4 B5 C1 D2 S3: A3 B3 C4 D1 S4: A5 B2 C5 D0 // Possible solution (I did this manually!) S1: [AA.BBBBBBCCCDDD] S2: [AAAABBBBBC...DD] S3: [AAA...BBBCCCC.D] S4: [AAAAA..BBCCCCC.]
Question How can I solve this algorithmically? The algorithm doesn't have to be particularly fast but it does need to yield working results.
Scenario 2: Tougher?! The same as above but the row of seats has enforced break points (like pillars, walkways, etc). I think this latter issue is merely a 'knapsack'-type modification to the above problem
Thoughts towards a solution It seems that it should be possible to have consecutive seating available in most cases, which implies that a solution could be found by identifying company-invariant seats by filling the minimum company representation across all sessions, leaving gaps between companies that are somehow calculated based on the variation of the company and it's neighbour.
It is trivial to find cases where there is only a partial solution, eg the following, but that's okay. I still need to get the best solution I can.
S1: [AAAACB] S2: [ACCCCB]
Edit: I managed to resolve this, using OR-Tools. It required 3 separate solvers in the end, in order to split the problem into tranches.
Tranche division is done with a solve for the rows, based on a count of seats to work per tranche. This uses two slack criteria to allow for (a) allocation wiggle room - and (b) one for an overflow (where there are large rows)!
Then a weight-change-over-each-session bin-packing variation to allocate organisations to the tranches.
Finally, seat allocation is managed. The seat allocation can manage about 100 representatives per tranche before it slows down due to scaling problems that seem to be inevitable with constraint programming systems. The constraints are as listed above. eg. for the constraint that one rep belongs to one company: