Packages
fixpoint
0.19.2
0.22.2
0.22.1
0.21.5
0.21.4
0.21.3
0.21.2
0.21.1
0.21.0
0.20.6
0.20.5
0.20.4
0.20.3
0.20.2
0.20.1
0.19.5
0.19.4
0.19.3
0.19.2
0.19.1
0.18.2
0.18.1
0.17.6
0.17.5
0.17.4
0.17.3
0.17.2
0.17.1
0.16.5
0.16.4
0.16.3
0.16.2
0.16.1
0.16.0
0.15.6
0.15.5
0.15.4
0.15.3
0.15.2
0.15.1
0.15.0
0.14.9
0.14.8
0.14.7
0.14.6
0.14.5
0.14.4
0.14.3
0.14.2
0.14.1
0.13.5
0.13.4
0.13.2
0.13.1
0.12.9
0.12.8
0.12.7
0.12.6
0.12.5
0.12.4
0.12.2
0.12.1
0.11.8
0.11.7
0.11.6
0.11.5
0.11.4
0.11.3
0.11.2
0.11.1
0.10.7
0.10.6
0.10.5
0.10.4
0.10.3
0.10.2
0.10.1
0.9.12
0.9.11
0.9.10
0.9.9
0.9.8
0.9.7
0.9.6
0.9.5
0.9.4
0.9.3
0.9.2
0.9.1
0.9.0
0.8.52
0.8.51
0.8.50
0.8.49
0.8.48
0.8.46
0.8.44
0.8.43
0.8.42
0.8.41
0.8.40
0.8.39
0.8.38
0.8.37
0.8.36
0.8.35
0.8.34
0.8.33
0.8.32
0.8.31
0.8.30
0.8.29
0.8.28
0.8.27
0.8.26
0.8.25
0.8.24
0.8.23
0.8.22
0.8.21
0.8.20
0.8.19
0.8.18
0.8.17
0.8.16
0.8.15
0.8.14
0.8.13
0.8.12
0.8.11
0.8.10
0.8.9
0.8.8
0.8.7
0.8.6
0.8.5
0.8.4
0.8.3
0.8.2
0.8.1
0.8.0
0.7.10
0.7.9
0.7.8
0.7.7
0.7.6
0.7.5
0.7.4
0.7.3
0.7.2
0.7.1
0.7.0
0.6.5
0.6.4
0.6.3
0.6.2
0.6.1
0.6.0
0.5.12
0.5.11
0.5.10
0.5.9
0.5.8
0.5.7
0.5.6
0.5.5
0.5.4
0.5.3
0.5.2
0.5.1
0.5.0
0.4.3
0.4.2
0.4.1
0.4.0
0.3.6
0.3.5
0.3.4
0.3.3
0.3.2
0.3.1
0.3.0
0.2.3
0.2.2
0.2.1
0.1.3
0.1.2
0.1.1
0.1.0
Constraint Programming Solver
Current section
Files
Jump to
Current section
Files
data/bin_packing/bin_packing/bin_packing.py
import hexaly.optimizer
import sys
import math
if len(sys.argv) < 2:
print("Usage: python bin_packing.py inputFile [outputFile] [timeLimit]")
sys.exit(1)
def read_integers(filename):
with open(filename) as f:
return [int(elem) for elem in f.read().split()]
with hexaly.optimizer.HexalyOptimizer() as optimizer:
# Read instance data
file_it = iter(read_integers(sys.argv[1]))
nb_items = int(next(file_it))
bin_capacity = int(next(file_it))
weights_data = [int(next(file_it)) for i in range(nb_items)]
nb_min_bins = int(math.ceil(sum(weights_data) / float(bin_capacity)))
nb_max_bins = min(nb_items, 2 * nb_min_bins)
#
# Declare the optimization model
#
model = optimizer.model
# Set decisions: bins[k] represents the items in bin k
bins = [model.set(nb_items) for _ in range(nb_max_bins)]
# Each item must be in one bin and one bin only
model.constraint(model.partition(bins))
# Create an array and a function to retrieve the item's weight
weights = model.array(weights_data)
weight_lambda = model.lambda_function(lambda i: weights[i])
# Weight constraint for each bin
bin_weights = [model.sum(b, weight_lambda) for b in bins]
for w in bin_weights:
model.constraint(w <= bin_capacity)
# Bin k is used if at least one item is in it
bins_used = [model.count(b) > 0 for b in bins]
# Count the used bins
total_bins_used = model.sum(bins_used)
# Minimize the number of used bins
model.minimize(total_bins_used)
model.close()
# Parameterize the optimizer
if len(sys.argv) >= 4:
optimizer.param.time_limit = int(sys.argv[3])
else:
optimizer.param.time_limit = 5
# Stop the search if the lower threshold is reached
optimizer.param.set_objective_threshold(0, nb_min_bins)
optimizer.solve()
# Write the solution in a file
if len(sys.argv) >= 3:
with open(sys.argv[2], 'w') as f:
for k in range(nb_max_bins):
if bins_used[k].value:
f.write("Bin weight: %d | Items: " % bin_weights[k].value)
for e in bins[k].value:
f.write("%d " % e)
f.write("\n")