jmarca/README.md

## README.md

      
    Raw
  

              README.md
            
          
    If you edit the source, and run with data['max_pseudoaxle_load'] = 300, then the fake axle load thing is not binding and the solver will put the loads wherever it wants.  For example:
Bin 0 

{'position': 0, 'item': 10, 'weight': 30, 'value': 45, 'length': 2}
{'position': 2, 'item': 12, 'weight': 42, 'value': 20, 'length': 2}
{'position': 4, 'item': 3, 'weight': 36, 'value': 50, 'length': 12}

Sum of item lengths 16
Packed bin weight: 108
Packed bin value: 115 

Bin 1 

{'position': 0, 'item': 14, 'weight': 36, 'value': 25, 'length': 2}
{'position': 2, 'item': 1, 'weight': 30, 'value': 30, 'length': 15}

Sum of item lengths 17
Packed bin weight: 66
Packed bin value: 55 

Bin 2 

{'position': 0, 'item': 5, 'weight': 48, 'value': 30, 'length': 2}
{'position': 2, 'item': 7, 'weight': 42, 'value': 40, 'length': 14}

Sum of item lengths 16
Packed bin weight: 90
Packed bin value: 70 

Bin 3 

{'position': 0, 'item': 4, 'weight': 36, 'value': 35, 'length': 12}
{'position': 12, 'item': 6, 'weight': 42, 'value': 15, 'length': 4}

Sum of item lengths 16
Packed bin weight: 78
Packed bin value: 50 

Bin 4 

{'position': 0, 'item': 9, 'weight': 24, 'value': 35, 'length': 15}
{'position': 15, 'item': 8, 'weight': 36, 'value': 30, 'length': 4}

Sum of item lengths 19
Packed bin weight: 60
Packed bin value: 65 

Total packed weight: 402
Total packed value: 355

If you edit the source, and run with data['max_pseudoaxle_load'] = 100, then the fake axle load thing is binding and the solver will put the heavier loads nearer to position 0, and the longer loads towards the last position (where they will affect fewer other items).  For example:
Bin 0 

{'position': 0, 'item': 14, 'weight': 36, 'value': 25, 'length': 2}
{'position': 2, 'item': 4, 'weight': 36, 'value': 35, 'length': 12}

Sum of item lengths 14
Packed bin weight: 72
Packed bin value: 60 

Bin 1 

{'position': 0, 'item': 8, 'weight': 36, 'value': 30, 'length': 4}
{'position': 4, 'item': 9, 'weight': 24, 'value': 35, 'length': 15}

Sum of item lengths 19
Packed bin weight: 60
Packed bin value: 65 

Bin 2 

{'position': 0, 'item': 12, 'weight': 42, 'value': 20, 'length': 2}
{'position': 2, 'item': 3, 'weight': 36, 'value': 50, 'length': 12}

Sum of item lengths 14
Packed bin weight: 78
Packed bin value: 70 

Bin 3 

{'position': 0, 'item': 10, 'weight': 30, 'value': 45, 'length': 2}
{'position': 2, 'item': 13, 'weight': 36, 'value': 30, 'length': 12}

Sum of item lengths 14
Packed bin weight: 66
Packed bin value: 75 

Bin 4 

{'position': 0, 'item': 5, 'weight': 48, 'value': 30, 'length': 2}
{'position': 2, 'item': 7, 'weight': 42, 'value': 40, 'length': 14}

Sum of item lengths 16
Packed bin weight: 90
Packed bin value: 70 

Total packed weight: 366
Total packed value: 340


## multiple_knapsack_fake_position_loads.py
# Derived from multiple_knapsack_sat.py
#
# Copyright 2010-2018 Google LLC
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
# [START program]
"""Solves a multiple knapsack problem using the CP-SAT solver."""

# [START import]
from ortools.sat.python import cp_model
# [END import]


