Need to add constraint single color for 1 bin (Bin Packing )

[sundar rathnam]

Hi ,

I am new to CP-Sat Solver and constraint programming. I am able to get the sample working fine.

I Want to add one more constraint for single color for single bin.

Any help on how to achieve this is highly appreciated.

Sample Code

-----------------------------------------------------------------------------------------

from ortools.sat.python import cp_model
from collections import Counter

class BinPacking:
    BOX_COEFFICIENT = 10000000

    def __init__(self):
        self.items = {
            1: {'volume': 33, 'weight': 50, 'quantity': 1, 'color': 10},
            2: {'volume': 45, 'weight': 30, 'quantity': 1, 'color': 11},
            3: {'volume': 10, 'weight': 20, 'quantity': 1, 'color': 10},
            4: {'volume': 12, 'weight': 25, 'quantity': 1, 'color': 12},
            5: {'volume': 1, 'weight': 2,   'quantity': 1, 'color': 11},
            6: {'volume': 22, 'weight': 28, 'quantity': 1, 'color': 12},
            7: {'volume': 50, 'weight': 68, 'quantity': 1, 'color': 11},
        }

        self.boxes = {
            1: {'volume': 40, 'weight': 600},
            2: {'volume': 100, 'weight': 1000},
            3: {'volume': 5, 'weight': 1000},
            4: {'volume': 150, 'weight': 500},
            5: {'volume': 120, 'weight': 1000},
        }

    def main(self):
        model = cp_model.CpModel()
        all_items = range(1, len(self.items) + 1)
        all_boxes = range(1, len(self.boxes) + 1)

        x = {}
        for i in all_items:
            for j in all_boxes:
                x[(i, j)] = model.NewIntVar(0, self.items[i]['quantity'], 'x_%i_%i' % (i, j))
               
             
        y = {}
        for j in all_boxes:
            y[j] = model.NewBoolVar('y[%i]' % j)

        for i in all_items:
            model.Add(sum(x[i, j] for j in self.boxes) == self.items[i]['quantity'])
           
                       
        for j in all_boxes:
            model.Add(sum(x[(i, j)] * self.items[i]['volume'] for i in all_items) <= y[j] * self.boxes[j]['volume'])
           

        model.Minimize(sum(y[j] * (self.BOX_COEFFICIENT + self.boxes[j]['volume']) for j in all_boxes))
       

        solver = cp_model.CpSolver()
        solver.parameters.log_search_progress = True
        solver.parameters.num_search_workers = 1 # Can be 8 or more for larger problems
        solver.parameters.linearization_level = 2 # Useful if the number of workers is 1
        status = solver.Solve(model)

        if status == cp_model.OPTIMAL:
            num_bins = 0
            for j in all_boxes:
                if solver.BooleanValue(y[j]):
                    bin_items = []
                    bin_volume = 0
                    bin_weight = 0
                    for i in all_items:
                        solution_value = solver.Value(x[i, j])
                        if solution_value > 0:
                            bin_items.append({i: solution_value})
                            bin_volume += solution_value * self.items[i]['volume']
                            bin_weight += solution_value * self.items[i]['weight']
                    if bin_volume > 0:
                        num_bins += 1
                        print('Box number', j)
                        print('  Items packed:', bin_items)
                        print('  Total volume:', bin_volume)
                        print('  Total weight:', bin_weight)
                        print()
            print()
            print('Number of boxes used:', num_bins)
            print('Time = ', solver.WallTime(), ' seconds')
        else:
            print('The problem does not have an optimal solution.')


if __name__ == '__main__':
    bp = BinPacking()
    bp.main()

---------------------------------------------------------------

Thanks

Sundar

[Laurent Perron]

for each bin, 

1 bool var per color. At_most_one of the them is true

for each item: item in bin implies color is true.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/a109d60e-c239-4cf6-b4be-37e272dcdb27n%40googlegroups.com.

[sundar rathnam]

Tried the following one but not working as expected.

1. color of the items  are not getting grouped binwise

2. Also found weight exceeded in one of the bin.

Any help would be appreciated.

Thanks 

================================================================

"""Solve a multiple knapsack problem using a MIP solver."""
from ortools.linear_solver import pywraplp


