Multiple knapsack problem with range constraint

[Skrallin]

Hi,

I am currently working with the multiple knapsack problem and started with the base from: https://developers.google.com/optimization/bin/multiple_knapsack. I have multiple knapsacks what I am trying to fill with boxes that have different sizes. The knapsack has a maximum height. But the constraint that I want to add is that the height difference between items cannot be higher than a X amount.

For example I have a box that has a height of 20 and the maximum height difference between the boxes in the knapsack is 60. So the maximum height of a box in this knapsack can be 80. An example:

Boxes height = [20, 30, 20, 80, 100, 120, 60]

The boxes that can be included in the knapsack when a box with the height of 20 is included in the knapsack are: [30, 20, 80, 60]. So the boxes with the height [100, 120] should be excluded as option for this knapsack.

Could someone help me with this problem. Thanks in advance!

[Skrallin]

Is my question clear? Or should I explain a bit more about the problem?

Op woensdag 17 november 2021 om 10:38:07 UTC+1 schreef Skrallin:

[Priidik Vilumaa]

Hello,

I guess you can define a new variable for each knapsack that captures the maximum height (and another one for minimum) of items in that bag. Then constrain the difference of max - min to be no more than X.

It is somewhat easier using CP-SAT, but I dont think it should make a real difference. In CP-SAT, the tools to use are roughly:

intermediary integer variables (your binary variable x multiplied by height)

AddMaxEquality(new_max_var_for_this_bag, height_vars_for_this_bag)

AddMinEquality(...)

model.Add(new_max_var_for_this_bag - new_min_var_for_this_bag <= 60)

In MIP/LP you can substitute AddMaxEquality with something like x[i] * height[i] <= y for i in I.

For each bag, do similarly for the minimum,and then constrain the difference.

Hope this helps.

Best,

Priidik

[Laurent Perron]

I would first try by enumerating conflicts

if a and b are incompatible:

  model.AddBoolOr([a_is_selected.Not(), b_is_selected.Not()])

Then use the normal knapsack model.

I do recommend using CP-SAT (with parallelism enabled).

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/bd6a364f-308b-44c0-8cf6-7ec71f1a0926n%40googlegroups.com.

[Mizux Seiha]

# [START program]

# [START import]

from ortools.sat.python import cp_model

# [END import]

# [START program_part1]

# [START data_model]

def create_data_model():

    """Create the data for the example."""

    data = {}

    heights = [20, 30, 20, 80, 100, 120, 60]

    values = [20, 30, 20, 80, 100, 120, 60]

    data['heights'] = heights

    data['values'] = values

    data['height_list'] = sorted(set(data['heights']))

    data['items'] = list(range(len(data['heights'])))

    data['num_items'] = len(data['items'])

    num_bins = 3

    data['bins'] = list(range(num_bins))

    data['bin_capacities'] = [200, 200, 200]

    return data

# [END data_model]

def main():

    # [START data]

    data = create_data_model()

    # [END data]

    # [END program_part1]

    # [START solver]

    model = cp_model.CpModel()

    # [END solver]

    # [START program_part2]

    # [START variables]

    # Variables

    # x[i, j] = 1 if item i is packed in bin j.

    x = {}

    for i in data['items']:

        for j in data['bins']:

            x[i, j] = model.NewBoolVar(f'x_{i}_{j}')

    # y[i, j] = 1 if an item of size i is packed in bin j.

    y = {}

    for i in data['height_list']:

        for j in data['bins']:

            y[i, j] = model.NewBoolVar(f'y_{i}_{j}')

    # [END variables]

    # [START constraints]

    # Constraints

    # Each item can be in at most one bin.

    for i in data['items']:

        model.Add(sum(x[i, j] for j in data['bins']) <= 1)

    # The amount packed in each bin cannot exceed its capacity.

    for j in data['bins']:

        model.Add(

            sum(x[i, j] * data['heights'][i]

                for i in data['items']) <= data['bin_capacities'][j])

    # Implement y[i, j] == (items of size i >= 1).

    for i in data['height_list']:

        for j in data['bins']:

            cst = sum(x[k, j] for k in data['items'] if i == data['heights'][k])

            model.Add(cst >= 1).OnlyEnforceIf(y[i, j])

            model.Add(cst < 1).OnlyEnforceIf(y[i, j].Not())

    # limit diff to 60

    for j in data['bins']:

        model.Add(

            sum([y[20, j], y[100, j]]) <= 1)

        model.Add(

            sum([y[20, j], y[120, j]]) <= 1)

        model.Add(

            sum([y[30, j], y[120, j]]) <= 1)

    # [END constraints]

    # [START objective]

    # Objective

    objective_terms = []

    for i in data['items']:

        for j in data['bins']:

            objective_terms.append(x[i, j] * data['values'][i])

    model.Maximize(sum(objective_terms))

    # [END objective]

    # Creates a solver and solves the model.

    # [START solve]

    solver = cp_model.CpSolver()

    status = solver.Solve(model)

    # [END solve]

    # [START print_solution]

    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:

        print('Items total value (upper bound):', sum(data['values']))

        print('Total packed value:', solver.ObjectiveValue())

        total_height = 0

        for j in data['bins']:

            bin_height = 0

            bin_value = 0

            print('Bin ', j, '\n')

            for i in data['height_list']:

                print(f"Has items of size {i}:", bool(solver.Value(y[i,j])))

            for i in data['items']:

                if solver.Value(x[i, j]) > 0:

                    print('Item', i, '- height:', data['heights'][i], ' value:', data['values'][i])

                    bin_height += data['heights'][i]

                    bin_value += data['values'][i]

            print('Packed bin weight:', bin_height)

            print('Packed bin value:', bin_value)

            print()

            total_height += bin_height

        print('Total packed weight:', total_height)

    else:

        print('The problem does not have an optimal solution.')

    # [END print_solution]

if __name__ == '__main__':

    main()

# [END program_part2]

# [END program]

possible output:

 %./plop.py

Items total value (upper bound): 430

Total packed value: 430.0

Bin  0 

Has items of size 20: True

Has items of size 30: True

Has items of size 60: False

Has items of size 80: False

Has items of size 100: False

Has items of size 120: False

Item 0 - height: 20  value: 20

Item 1 - height: 30  value: 30

Item 2 - height: 20  value: 20

Packed bin weight: 70

Packed bin value: 70

Bin  1 

Has items of size 20: False

Has items of size 30: False

Has items of size 60: False

Has items of size 80: True

Has items of size 100: True

Has items of size 120: False

Item 3 - height: 80  value: 80

Item 4 - height: 100  value: 100

Packed bin weight: 180

Packed bin value: 180

Bin  2 

Has items of size 20: False

Has items of size 30: False

Has items of size 60: True

Has items of size 80: False

Has items of size 100: False

Has items of size 120: True

Item 5 - height: 120  value: 120

Item 6 - height: 60  value: 60

Packed bin weight: 180

Packed bin value: 180

Total packed weight: 430