Come nel caso di più zaini, anche in imballaggio dei rifiuti è necessario imballare gli articoli in bin. Tuttavia, il problema di bin packing ha un obiettivo diverso: trova il numero minore di bin che conterrà tutti gli elementi.
Di seguito sono riepilogate le differenze tra i due problemi:
Problema relativo a più zaini: raggruppa un sottoinsieme di elementi in un numero fisso di bin, con capacità diverse, in modo che il valore totale degli elementi pacchettizzati sia un massimo.
Problema di imballaggio dei binari: poiché sono necessari tutti i bin con una capacità comune, trova il numero inferiore di elementi che conterrà tutti gli elementi. In questo problema, agli elementi non vengono assegnati valori, perché l'obiettivo non riguarda il valore.
L'esempio seguente mostra come risolvere un problema di imballaggio del cestino.
Esempio
In questo esempio, gli articoli di diverse ponderazioni devono essere imballati in un insieme di bin con una capacità comune. Supponendo che ci siano abbastanza contenitori per contenere tutti gli elementi, il problema è trovarne pochino sufficienti.
Le seguenti sezioni presentano programmi che risolvono questo problema. Per i programmi completi, consulta la sezione Programmi completi.
In questo esempio viene utilizzato il wrapper MPSolver.
Importa le librerie
Il codice seguente importa le librerie necessarie.
Python
from ortools.linear_solver import pywraplp
C++
#include <iostream> #include <memory> #include <numeric> #include <ostream> #include <vector> #include "ortools/linear_solver/linear_expr.h" #include "ortools/linear_solver/linear_solver.h"
Java
import com.google.ortools.Loader; import com.google.ortools.linearsolver.MPConstraint; import com.google.ortools.linearsolver.MPObjective; import com.google.ortools.linearsolver.MPSolver; import com.google.ortools.linearsolver.MPVariable;
C#
using System; using Google.OrTools.LinearSolver;
Creare i dati
Il codice seguente crea i dati per l'esempio.
Python
def create_data_model():
"""Create the data for the example."""
data = {}
weights = [48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30]
data["weights"] = weights
data["items"] = list(range(len(weights)))
data["bins"] = data["items"]
data["bin_capacity"] = 100
return data
C++
struct DataModel {
const std::vector<double> weights = {48, 30, 19, 36, 36, 27,
42, 42, 36, 24, 30};
const int num_items = weights.size();
const int num_bins = weights.size();
const int bin_capacity = 100;
};
Java
static class DataModel {
public final double[] weights = {48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30};
public final int numItems = weights.length;
public final int numBins = weights.length;
public final int binCapacity = 100;
}
C#
class DataModel
{
public static double[] Weights = { 48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30 };
public int NumItems = Weights.Length;
public int NumBins = Weights.Length;
public double BinCapacity = 100.0;
}
tra cui:
weights: un vettore che contiene le ponderazioni degli elementi.bin_capacity: un unico numero che indica la capacità dei contenitori.
Non vengono assegnati valori agli elementi perché l'obiettivo di ridurre al minimo il numero di bin non comporta alcun valore.
Tieni presente che num_bins è impostato sul numero di elementi. Questo perché, se il problema ha una soluzione, la ponderazione di ogni elemento deve essere inferiore o uguale alla capacità del cestino. In questo caso, il numero massimo di bin di cui potresti avere bisogno è
il numero di elementi, perché potresti sempre inserire ogni elemento in un riquadro separato.
Dichiara il risolutore
Il codice seguente dichiara il risolutore.
Python
# Create the mip solver with the SCIP backend.
solver = pywraplp.Solver.CreateSolver("SCIP")
if not solver:
return
C++
// Create the mip solver with the SCIP backend.
std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("SCIP"));
if (!solver) {
LOG(WARNING) << "SCIP solver unavailable.";
return;
}
Java
// Create the linear solver with the SCIP backend.
MPSolver solver = MPSolver.createSolver("SCIP");
if (solver == null) {
System.out.println("Could not create solver SCIP");
return;
}
C#
// Create the linear solver with the SCIP backend.
Solver solver = Solver.CreateSolver("SCIP");
if (solver is null)
{
return;
}
Creare le variabili
Il codice seguente crea le variabili per il programma.
Python
# 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)] = solver.IntVar(0, 1, "x_%i_%i" % (i, j))
# y[j] = 1 if bin j is used.
y = {}
for j in data["bins"]:
y[j] = solver.IntVar(0, 1, "y[%i]" % j)
C++
std::vector<std::vector<const MPVariable*>> x(
data.num_items, std::vector<const MPVariable*>(data.num_bins));
for (int i = 0; i < data.num_items; ++i) {
for (int j = 0; j < data.num_bins; ++j) {
x[i][j] = solver->MakeIntVar(0.0, 1.0, "");
}
}
// y[j] = 1 if bin j is used.
std::vector<const MPVariable*> y(data.num_bins);
for (int j = 0; j < data.num_bins; ++j) {
y[j] = solver->MakeIntVar(0.0, 1.0, "");
}
Java
MPVariable[][] x = new MPVariable[data.numItems][data.numBins];
for (int i = 0; i < data.numItems; ++i) {
for (int j = 0; j < data.numBins; ++j) {
x[i][j] = solver.makeIntVar(0, 1, "");
}
}
MPVariable[] y = new MPVariable[data.numBins];
for (int j = 0; j < data.numBins; ++j) {
y[j] = solver.makeIntVar(0, 1, "");
}
C#
Variable[,] x = new Variable[data.NumItems, data.NumBins];
for (int i = 0; i < data.NumItems; i++)
{
for (int j = 0; j < data.NumBins; j++)
{
x[i, j] = solver.MakeIntVar(0, 1, $"x_{i}_{j}");
}
}
Variable[] y = new Variable[data.NumBins];
for (int j = 0; j < data.NumBins; j++)
{
y[j] = solver.MakeIntVar(0, 1, $"y_{j}");
}
Come nell'esempio dei zaini multipli, definisci una matrice di variabili x[(i,
j)], il cui valore è 1 se l'elemento i è posizionato nel cestino j, altrimenti è 0.
Per il bin packing, definisci anche un array di variabili, y[j], il cui valore è 1
se viene utilizzato bin j, ovvero se contiene elementi, e 0
altrimenti. La somma di y[j] sarà il numero dei bin utilizzati.
Definisci i vincoli
Il seguente codice definisce i vincoli per il problema:
Python
# Constraints
# Each item must be in exactly one bin.
for i in data["items"]:
solver.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"]:
solver.Add(
sum(x[(i, j)] * data["weights"][i] for i in data["items"])
<= y[j] * data["bin_capacity"]
)
C++
// Create the constraints.
// Each item is in exactly one bin.
for (int i = 0; i < data.num_items; ++i) {
LinearExpr sum;
for (int j = 0; j < data.num_bins; ++j) {
sum += x[i][j];
}
solver->MakeRowConstraint(sum == 1.0);
}
// For each bin that is used, the total packed weight can be at most
// the bin capacity.
for (int j = 0; j < data.num_bins; ++j) {
LinearExpr weight;
for (int i = 0; i < data.num_items; ++i) {
weight += data.weights[i] * LinearExpr(x[i][j]);
}
solver->MakeRowConstraint(weight <= LinearExpr(y[j]) * data.bin_capacity);
}
Java
double infinity = java.lang.Double.POSITIVE_INFINITY;
for (int i = 0; i < data.numItems; ++i) {
MPConstraint constraint = solver.makeConstraint(1, 1, "");
for (int j = 0; j < data.numBins; ++j) {
constraint.setCoefficient(x[i][j], 1);
}
}
// The bin capacity contraint for bin j is
// sum_i w_i x_ij <= C*y_j
// To define this constraint, first subtract the left side from the right to get
// 0 <= C*y_j - sum_i w_i x_ij
//
// Note: Since sum_i w_i x_ij is positive (and y_j is 0 or 1), the right side must
// be less than or equal to C. But it's not necessary to add this constraint
// because it is forced by the other constraints.
for (int j = 0; j < data.numBins; ++j) {
MPConstraint constraint = solver.makeConstraint(0, infinity, "");
constraint.setCoefficient(y[j], data.binCapacity);
for (int i = 0; i < data.numItems; ++i) {
constraint.setCoefficient(x[i][j], -data.weights[i]);
}
}
C#
for (int i = 0; i < data.NumItems; ++i)
{
Constraint constraint = solver.MakeConstraint(1, 1, "");
for (int j = 0; j < data.NumBins; ++j)
{
constraint.SetCoefficient(x[i, j], 1);
}
}
for (int j = 0; j < data.NumBins; ++j)
{
Constraint constraint = solver.MakeConstraint(0, Double.PositiveInfinity, "");
constraint.SetCoefficient(y[j], data.BinCapacity);
for (int i = 0; i < data.NumItems; ++i)
{
constraint.SetCoefficient(x[i, j], -DataModel.Weights[i]);
}
}
I vincoli sono i seguenti:
- Ogni elemento deve essere posizionato esattamente in un contenitore. Questo vincolo è impostato richiedendo che la somma di
x[i][j]in tutti i binjsia uguale a 1. Tale problema è diverso da quello relativo agli zaini multipli, in cui la somma deve essere inferiore o uguale a 1, perché non tutti gli elementi devono essere pacchettizzati. Il peso totale imballato in ogni contenitore non può superare la sua capacità. Questo è lo stesso vincolo del problema relativo a più zaini, ma in questo caso moltiplichi la capacità del cestino sul lato destro delle disuguaglianze per
y[j].Perché moltiplicare per
y[j]? Perchéy[j]è uguale a 1 se un articolo è imballato nel cestinoj. Ciò avviene perché, sey[j]fosse 0, il lato destro della disuguaglianza sarebbe 0, mentre il peso del cestino sul lato sinistro sarebbe maggiore di 0, violando il vincolo. Questa operazione collega le variabiliy[j]all'obiettivo del problema, poiché per ora il risolutore cercherà di ridurre al minimo il numero di bin per cuiy[j]è 1.
Definisci l'obiettivo
Il seguente codice definisce la funzione oggettiva del problema.
Python
# Objective: minimize the number of bins used. solver.Minimize(solver.Sum([y[j] for j in data["bins"]]))
C++
// Create the objective function.
MPObjective* const objective = solver->MutableObjective();
LinearExpr num_bins_used;
for (int j = 0; j < data.num_bins; ++j) {
num_bins_used += y[j];
}
objective->MinimizeLinearExpr(num_bins_used);
Java
MPObjective objective = solver.objective();
for (int j = 0; j < data.numBins; ++j) {
objective.setCoefficient(y[j], 1);
}
objective.setMinimization();
C#
Objective objective = solver.Objective();
for (int j = 0; j < data.NumBins; ++j)
{
objective.SetCoefficient(y[j], 1);
}
objective.SetMinimization();
Poiché y[j] è 1 se viene utilizzato bin j, altrimenti 0, la somma di y[j] è
il numero di bin utilizzati. L'obiettivo è ridurre al minimo la somma.
Chiama il risolutore e stampa la soluzione
Il codice seguente chiama il risolutore e stampa la soluzione.
Python
print(f"Solving with {solver.SolverVersion()}")
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
num_bins = 0
for j in data["bins"]:
if y[j].solution_value() == 1:
bin_items = []
bin_weight = 0
for i in data["items"]:
if x[i, j].solution_value() > 0:
bin_items.append(i)
bin_weight += data["weights"][i]
if bin_items:
num_bins += 1
print("Bin number", j)
print(" Items packed:", bin_items)
print(" Total weight:", bin_weight)
print()
print()
print("Number of bins used:", num_bins)
print("Time = ", solver.WallTime(), " milliseconds")
else:
print("The problem does not have an optimal solution.")
C++
const MPSolver::ResultStatus result_status = solver->Solve();
// Check that the problem has an optimal solution.
if (result_status != MPSolver::OPTIMAL) {
std::cerr << "The problem does not have an optimal solution!";
return;
}
std::cout << "Number of bins used: " << objective->Value() << std::endl
<< std::endl;
double total_weight = 0;
for (int j = 0; j < data.num_bins; ++j) {
if (y[j]->solution_value() == 1) {
std::cout << "Bin " << j << std::endl << std::endl;
double bin_weight = 0;
for (int i = 0; i < data.num_items; ++i) {
if (x[i][j]->solution_value() == 1) {
std::cout << "Item " << i << " - Weight: " << data.weights[i]
<< std::endl;
bin_weight += data.weights[i];
}
}
std::cout << "Packed bin weight: " << bin_weight << std::endl
<< std::endl;
total_weight += bin_weight;
}
}
std::cout << "Total packed weight: " << total_weight << std::endl;
Java
final MPSolver.ResultStatus resultStatus = solver.solve();
// Check that the problem has an optimal solution.
if (resultStatus == MPSolver.ResultStatus.OPTIMAL) {
System.out.println("Number of bins used: " + objective.value());
double totalWeight = 0;
for (int j = 0; j < data.numBins; ++j) {
if (y[j].solutionValue() == 1) {
System.out.println("\nBin " + j + "\n");
double binWeight = 0;
for (int i = 0; i < data.numItems; ++i) {
if (x[i][j].solutionValue() == 1) {
System.out.println("Item " + i + " - weight: " + data.weights[i]);
binWeight += data.weights[i];
}
}
System.out.println("Packed bin weight: " + binWeight);
totalWeight += binWeight;
}
}
System.out.println("\nTotal packed weight: " + totalWeight);
} else {
System.err.println("The problem does not have an optimal solution.");
}
C#
Solver.ResultStatus resultStatus = solver.Solve();
// Check that the problem has an optimal solution.
if (resultStatus != Solver.ResultStatus.OPTIMAL)
{
Console.WriteLine("The problem does not have an optimal solution!");
return;
}
Console.WriteLine($"Number of bins used: {solver.Objective().Value()}");
double TotalWeight = 0.0;
for (int j = 0; j < data.NumBins; ++j)
{
double BinWeight = 0.0;
if (y[j].SolutionValue() == 1)
{
Console.WriteLine($"Bin {j}");
for (int i = 0; i < data.NumItems; ++i)
{
if (x[i, j].SolutionValue() == 1)
{
Console.WriteLine($"Item {i} weight: {DataModel.Weights[i]}");
BinWeight += DataModel.Weights[i];
}
}
Console.WriteLine($"Packed bin weight: {BinWeight}");
TotalWeight += BinWeight;
}
}
Console.WriteLine($"Total packed weight: {TotalWeight}");
La soluzione mostra il numero minimo di bin necessari per imballare tutti gli articoli. Per ogni contenitore utilizzato, la soluzione mostra gli articoli contenuti e il peso totale del contenitore.
Output del programma
Quando esegui il programma, viene visualizzato il seguente output.
Bin number 0 Items packed: [1, 5, 10] Total weight: 87 Bin number 1 Items packed: [0, 6] Total weight: 90 Bin number 2 Items packed: [2, 4, 7] Total weight: 97 Bin number 3 Items packed: [3, 8, 9] Total weight: 96 Number of bins used: 4.0
Completare i programmi
Di seguito sono riportati i programmi completi per il problema di imballaggio del cestino.
Python
from ortools.linear_solver import pywraplp
def create_data_model():
"""Create the data for the example."""
data = {}
weights = [48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30]
data["weights"] = weights
data["items"] = list(range(len(weights)))
data["bins"] = data["items"]
data["bin_capacity"] = 100
return data
def main():
data = create_data_model()
# Create the mip solver with the SCIP backend.
solver = pywraplp.Solver.CreateSolver("SCIP")
if not solver:
return
# 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)] = solver.IntVar(0, 1, "x_%i_%i" % (i, j))
# y[j] = 1 if bin j is used.
y = {}
for j in data["bins"]:
y[j] = solver.IntVar(0, 1, "y[%i]" % j)
# Constraints
# Each item must be in exactly one bin.
for i in data["items"]:
solver.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"]:
solver.Add(
sum(x[(i, j)] * data["weights"][i] for i in data["items"])
<= y[j] * data["bin_capacity"]
)
# Objective: minimize the number of bins used.
solver.Minimize(solver.Sum([y[j] for j in data["bins"]]))
print(f"Solving with {solver.SolverVersion()}")
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
num_bins = 0
for j in data["bins"]:
if y[j].solution_value() == 1:
bin_items = []
bin_weight = 0
for i in data["items"]:
if x[i, j].solution_value() > 0:
bin_items.append(i)
bin_weight += data["weights"][i]
if bin_items:
num_bins += 1
print("Bin number", j)
print(" Items packed:", bin_items)
print(" Total weight:", bin_weight)
print()
print()
print("Number of bins used:", num_bins)
print("Time = ", solver.WallTime(), " milliseconds")
else:
print("The problem does not have an optimal solution.")
if __name__ == "__main__":
main()
C++
#include <iostream>
#include <memory>
#include <numeric>
#include <ostream>
#include <vector>
#include "ortools/linear_solver/linear_expr.h"
#include "ortools/linear_solver/linear_solver.h"
namespace operations_research {
struct DataModel {
const std::vector<double> weights = {48, 30, 19, 36, 36, 27,
42, 42, 36, 24, 30};
const int num_items = weights.size();
const int num_bins = weights.size();
const int bin_capacity = 100;
};
void BinPackingMip() {
DataModel data;
// Create the mip solver with the SCIP backend.
std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("SCIP"));
if (!solver) {
LOG(WARNING) << "SCIP solver unavailable.";
return;
}
std::vector<std::vector<const MPVariable*>> x(
data.num_items, std::vector<const MPVariable*>(data.num_bins));
for (int i = 0; i < data.num_items; ++i) {
for (int j = 0; j < data.num_bins; ++j) {
x[i][j] = solver->MakeIntVar(0.0, 1.0, "");
}
}
// y[j] = 1 if bin j is used.
std::vector<const MPVariable*> y(data.num_bins);
for (int j = 0; j < data.num_bins; ++j) {
y[j] = solver->MakeIntVar(0.0, 1.0, "");
}
// Create the constraints.
// Each item is in exactly one bin.
for (int i = 0; i < data.num_items; ++i) {
LinearExpr sum;
for (int j = 0; j < data.num_bins; ++j) {
sum += x[i][j];
}
solver->MakeRowConstraint(sum == 1.0);
}
// For each bin that is used, the total packed weight can be at most
// the bin capacity.
for (int j = 0; j < data.num_bins; ++j) {
LinearExpr weight;
for (int i = 0; i < data.num_items; ++i) {
weight += data.weights[i] * LinearExpr(x[i][j]);
}
solver->MakeRowConstraint(weight <= LinearExpr(y[j]) * data.bin_capacity);
}
// Create the objective function.
MPObjective* const objective = solver->MutableObjective();
LinearExpr num_bins_used;
for (int j = 0; j < data.num_bins; ++j) {
num_bins_used += y[j];
}
objective->MinimizeLinearExpr(num_bins_used);
const MPSolver::ResultStatus result_status = solver->Solve();
// Check that the problem has an optimal solution.
if (result_status != MPSolver::OPTIMAL) {
std::cerr << "The problem does not have an optimal solution!";
return;
}
std::cout << "Number of bins used: " << objective->Value() << std::endl
<< std::endl;
double total_weight = 0;
for (int j = 0; j < data.num_bins; ++j) {
if (y[j]->solution_value() == 1) {
std::cout << "Bin " << j << std::endl << std::endl;
double bin_weight = 0;
for (int i = 0; i < data.num_items; ++i) {
if (x[i][j]->solution_value() == 1) {
std::cout << "Item " << i << " - Weight: " << data.weights[i]
<< std::endl;
bin_weight += data.weights[i];
}
}
std::cout << "Packed bin weight: " << bin_weight << std::endl
<< std::endl;
total_weight += bin_weight;
}
}
std::cout << "Total packed weight: " << total_weight << std::endl;
}
} // namespace operations_research
int main(int argc, char** argv) {
operations_research::BinPackingMip();
return EXIT_SUCCESS;
}
Java
package com.google.ortools.linearsolver.samples;
import com.google.ortools.Loader;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;
/** Bin packing problem. */
public class BinPackingMip {
static class DataModel {
public final double[] weights = {48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30};
public final int numItems = weights.length;
public final int numBins = weights.length;
public final int binCapacity = 100;
}
public static void main(String[] args) throws Exception {
Loader.loadNativeLibraries();
final DataModel data = new DataModel();
// Create the linear solver with the SCIP backend.
MPSolver solver = MPSolver.createSolver("SCIP");
if (solver == null) {
System.out.println("Could not create solver SCIP");
return;
}
MPVariable[][] x = new MPVariable[data.numItems][data.numBins];
for (int i = 0; i < data.numItems; ++i) {
for (int j = 0; j < data.numBins; ++j) {
x[i][j] = solver.makeIntVar(0, 1, "");
}
}
MPVariable[] y = new MPVariable[data.numBins];
for (int j = 0; j < data.numBins; ++j) {
y[j] = solver.makeIntVar(0, 1, "");
}
double infinity = java.lang.Double.POSITIVE_INFINITY;
for (int i = 0; i < data.numItems; ++i) {
MPConstraint constraint = solver.makeConstraint(1, 1, "");
for (int j = 0; j < data.numBins; ++j) {
constraint.setCoefficient(x[i][j], 1);
}
}
// The bin capacity contraint for bin j is
// sum_i w_i x_ij <= C*y_j
// To define this constraint, first subtract the left side from the right to get
// 0 <= C*y_j - sum_i w_i x_ij
//
// Note: Since sum_i w_i x_ij is positive (and y_j is 0 or 1), the right side must
// be less than or equal to C. But it's not necessary to add this constraint
// because it is forced by the other constraints.
for (int j = 0; j < data.numBins; ++j) {
MPConstraint constraint = solver.makeConstraint(0, infinity, "");
constraint.setCoefficient(y[j], data.binCapacity);
for (int i = 0; i < data.numItems; ++i) {
constraint.setCoefficient(x[i][j], -data.weights[i]);
}
}
MPObjective objective = solver.objective();
for (int j = 0; j < data.numBins; ++j) {
objective.setCoefficient(y[j], 1);
}
objective.setMinimization();
final MPSolver.ResultStatus resultStatus = solver.solve();
// Check that the problem has an optimal solution.
if (resultStatus == MPSolver.ResultStatus.OPTIMAL) {
System.out.println("Number of bins used: " + objective.value());
double totalWeight = 0;
for (int j = 0; j < data.numBins; ++j) {
if (y[j].solutionValue() == 1) {
System.out.println("\nBin " + j + "\n");
double binWeight = 0;
for (int i = 0; i < data.numItems; ++i) {
if (x[i][j].solutionValue() == 1) {
System.out.println("Item " + i + " - weight: " + data.weights[i]);
binWeight += data.weights[i];
}
}
System.out.println("Packed bin weight: " + binWeight);
totalWeight += binWeight;
}
}
System.out.println("\nTotal packed weight: " + totalWeight);
} else {
System.err.println("The problem does not have an optimal solution.");
}
}
private BinPackingMip() {}
}
C#
using System;
using Google.OrTools.LinearSolver;
public class BinPackingMip
{
class DataModel
{
public static double[] Weights = { 48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30 };
public int NumItems = Weights.Length;
public int NumBins = Weights.Length;
public double BinCapacity = 100.0;
}
public static void Main()
{
DataModel data = new DataModel();
// Create the linear solver with the SCIP backend.
Solver solver = Solver.CreateSolver("SCIP");
if (solver is null)
{
return;
}
Variable[,] x = new Variable[data.NumItems, data.NumBins];
for (int i = 0; i < data.NumItems; i++)
{
for (int j = 0; j < data.NumBins; j++)
{
x[i, j] = solver.MakeIntVar(0, 1, $"x_{i}_{j}");
}
}
Variable[] y = new Variable[data.NumBins];
for (int j = 0; j < data.NumBins; j++)
{
y[j] = solver.MakeIntVar(0, 1, $"y_{j}");
}
for (int i = 0; i < data.NumItems; ++i)
{
Constraint constraint = solver.MakeConstraint(1, 1, "");
for (int j = 0; j < data.NumBins; ++j)
{
constraint.SetCoefficient(x[i, j], 1);
}
}
for (int j = 0; j < data.NumBins; ++j)
{
Constraint constraint = solver.MakeConstraint(0, Double.PositiveInfinity, "");
constraint.SetCoefficient(y[j], data.BinCapacity);
for (int i = 0; i < data.NumItems; ++i)
{
constraint.SetCoefficient(x[i, j], -DataModel.Weights[i]);
}
}
Objective objective = solver.Objective();
for (int j = 0; j < data.NumBins; ++j)
{
objective.SetCoefficient(y[j], 1);
}
objective.SetMinimization();
Solver.ResultStatus resultStatus = solver.Solve();
// Check that the problem has an optimal solution.
if (resultStatus != Solver.ResultStatus.OPTIMAL)
{
Console.WriteLine("The problem does not have an optimal solution!");
return;
}
Console.WriteLine($"Number of bins used: {solver.Objective().Value()}");
double TotalWeight = 0.0;
for (int j = 0; j < data.NumBins; ++j)
{
double BinWeight = 0.0;
if (y[j].SolutionValue() == 1)
{
Console.WriteLine($"Bin {j}");
for (int i = 0; i < data.NumItems; ++i)
{
if (x[i, j].SolutionValue() == 1)
{
Console.WriteLine($"Item {i} weight: {DataModel.Weights[i]}");
BinWeight += DataModel.Weights[i];
}
}
Console.WriteLine($"Packed bin weight: {BinWeight}");
TotalWeight += BinWeight;
}
}
Console.WriteLine($"Total packed weight: {TotalWeight}");
}
}