def main():
    data = {}
    data["weights"] = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36]
    data["values"] = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25]
    assert len(data["weights"]) == len(data["values"])
    data["num_items"] = len(data["weights"])
    data["all_items"] = range(data["num_items"])

    data["colors"] = [10, 11, 10, 10, 12, 10, 11, 10, 10, 11,10,10,11,10,10]
    data["num_colors"] = len(data["colors"])
    data["all_colors"] = range(data["num_colors"])
   
   
    data["bin_capacities"] = [100, 100, 100, 100, 100]
    data["num_bins"] = len(data["bin_capacities"])
    data["all_bins"] = range(data["num_bins"])

    # Create the mip solver with the SCIP backend.
    solver = pywraplp.Solver.CreateSolver("SCIP")
    if solver is None:
        print("SCIP solver unavailable.")
        return

    # Variables.
    # x[i, b] = 1 if item i is packed in bin b.
    x = {}
    for b in data["all_bins"]:
        for c in data["all_colors"]:
            for i in data["all_items"]:        
                x[i, c, b] = solver.BoolVar(f"x_{i}_{c}_{b}")

    # Constraints.
    # Each item is assigned to at most one bin.
    for i in data["all_items"]:
        solver.Add(sum(x[i, c, b] for b in data["all_bins"]) <= 1)

    for b in data["all_bins"]:
        solver.Add(
             sum(x[i, c, b]  for c in data["all_colors"] ) <= 1 )
             
    # The amount packed in each bin cannot exceed its capacity.
    for b in data["all_bins"]:
        for c in data["all_colors"]:
            solver.Add(
                sum(x[i, c, b] * data["weights"][i] for i in data["all_items"] )
                <= data["bin_capacities"][b]
            )

       
    # Objective.
    # Maximize total value of packed items.
    objective = solver.Objective()
    for i in data["all_items"]:
        for b in data["all_bins"]:
            for c in data["all_colors"]:
                objective.SetCoefficient(x[i, c, b],  1)
    objective.SetMaximization()

    #print(f"Solving with {solver.SolverVersion()}")
    status = solver.Solve()

    if status == pywraplp.Solver.OPTIMAL:
        print(f"Total packed value: {objective.Value()}")
        total_weight = 0
        for b in data["all_bins"]:
            print(f"Bin {b}")
            bin_weight = 0
            bin_value = 0
            for i in data["all_items"]:
                if x[i, c, b].solution_value() > 0:
                    print(
                        f"Item {i} weight: {data['weights'][i]} value: {data['values'][i]}"
                        f"\nItem {i} weight: {data['weights'][i]} value: {data['values'][i]}  color: {data['colors'][i]}"
                   
                    )
                    bin_weight += data["weights"][i]
                    bin_value += data["values"][i]
            print(f"Packed bin weight: {bin_weight}")
            print(f"Packed bin value: {bin_value}\n")
            total_weight += bin_weight
        print(f"Total packed weight: {total_weight}")

    else:
        print("The problem does not have an optimal solution.")

if __name__ == "__main__":
    main()

Result

======

Bin 0
Item 4 weight: 36 value: 35
Item 4 weight: 36 value: 35  color: 12
Item 9 weight: 24 value: 35
Item 9 weight: 24 value: 35  color: 11
Item 14 weight: 36 value: 25
Item 14 weight: 36 value: 25  color: 10
Packed bin weight: 96
Packed bin value: 95

Bin 1
Item 3 weight: 36 value: 50
Item 3 weight: 36 value: 50  color: 10
Item 11 weight: 30 value: 10
Item 11 weight: 30 value: 10  color: 10
Packed bin weight: 66
Packed bin value: 60

Bin 2
Item 1 weight: 30 value: 30
Item 1 weight: 30 value: 30  color: 11
Item 8 weight: 36 value: 30
Item 8 weight: 36 value: 30  color: 10
Item 10 weight: 30 value: 45
Item 10 weight: 30 value: 45  color: 10
Packed bin weight: 96
Packed bin value: 105

Bin 3
Item 7 weight: 42 value: 40
Item 7 weight: 42 value: 40  color: 10
Item 13 weight: 36 value: 30
Item 13 weight: 36 value: 30  color: 10
Packed bin weight: 78
Packed bin value: 70

Bin 4
Item 2 weight: 42 value: 25
Item 2 weight: 42 value: 25  color: 10
Item 12 weight: 42 value: 20
Item 12 weight: 42 value: 20  color: 11
Packed bin weight: 84
Packed bin value: 45

Total packed weight: 420

[Mizux Seiha]

Prefer to use the CP-SAT solver so you can easy write the implication