# [START data_model]
def create_data_model():
    """Create the data for the example."""
    data = {}
    weights = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36]
    values = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25]
    lengths = [12, 15, 16, 12, 12, 2, 4, 14, 4, 15, 2, 11, 2, 12, 2]
    data['num_items'] = len(weights)
    data['all_items'] = range(data['num_items'])
    data['weights'] = weights
    data['values'] = values
    data['lengths'] = lengths
    data['bin_capacities'] = [120, 100, 100, 100, 150]
    # data['bin_axle_loads'] = [100, 100, 100, 100, 100]
    data['num_bins'] = len(data['bin_capacities'])
    data['all_bins'] = range(data['num_bins'])
    data['length_wagon'] = 20
    data['max_pseudoaxle_load'] = 100
    return data

# [END data_model]


# [START solution_printer]
def print_solutions(data, solver, x, positions):
    """Display the solution."""
    total_weight = 0
    total_value = 0
    for b in data['all_bins']:
        print('Bin', b, '\n')
        bin_weight = 0
        bin_value = 0
        item_lengths = 0
        last_position_ends = 0
        loaded_items = []
        for idx, val in enumerate(data['weights']):
            if solver.Value(x[(idx, b)]) > 0:
                loaded_items.append({"position": solver.Value(positions[idx]),
                                     "item": idx,
                                     "weight": val,
                                     "value": data['values'][idx],
                                     "length": data['lengths'][idx]})
                item_lengths += data['lengths'][idx]
                bin_weight += val
                bin_value += data['values'][idx]
        loaded_items.sort(key=lambda k: k['position'])
        for item in loaded_items:
            print(item)
        print(f"\nSum of item lengths {item_lengths}")
        print('Packed bin weight:', bin_weight)
        print('Packed bin value:', bin_value, '\n')
        total_weight += bin_weight
        total_value += bin_value
    print('Total packed weight:', total_weight)
    print('Total packed value:', total_value)

# [END solution_printer]


def compute_item_load(weight, dist, axledist=2):
    constant = int(weight / axledist)
    load = constant + constant * dist
    return load


