Al igual que el problema de la mochila, el problema de empaquetado de discretizaciones también implica empaquetar elementos en discretizaciones. Sin embargo, el problema de la compresión tiene un objetivo diferente: encontrar la menor cantidad de contenedores que contendrán todos los elementos.
A continuación, se resumen las diferencias entre ambos problemas:
Problema con la mochila: empaqueta un subconjunto de los elementos en una cantidad fija de discretizaciones, con capacidades de variación variables, de modo que el valor total de los elementos empaquetados sea el máximo.
Problema de empaque: dado que hay tantos contenedores con una capacidad común como sea necesario, encuentra la menor que pueda contener todos los elementos. En este problema, los elementos no tienen valores asignados, ya que el objetivo no implica valor.
En el siguiente ejemplo, se muestra cómo resolver un problema de empaquetado en contenedores.
Ejemplo
En este ejemplo, los elementos de varios pesos deben empaquetarse en un conjunto de discretizaciones con una capacidad común. Si suponemos que hay suficientes discretizaciones para contener todos los elementos, el problema es encontrar el menor número suficiente.
En las siguientes secciones, se presentan los programas para resolver este problema. Para ver los programas completos, consulta Programas completos.
En este ejemplo, se usa el wrapper de MPSolver.
Importa las bibliotecas
El siguiente código importa las bibliotecas requeridas.
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;
Crea los datos
El siguiente código crea los datos para el ejemplo.
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;
}
Los datos incluyen lo siguiente:
weights: Un vector que contiene los pesos de los elementos.bin_capacity: Es un solo número que indica la capacidad de los contenedores.
No hay valores asignados a los elementos porque el objetivo de minimizar la cantidad de discretizaciones no implica el valor.
Ten en cuenta que num_bins se estableció en la cantidad de elementos. Esto se debe a que, si el problema tiene una solución, el peso de cada elemento debe ser menor o igual que la capacidad de la discretización. En ese caso, la cantidad máxima de discretizaciones que podrías necesitar es la cantidad de elementos, ya que siempre puedes poner cada elemento en una discretización separada.
Cómo declarar el solucionador
El siguiente código declara el solucionador.
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;
}
Crea las variables
El siguiente código crea las variables para el programa.
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}");
}
Al igual que en el ejemplo de la mochila múltiples, debes definir un arreglo de variables x[(i,
j)], cuyo valor es 1 si el elemento i está ubicado en la papelera j, y 0 en caso contrario.
Para el empaquetado de discretización, también defines un arreglo de variables, y[j], cuyo valor es 1 si se usa la discretización j, es decir, si algún elemento está empaquetado, o 0 si se usa en caso contrario. La suma de y[j] será la cantidad de discretizaciones usadas.
Define las restricciones
El siguiente código define las restricciones del 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]);
}
}
Las restricciones son las siguientes:
- Cada artículo se debe colocar en exactamente un contenedor. Para esta restricción, se requiere que la suma de
x[i][j]en todas las discretizacionesjsea igual a 1. Ten en cuenta que esto difiere del problema de la mochila, en el que solo se requiere que la suma sea menor o igual que 1, ya que no todos los elementos deben empaquetarse. El peso total empaquetado en cada discretización no puede superar su capacidad. Esta es la misma restricción que la del problema de la mochila, pero en este caso se multiplica la capacidad de la discretización del lado derecho de las desigualdades por
y[j].¿Por qué multiplicar por
y[j]? Debido a que fuerza ay[j]a igual a 1 si algún elemento está empaquetado en la papeleraj. Esto se debe a que, siy[j]es 0, el lado derecho de la desigualdad sería 0, mientras que el peso de la papelera en el lado izquierdo sería mayor que 0, lo que infringe la restricción. Esto conecta las variablesy[j]al objetivo del problema. Por ahora, el solucionador intentará minimizar la cantidad de discretizaciones para las quey[j]es 1.
Define el objetivo
El siguiente código define la función objetiva 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();
Dado que y[j] es 1 si se usa la discretización j, y 0 de lo contrario, la suma de y[j] es la cantidad de discretizaciones usadas. El objetivo es minimizar la suma.
Llama al agente de resolución e imprime la solución
El siguiente código llama al solucionador e imprime la solución.
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 solución muestra la cantidad mínima de discretizaciones necesarias para empaquetar todos los elementos. Para cada discretización que se use, la solución muestra los elementos empaquetados y el peso total de la discretización.
Resultado del programa
Cuando ejecutes el programa, se mostrará el siguiente resultado.
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
Programas completos
A continuación, se muestran los programas completos para solucionar el problema.
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}");
}
}