Rearrange 'x' piles of items into eight possible locations/bins based on item color and length

Question

I have an optimization problem that I believe is a variant of the 'bin packing problem with precedence', but I'm unsure of if that is the correct paradigm to work with and I'm not having a huge amount of success searching for how to implement this problem and my desired constraints.

What I am trying to implement is this:

• I have 'x' input stacks of items which have two key parameters - color and length (see figure)
• I want to rearrange these input stacks of items into eight possible output locations - this number of locations/bins is fixed. I don't necessarily need to use all eight, but there is no possibility of more.
• My preference for placing items in locations/bins are:
  1. Colors grouped together
  2. Longer items cannot be stacked on top of shorter items

In addition:

• I can only access the top item of each input stack at any time
• I can only handle each item once

As noted, my first issue is understanding what type of problem this is so I can implement the appropriate framework.

From what I understand I have hard constraints (eight final locations, only access top item from each input stack) and soft constraints (group colors, no longer items on top of shorter items). Eventually I would like to add further soft constraints (e.g. preference taking items from input stack 1 first).

I have tried to repurpose an OR-Tools example to formulate my problem, but the output is not as expected and I'm not sure if it's because I'm going about this incorrectly, or I've just not formulated the problem/constraints properly.

from ortools.linear_solver import pywraplp

# Sample data representing the objects in the initial stacks
initial_stacks = [
    [{'colour': 'red', 'length': '3'}, {'colour': 'blue', 'length': '4'}, {'colour': 'red', 'length': '3'}],
    [{'colour': 'blue', 'length': '2'}, {'colour': 'green', 'length': '4'}, {'colour': 'red', 'length': '4'}],
    [{'colour': 'green', 'length': '2'}, {'colour': 'red', 'length': '3'}, {'colour': 'blue', 'length': '3'}],
    [{'colour': 'red', 'length': '4'}, {'colour': 'red', 'length': '3'}, {'colour': 'blue', 'length': '3'}]
]
num_initial_stacks = len(initial_stacks)

# Create the solver
solver = pywraplp.Solver.CreateSolver('SCIP')

# Create decision variables
num_new_stacks = 8
num_objects = sum(len(stack) for stack in initial_stacks)
num_colors = len(set(obj['colour'] for stack in initial_stacks for obj in stack))
x = {}
for i in range(num_objects):
    for j in range(num_new_stacks):
        for c in range(num_colors):
            x[i, j, c] = solver.BoolVar(f'x[{i},{j},{c}]')

# Set constraints
# Each object is placed in only one stack and one length within each stack
for i in range(num_objects):
    solver.Add(solver.Sum(x[i, j, c] for j in range(num_new_stacks) for c in range(num_colors)) == 1)

# Grouping constraints: Objects with the same colour are grouped together
for c in range(num_colors):
    for j in range(num_new_stacks):
        solver.Add(solver.Sum(x[i, j, c] for i in range(num_objects)) <= 1)

# Objective function: Maximize the number of grouped objects
objective = solver.Objective()
for i in range(num_objects):
    for j in range(num_new_stacks):
        for c in range(num_colors):
            objective.SetCoefficient(x[i, j, c], 1)
objective.SetMaximization()

# Solve the problem
status = solver.Solve()

# Print the solution
if status == pywraplp.Solver.OPTIMAL:
    print('Objective value:', objective.Value())
    for j in range(num_new_stacks):
        stack = []
        for i in range(num_objects):
            for c in range(num_colors):
                if x[i, j, c].solution_value() == 1:
                    stack.append((f'Object {i}', f'Color {c}'))
        print(f'New Stack {j+1}:', stack)
else:
    print('The problem does not have an optimal solution.')

which produces the output:

Objective value: 12.0
New Stack 1: [('Object 0', 'Color 0'), ('Object 1', 'Color 1'), ('Object 2', 'Color 2')]
New Stack 2: [('Object 3', 'Color 0'), ('Object 4', 'Color 1'), ('Object 5', 'Color 2')]
New Stack 3: [('Object 6', 'Color 0'), ('Object 7', 'Color 1'), ('Object 8', 'Color 2')]
New Stack 4: [('Object 9', 'Color 0'), ('Object 10', 'Color 1'), ('Object 11', 'Color 2')]
New Stack 5: []
New Stack 6: []
New Stack 7: []
New Stack 8: []

Answer 1

You can consult the Towers of Hanoi algorithm Still you want to use optimization then define binary decision variables $ x_{i,b}$ for $ i$ is index for your objects & $ b$ represents your bin.
Create two types of sets/dictionaries:
$C_i = \{i \}$ where object $i$ has color $C$
Another set: ordered pairs of objects according to their lenghts $ L=\{ (i,j) : L_i \le L_j \}$\

Optional varibles depending upon your objective
binary variable $ z_{c,b}$ indicating if a color $c$ is assigned to a bin $b$
binary $ \delta_b$ indicating if a bin $b$ is used at all. useful if you want to use an objective.

Constraints
To capture ordering of objects according to their lengths you can use precedence constraints either as

(1) $ x_{j,b} \le x_{i,b} \ \ \forall b \ \ \forall (i,j) \in L $
or
(1) $x_{i,b}+x_{j,b} - 1 \le My_{i,j} \ \ \forall b \ \ \forall (i,j) \in L$ with additional binaries $ y_{i,j} \ \forall (i,j) \in L$ similar to precedence constraints if you want to track it.

(2) $z_{c,b} \le \sum_{i \in c} x_{i,b} \le \vert c \vert z_{c,b} \quad \forall b \ \ \forall c \in $ Colors

(3) $ 1 \le \sum_b z_{c,b} \le U \ \ \forall c$
here you can choose a value of $U$ to restrict how many bins objects of a color $c$ will be distributed to or choose $ \sum_b \delta_b$.

(4) $ \delta_b \le \sum_i x_{i,b} \le B\delta_b \ \ \forall b$
where $ B$ is number of bins

(5) $\sum_b x_{i,b} = 1 \ \ \forall i $

Objective (optional) $ \min \sum_b \delta_{b} $