Emballage avec des poids variants dans le temps

Question

Cela semble être un problème de sac à dos / bac, mais il me semble que je suis resté coincé et j'ai pu apprécier les contributions.

Scénario 1: dur (pour moi!)Il y a une conférence d'une journée avec un ensemble de séances (4 ou plus). La conférence sera suivie par un certain nombre d'entreprises, chacune étant représentée par un (1 ou plus) représentants.

Dans toutes les séances, le nombre de représentants pour chaque entreprise variera (et peut être nul), chaque individu ayant les mêmes chances d'être présents que toute autre personne (il y a donc une probabilité croissante qu'une entreprise soit représentée lorsqu'elle a plus de représentants) .

Il y a une seule rangée de sièges dans la conférence. Il y a plus que suffisamment de sièges pour la session la plus populaire. (Par exemple, si la session la plus populaire a 100 délégués, il pourrait y avoir 120 sièges pour toute la conférence).

Contraintes

• Un représentant. appartient à une entreprise
• Un représentant. Doit être assis dans une session dans laquelle ils vont.
• Un représentant. ne doit pas changer de siège à travers les séances consécutives
• Un représentant. est affecté à une chaise à chaque session à laquelle ils assistent.

ObjectifPour s'adapter aux contraintes et aux priorités de manière optimale. Exemple. 15 chaises, 4 sociétés (AD), 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.]

QuestionComment puis-je résoudre ce problème algorithmique? L'algorithme ne doit pas être particulièrement rapide, mais il doit donner des résultats de travail.

Scénario 2: plus difficile ?!La même chose que ci-dessus, mais la rangée de sièges a appliqué des points de rupture (comme des piliers, des allées, etc.). Je pense que ce dernier problème n'est qu'une modification de type «Knipack» au problème ci-dessus

Réflexions envers une solutionIl semble qu'il soit possible d'avoir des sièges consécutifs disponibles dans la plupart des cas, ce qui implique qu'une solution pourrait être trouvée en identifiant les sièges invariants de l'entreprise en remplissant la représentation minimale de l'entreprise à toutes les séances, laissant les lacunes entre les entreprises qui sont en quelque sorte calculées en fonction de La variation de l'entreprise et de son voisin.

Il est trivial de trouver des cas où il n'y a qu'une solution partielle, par exemple ce qui suit, mais ça va. J'ai encore besoin d'obtenir la meilleure solution possible.

S1:   [AAAACB]
S2:   [ACCCCB]

Éditer: J'ai réussi à résoudre ce problème en utilisant Or-Tools. Il nécessitait 3 solveurs distincts à la fin, afin de diviser le problème en tranches.

La division Tranche est réalisée avec une résolution pour les lignes, basée sur un décompte de sièges pour travailler par tranche. Cela utilise deux critères de mou pour permettre (a) la marge de manœuvre d'allocation - et (b) une pour un débordement (où il y a de grandes rangées)!

Ensuite, une variation d'emballage du bac à changement de poids pour allouer des organisations aux tranches.

Enfin, l'allocation des sièges est gérée. L'allocation des sièges peut gérer environ 100 représentants par tranche avant de ralentir en raison de problèmes de mise à l'échelle qui semblent inévitables avec les systèmes de programmation de contraintes. Les contraintes sont énumérées ci-dessus. par exemple. Pour la contrainte qu'un représentant appartient à une entreprise:

model.AddImplication(del_chairs[d_tuple], org_chairs[o_tuple])