packing with time-variant weights

Question

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

Answer 1

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.