1
$\begingroup$

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).

Constraints

  • 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:

model.AddImplication(del_chairs[d_tuple], org_chairs[o_tuple])
$\endgroup$
1
$\begingroup$

I'd suggest formulating this as an instance of SAT or ILP, then using an off-the-shelf SAT or ILP solver. This smells like the kind of problem that might be NP-hard in general and thus it might not be reasonable to expect a general, efficient algorithm that always outputs the optimal solution.

For example, if you only wanted to find a solution that meets all of the constraints, and you ignore the priorities, then you could express this as a SAT instance easily. You could use a one-hot encoding, where the boolean variable $x_{i,j,k}$ if representative $i$ is assigned to seat $j$ in session $k$. Then each constraint can be translated into a logical predicate on these boolean variables and thus into SAT. I find the Z3 solver convenient for expressing these kinds of constraints.

To capture the priorities, you could introduce additional boolean variables, say $y_{i,k}$ is 1 (true) if representative $i$ changes seat after session $k$ or 0 (false) otherwise, and then add constraints to capture the relationship between the $x$'s and $y$'s, and finally minimize the sum of the $y$'s, or require that the sum of the $y$'s be below some threshold $\tau$ and use binary search on $\tau$. For that, pseudo-boolean inequalities or integer linear programming might be useful.

There are many details that would need to be filled in. I'll let you work out the details.

See, e.g., Express boolean logic operations in zero-one integer linear programming (ILP), Encoding 1-out-of-n constraint for SAT solvers, Reduce the following problem to SAT, When to use SAT vs Constraint Satisfaction?, https://stackoverflow.com/q/43081929/781723 for some relevant reading. The operations research community and tools (e.g., OR-Tools) might also be relevant.

$\endgroup$
  • $\begingroup$ @DW, Thanks for this hint. My current problem is that I don't even know how to describe / formulate the problem other than as a description - i.e. I'm not sure how to get -any- solution let alone a near-optimal one! $\endgroup$ – Konchog Sep 27 at 18:58
  • 1
    $\begingroup$ @Konchog, got it -- see edited answer for elaboration. $\endgroup$ – D.W. Sep 27 at 20:18
  • $\begingroup$ @DW, thanks a lot! Your advice is keeping me very busy - as these fields are new to me. I’m still struggling to find a way of encoding the ‘same seat’ criterion. Currently I am reading through the OR-Tools stuff, though Z3 looks very interesting too. $\endgroup$ – Konchog Sep 29 at 10:44
  • $\begingroup$ @DW, if you are remotely interested, I partially solved the problem of adjacency by looking at the candidates as weights - so a sort of knapsack. But this leaves me stuck with the question of contiguous seating!! $\endgroup$ – Konchog Oct 1 at 15:35
  • $\begingroup$ @Konchog, for adjacency, I would suggest having the representatives sit in order; then the requirement is that if rep $i$ is sitting in seat $j$, then rep $i+1$ is sitting in seat $j+1$, i.e., $x_{i,j,k} \implies x_{i+1,j+1,k}$. For "same seat in multiple sessions",if $x_{i,j,k}=1$ and $y_{i,k}=0$ then $x_{i,j,k+1}=1$; if $x_{i,j,k}=1$ and $y_{i,k}=1$ then $x_{i,j,k+1}=0$. I'm not sure what is the difference between adjacency vs contiguous seating. $\endgroup$ – D.W. Oct 1 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.