I am working on a formulation for a problem that seems similar to the bin packing problem. My problem variables include items that are to be placed in bins, special events that are conditionally required, and the bins themselves. The constraints include
Capacity constraints for the bins
Certain items cannot be in the same bin as other items
Certain items must be have a special event between them. For example, to get from item i to item j, a special event must occur. Based on certain properties of the item.
A sequence dependent constraint such that items must follow a particular order in the bins. For example, item i must come before items j,k (if they are in the same bin together) and therefore cannot be placed in the bin after them. This is determined by a property of the item.
The objective for this problem is to identify the least number of bins needed to store all of the items, with an upper bound on the number of special events allowed on a bin.
The most obvious formulation I can think of is to have binary variables x_ijk and y_ijk. Where index i is the item (or special event taking place), j is the bin, and k is the position on the bin. Using a triple index like this makes formulating the problem quite simple, but I believe for even a modest size (100 items), the problem size is massive. I expect encoding the variables this way will make the problem size large because I am after a feasible solution and therefore expect the number of items = number of bins = number of sequence position. This guarantees the edge cases of all items being placed on a single bin, and all items being associated to their own individual bins.
Is there another formulation that is more efficient that can be used to model this problem?