def main():
    # [START data]
    data = create_data_model()
    # [END data]

    # [START model]
    model = cp_model.CpModel()
    # [END model]

    # Main variables.
    # [START variables]
    x = {}
    for idx in data['all_items']:
        for b in data['all_bins']:
            x[(idx, b)] = model.NewIntVar(0, 1, f'x_{idx}_{b}')
    max_value = sum(data['values'])
    # value[b] is the value of bin b when packed.
    value = [
        model.NewIntVar(0, max_value, f'value_{b}') for b in data['all_bins']
    ]
    for b in data['all_bins']:
        model.Add(value[b] == sum(
            x[(i, b)] * data['values'][i] for i in data['all_items']))
    # [END variables]

    # item_loaded = [model.NewBoolVar(f"item_{idx} is loaded")
    #                for idx in data['all_items']]

    max_wagon_length = data['length_wagon']
    positions = [model.NewIntVar(0, max_wagon_length - data['lengths'][idx], f'position of item {idx}')
                for idx in data['all_items']]

    max_load = max(data['weights']) * data['length_wagon']
    item_loads = [model.NewIntVar(0, max_load, f"load for item {idx}")
                  for idx, p in enumerate(positions)]

    # [START constraints]
    # Each item can be in at most one bin.
    is_loaded = []
    for idx in data['all_items']:
        item_is_loaded = model.NewIntVar(0, 1, f"item {idx} is loaded somewhere")
        model.Add(item_is_loaded == sum(x[idx, b] for b in data['all_bins']))
        is_loaded.append(item_is_loaded)
        model.Add(item_loads[idx] == compute_item_load(data["weights"][idx], positions[idx])).OnlyEnforceIf(item_is_loaded)
        model.Add(item_loads[idx] == 0).OnlyEnforceIf(item_is_loaded.Not())

    # The amount packed in each bin cannot exceed its capacity.
    for b in data['all_bins']:
        # for bin capacities
        model.Add(
            sum(x[(i, b)] * data['weights'][i]
                for i in data['all_items']) <= data['bin_capacities'][b])
        # limit each bin's pseudo axle loads
        loaded_weights = []
        for i in data['all_items']:
            loaded_weight = model.NewIntVar(0, 10000, f"item {i} weight in bin {b}")
            model.Add(loaded_weight == item_loads[i]).OnlyEnforceIf(x[(i, b)])
            model.Add(loaded_weight == 0).OnlyEnforceIf(x[(i, b)].Not())
            loaded_weights.append(loaded_weight)
        model.Add(sum(loaded_weights) <= data['max_pseudoaxle_load'])

    literals = {}

    for bin_number, bin in enumerate(data['all_bins']):
        arcs = []  # accumulate the graph edges
        for item_number, item in enumerate(data['all_items']):
            # might be first, might not.
            start_lit = model.NewBoolVar(f"item {item} is first in  bin {bin}")
            # item_node = bin_number * num_items + item_number + 1
            item_node = item_number + 1
            arcs.append([0, item_node, start_lit])
            end_lit = model.NewBoolVar(f"item {item} is last in  bin {bin}")
            arcs.append([item_node, 0, end_lit])

            # self loop in case this item is not loaded
            skip_lit = model.NewBoolVar(f"item {item} is skipped for bin {bin}")
            arcs.append([item_node, item_node, skip_lit])

            literals[(item_number, bin_number)] = {}
            literals[(item_number, bin_number)]['start'] = start_lit
            literals[(item_number, bin_number)]['end'] = end_lit
            literals[(item_number, bin_number)]['skip'] = skip_lit

            model.Add(skip_lit == 1).OnlyEnforceIf(x[(item_number, bin_number)].Not())
            model.Add(skip_lit == 0).OnlyEnforceIf(x[(item_number, bin_number)])

            model.Add(positions[item_number] == 0).OnlyEnforceIf(start_lit)

            for next_item_number, next_item in enumerate(data['all_items']):
                if next_item_number == item_number:
                    continue
                # next_item_node = bin_number * num_items + next_item_number + 1
                next_item_node = next_item_number + 1

                i_j_lit = model.NewBoolVar(f"item {next_item} follows item {item} in bin {bin}")

                literals[(item_number, bin_number)][f"next_{next_item_number}"] = i_j_lit

                arcs.append([item_node, next_item_node, i_j_lit])

                length_of_preceding_container = data['lengths'][item_number]
                model.Add(positions[next_item_number] == positions[item_number] +
                          length_of_preceding_container).OnlyEnforceIf(i_j_lit)


        # create the Circuit constraint
        # print(arcs)
        model.AddCircuit(arcs)

    #bin_arcs.append(arcs)
    # [END constraints]

    # [START objective]
    # Maximize total value of packed items.
    model.Maximize(sum(value))
    # [END objective]

    # [START solver]
    solver = cp_model.CpSolver()
    # [END solver]

    solver.parameters.log_search_progress = True
    solver.parameters.max_time_in_seconds = 300
    solver.parameters.num_search_workers = 9

    # [START solve]
    status = solver.Solve(model)
    # [END solve]

    # [START print_solution]
    if status == cp_model.OPTIMAL:
        for i, l in enumerate(item_loads):
            print(f"item {i}, weight is {data['weights'][i]}, is is loaded? {solver.Value(is_loaded[i])},  load is {solver.Value(l)}")
        # for key, value in literals.items():
        #     for kk, vv in value.items():
        #         print(f"{key}: {kk} {vv} is {solver.Value(vv)}")
        print_solutions(data, solver, x, positions)
    else:
        print('you messed up dude')

    # [END solutions_printer]


if __name__ == '__main__':
    main()