```
"""Solve a multiple knapsack problem using the CP-SAT solver."""
from ortools.sat.python import cp_model

def main():
    data = {}
    data["weights"] = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36]
    data["values"] = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25]
    assert len(data["weights"]) == len(data["values"])
    data["num_items"] = len(data["weights"])
    data["all_items"] = range(data["num_items"])

    colors = [10, 11, 12]

    data["colors"] = [10, 11, 10, 10, 12, 10, 11, 10, 10, 11, 10, 10, 11, 10, 10]

    for c in data["colors"]:
        assert c in colors, f"Color {c} unknow !"
    assert len(data["colors"]) == len(data["values"])

    data["num_colors"] = len(data["colors"])
    data["all_colors"] = range(data["num_colors"])

    data["bin_capacities"] = [100, 100, 100, 100, 100]
    data["num_bins"] = len(data["bin_capacities"])
    data["all_bins"] = range(data["num_bins"])

    # Create the CP-SAT model.
    model = cp_model.CpModel()

    # Variables.
    # x[i, b] = 1 if item i is packed in bin b.
    x = {}
    for b in data["all_bins"]:

            for i in data["all_items"]:

                x[i, b] = model.new_bool_var(f"x_{i}_{b}")
   
    # y[c, b] = 1 if color c is packed in bin b.
    y = {}

    for b in data["all_bins"]:

            for c in colors:
                y[c, b] = model.new_bool_var(f"y_{c}_{b}")

    # Constraints.
    # Each item is assigned to at most one bin.
    for i in data["all_items"]:

        model.add(sum(x[i, b] for b in data["all_bins"]) <= 1)

    # The amount packed in each bin cannot exceed its capacity.
    for b in data["all_bins"]:

        model.add(
            sum(x[i, b] * data["weights"][i] for i in data["all_items"])

            <= data["bin_capacities"][b]
        )

    # a color is present in a bin if at least one item of this color is present in the bin

    for b in data["all_bins"]:

            for c in colors:
                model.add(sum(x[i, b] for i in data["all_items"] if data["colors"][i] == c) >= 1).only_enforce_if(y[c, b])
                model.add(sum(x[i, b] for i in data["all_items"] if data["colors"][i] == c) == 0).only_enforce_if(y[c, b].negated())

    # Each bin has at most one color

    for b in data["all_bins"]:

        model.add(sum(y[c, b] for c in colors) <= 1)

    # Objective.
    # Maximize total value of packed items.

    model.maximize(
       sum(x[i, b] * data['values'][i] for i in data["all_items"] for b in data["all_bins"])
    )

    # Solve
    solver = cp_model.CpSolver()
    status = solver.solve(model)

    # Print solution
    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
        print(f"Total packed value: {solver.objective_value}")
        total_weight = 0
        total_value = 0

        for b in data["all_bins"]:
            print(f"Bin {b}")
            bin_weight = 0
            bin_value = 0

            bin_colors = set()

            for i in data["all_items"]:

                if solver.boolean_value(x[i, b]):
                    print(f"Item {i} weight: {data['weights'][i]} value: {data['values'][i]}  color: {data['colors'][i]}")

                    bin_weight += data["weights"][i]
                    bin_value += data["values"][i]

                    bin_colors.add(data["colors"][i])

            print(f"Packed bin weight: {bin_weight}")

            print(f"Packed bin value: {bin_value}")
            print(f"Color bin value: {bin_colors}\n")
            total_weight += bin_weight
            total_value += bin_value

        print(f"Total packed weight: {total_weight}")

        print(f"Total packed value: {total_value}")

    else:
        print("The problem does not have an optimal solution.")


if __name__ == "__main__":
    main()

```

* Use of CP-SAT instead of MPSolver since it's easier to write channelling
* Add a y[c, b] variable which will be true if color c is in bin b

* Here the channeling stuff
```python
   # a color is present in a bin if at least one item of this color is present in the bin

    for b in data["all_bins"]:

            for c in colors:
                model.add(sum(x[i, b] for i in data["all_items"] if data["colors"][i] == c) >= 1).only_enforce_if(y[c, b])
                model.add(sum(x[i, b] for i in data["all_items"] if data["colors"][i] == c) == 0).only_enforce_if(y[c, b].negated())
```
ref: https://github.com/google/or-tools/blob/main/ortools/sat/docs/channeling.md

possible output (note, I've used `main` branch):
%./build/python/venv/bin/python /tmp/plop.py
Total packed value: 370.0
Bin 0

Item 10 weight: 30 value: 45  color: 10

Item 11 weight: 30 value: 10  color: 10

Item 14 weight: 36 value: 25  color: 10
Packed bin weight: 96

Packed bin value: 80
Color bin value: {10}

Bin 1
Item 3 weight: 36 value: 50  color: 10

Item 7 weight: 42 value: 40  color: 10

Packed bin weight: 78
Packed bin value: 90
Color bin value: {10}

Bin 2

Item 2 weight: 42 value: 25  color: 10

Item 13 weight: 36 value: 30  color: 10
Packed bin weight: 78

Packed bin value: 55
Color bin value: {10}

Bin 3
Item 5 weight: 48 value: 30  color: 10

Item 8 weight: 36 value: 30  color: 10

Packed bin weight: 84
Packed bin value: 60
Color bin value: {10}

Bin 4

Item 1 weight: 30 value: 30  color: 11

Item 9 weight: 24 value: 35  color: 11

Item 12 weight: 42 value: 20  color: 11

Packed bin weight: 96
Packed bin value: 85
Color bin value: {11}

Total packed weight: 432
Total packed value: 370

[sundar rathnam]

Tonnes of thanks Mizu, i m not sure hot to use the variables and channeling.

Got a better understanding on how to use them.

This solution works like a charm.