# [END program]
	# Derived from multiple_knapsack_sat.py
	#
	# Copyright 2010-2018 Google LLC
	# Licensed under the Apache License, Version 2.0 (the "License");
	# you may not use this file except in compliance with the License.
	# You may obtain a copy of the License at
	#
	# http://www.apache.org/licenses/LICENSE-2.0
	#
	# Unless required by applicable law or agreed to in writing, software
	# distributed under the License is distributed on an "AS IS" BASIS,
	# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	# See the License for the specific language governing permissions and
	# limitations under the License.
	# [START program]
	"""Solves a multiple knapsack problem using the CP-SAT solver."""

	# [START import]
	from ortools.sat.python import cp_model
	# [END import]


	# [START data_model]
	def create_data_model():
	"""Create the data for the example."""
	data = {}
	weights = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36]
	values = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25]
	lengths = [12, 15, 16, 12, 12, 2, 4, 14, 4, 15, 2, 11, 2, 12, 2]
	data['num_items'] = len(weights)
	data['all_items'] = range(data['num_items'])
	data['weights'] = weights
	data['values'] = values
	data['lengths'] = lengths
	data['bin_capacities'] = [120, 100, 100, 100, 150]
	# data['bin_axle_loads'] = [100, 100, 100, 100, 100]
	data['num_bins'] = len(data['bin_capacities'])
	data['all_bins'] = range(data['num_bins'])
	data['length_wagon'] = 20
	data['max_pseudoaxle_load'] = 100
	return data

	# [END data_model]


	# [START solution_printer]
	def print_solutions(data, solver, x, positions):
	"""Display the solution."""
	total_weight = 0
	total_value = 0
	for b in data['all_bins']:
	print('Bin', b, '\n')
	bin_weight = 0
	bin_value = 0
	item_lengths = 0
	last_position_ends = 0
	loaded_items = []
	for idx, val in enumerate(data['weights']):
	if solver.Value(x[(idx, b)]) > 0:
	loaded_items.append({"position": solver.Value(positions[idx]),
	"item": idx,
	"weight": val,
	"value": data['values'][idx],
	"length": data['lengths'][idx]})
	item_lengths += data['lengths'][idx]
	bin_weight += val
	bin_value += data['values'][idx]
	loaded_items.sort(key=lambda k: k['position'])
	for item in loaded_items:
	print(item)
	print(f"\nSum of item lengths {item_lengths}")
	print('Packed bin weight:', bin_weight)
	print('Packed bin value:', bin_value, '\n')
	total_weight += bin_weight
	total_value += bin_value
	print('Total packed weight:', total_weight)
	print('Total packed value:', total_value)

	# [END solution_printer]


	def compute_item_load(weight, dist, axledist=2):
	constant = int(weight / axledist)
	load = constant + constant * dist
	return load


	def main():
	# [START data]
	data = create_data_model()
	# [END data]

	# [START model]
	model = cp_model.CpModel()
	# [END model]

	# Main variables.
	# [START variables]
	x = {}
	for idx in data['all_items']:
	for b in data['all_bins']:
	x[(idx, b)] = model.NewIntVar(0, 1, f'x_{idx}_{b}')
	max_value = sum(data['values'])
	# value[b] is the value of bin b when packed.
	value = [
	model.NewIntVar(0, max_value, f'value_{b}') for b in data['all_bins']
	]
	for b in data['all_bins']:
	model.Add(value[b] == sum(
	x[(i, b)] * data['values'][i] for i in data['all_items']))
	# [END variables]

	# item_loaded = [model.NewBoolVar(f"item_{idx} is loaded")
	# for idx in data['all_items']]

	max_wagon_length = data['length_wagon']
	positions = [model.NewIntVar(0, max_wagon_length - data['lengths'][idx], f'position of item {idx}')
	for idx in data['all_items']]

	max_load = max(data['weights']) * data['length_wagon']
	item_loads = [model.NewIntVar(0, max_load, f"load for item {idx}")
	for idx, p in enumerate(positions)]

	# [START constraints]
	# Each item can be in at most one bin.
	is_loaded = []
	for idx in data['all_items']:
	item_is_loaded = model.NewIntVar(0, 1, f"item {idx} is loaded somewhere")
	model.Add(item_is_loaded == sum(x[idx, b] for b in data['all_bins']))
	is_loaded.append(item_is_loaded)
	model.Add(item_loads[idx] == compute_item_load(data["weights"][idx], positions[idx])).OnlyEnforceIf(item_is_loaded)
	model.Add(item_loads[idx] == 0).OnlyEnforceIf(item_is_loaded.Not())

	# The amount packed in each bin cannot exceed its capacity.
	for b in data['all_bins']:
	# for bin capacities
	model.Add(
	sum(x[(i, b)] * data['weights'][i]
	for i in data['all_items']) <= data['bin_capacities'][b])
	# limit each bin's pseudo axle loads
	loaded_weights = []
	for i in data['all_items']:
	loaded_weight = model.NewIntVar(0, 10000, f"item {i} weight in bin {b}")
	model.Add(loaded_weight == item_loads[i]).OnlyEnforceIf(x[(i, b)])
	model.Add(loaded_weight == 0).OnlyEnforceIf(x[(i, b)].Not())
	loaded_weights.append(loaded_weight)
	model.Add(sum(loaded_weights) <= data['max_pseudoaxle_load'])

	literals = {}

	for bin_number, bin in enumerate(data['all_bins']):
	arcs = [] # accumulate the graph edges
	for item_number, item in enumerate(data['all_items']):
	# might be first, might not.
	start_lit = model.NewBoolVar(f"item {item} is first in bin {bin}")
	# item_node = bin_number * num_items + item_number + 1
	item_node = item_number + 1
	arcs.append([0, item_node, start_lit])
	end_lit = model.NewBoolVar(f"item {item} is last in bin {bin}")
	arcs.append([item_node, 0, end_lit])

	# self loop in case this item is not loaded
	skip_lit = model.NewBoolVar(f"item {item} is skipped for bin {bin}")
	arcs.append([item_node, item_node, skip_lit])

	literals[(item_number, bin_number)] = {}
	literals[(item_number, bin_number)]['start'] = start_lit
	literals[(item_number, bin_number)]['end'] = end_lit
	literals[(item_number, bin_number)]['skip'] = skip_lit

	model.Add(skip_lit == 1).OnlyEnforceIf(x[(item_number, bin_number)].Not())
	model.Add(skip_lit == 0).OnlyEnforceIf(x[(item_number, bin_number)])

	model.Add(positions[item_number] == 0).OnlyEnforceIf(start_lit)

	for next_item_number, next_item in enumerate(data['all_items']):
	if next_item_number == item_number:
	continue
	# next_item_node = bin_number * num_items + next_item_number + 1
	next_item_node = next_item_number + 1

	i_j_lit = model.NewBoolVar(f"item {next_item} follows item {item} in bin {bin}")

	literals[(item_number, bin_number)][f"next_{next_item_number}"] = i_j_lit

	arcs.append([item_node, next_item_node, i_j_lit])

	length_of_preceding_container = data['lengths'][item_number]
	model.Add(positions[next_item_number] == positions[item_number] +
	length_of_preceding_container).OnlyEnforceIf(i_j_lit)


	# create the Circuit constraint
	# print(arcs)
	model.AddCircuit(arcs)

	#bin_arcs.append(arcs)
	# [END constraints]

	# [START objective]
	# Maximize total value of packed items.
	model.Maximize(sum(value))
	# [END objective]

	# [START solver]
	solver = cp_model.CpSolver()
	# [END solver]

	solver.parameters.log_search_progress = True
	solver.parameters.max_time_in_seconds = 300
	solver.parameters.num_search_workers = 9

	# [START solve]
	status = solver.Solve(model)
	# [END solve]

	# [START print_solution]
	if status == cp_model.OPTIMAL:
	for i, l in enumerate(item_loads):
	print(f"item {i}, weight is {data['weights'][i]}, is is loaded? {solver.Value(is_loaded[i])}, load is {solver.Value(l)}")
	# for key, value in literals.items():
	# for kk, vv in value.items():
	# print(f"{key}: {kk} {vv} is {solver.Value(vv)}")
	print_solutions(data, solver, x, positions)
	else:
	print('you messed up dude')

	# [END solutions_printer]



	if __name__ == '__main__':
	main()
	# [END program]