여러 배낭 문제와 마찬가지로 bin 패킹 문제에는 항목을 bin으로 패킹하는 문제도 포함됩니다. 하지만 빈 패킹 문제에는 목표가 다릅니다. 즉, 모든 항목을 보관할 가장 적은 빈을 찾습니다.
다음은 두 문제의 차이점을 요약한 것입니다.
여러 너플 문제: 최대 용량의 포장된 아이템이 넘치도록 각 항목의 하위 집합을 고정된 수의 빈에 담습니다.
휴지통 패킹 문제: 필요한 수용 인원이 같은 빈을 가능한 한 많이 주어진다는 전제 하에 모든 상품을 보관할 최소 수의 상자를 선택합니다. 이 문제에서는 목표에 값이 포함되지 않으므로 항목에 값이 할당되지 않습니다.
다음 예시는 적재 문제를 해결하는 방법을 보여줍니다.
예
이 예시에서 다양한 가중치의 항목을 공통 용량이 있는 구간 모음에 패킹해야 합니다. 모든 항목을 담을 수 있는 빈이 충분하다고 가정하면 충분한 수의 빈을 찾는 것입니다.
다음 섹션에서는 이 문제를 해결하는 프로그램을 설명합니다. 전체 프로그램은 프로그램 완료를 참고하세요.
이 예에서는 MPSolver 래퍼를 사용합니다.
라이브러리 가져오기
아래 코드는 필요한 라이브러리를 가져옵니다.
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"
자바
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;
데이터 만들기
아래 코드는 예에 대한 데이터를 생성합니다.
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;
};
자바
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;
}
데이터에는 다음이 포함됩니다.
weights: 항목의 가중치가 포함된 벡터입니다.bin_capacity: 빈의 용량을 제공하는 단일 숫자입니다.
구간 수를 최소화하는 목적은 값을 포함하지 않으므로 항목에 할당된 값이 없습니다.
num_bins는 항목 수로 설정됩니다. 문제에 해결책이 있다면 모든 항목의 가중치가 bin 용량보다 작거나 같아야 하기 때문입니다. 이 경우 언제든지 각 항목을 별도의 구간에 배치할 수 있으므로 필요한 최대 구간이 항목 수입니다.
문제 해결사 선언
다음 코드는 솔버를 선언합니다.
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;
}
자바
// 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;
}
변수 만들기
다음 코드는 프로그램의 변수를 만듭니다.
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, "");
}
자바
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}");
}
여러 배낭의 예시에서와 같이 x[(i,
j)] 변수의 배열을 정의합니다. 이 항목의 i가 bin j에 배치되면 1, 그 외에는 0이 됩니다.
bin 패킹의 경우 변수 배열 y[j]도 정의합니다. 변수 배열은 bin j이 사용되는 경우 1(즉, 항목이 패키징된 경우)이고 다른 경우에는 0입니다. y[j]의 합계는 사용된 구간의 수입니다.
제약조건 정의
다음 코드는 문제의 제약 조건을 정의합니다.
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);
}
자바
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]);
}
}
제약조건은 다음과 같습니다.
- 각 항목을 정확히 1개의 휴지통에 넣어야 합니다. 이 제약조건은 모든 구간
j에 대한x[i][j]의 합계가 1이 되도록 설정합니다. 이는 모든 항목을 채워야 하는 것은 아니므로 합계가 1보다 작거나 같아야 하는 여러 배낭 문제와는 다릅니다. 각 구간에 포함되는 총 중량은 용량을 초과할 수 없습니다. 이는 여러 배낭 문제와 동일한 제약 조건이지만 이 경우에는 부등식의 오른쪽에 있는 용량에
y[j]를 곱합니다.y[j]을(를) 곱하는 이유는 무엇인가요? 어떤 항목이 binj에 패킹된 경우y[j]가 1이 되도록 강제하기 때문입니다.y[j]가 0이면 부등식의 오른쪽이 0이 되고 왼쪽의 가중치 가중치는 0보다 크므로 제약 조건을 위반하기 때문입니다. 이렇게 하면y[j]변수가 문제의 목표에 연결됩니다. 이제 문제 해결사가y[j]이 1인 빈 수를 최소화하려고 합니다.
목표 정의
다음 코드는 문제에 대한 목적 함수를 정의합니다.
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);
자바
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();
y[j]는 bin j가 사용되는 경우 1이고 그렇지 않은 경우 0이므로 y[j]의 합계는 사용된 bin의 수입니다. 목표는 합계를 최소화하는 것입니다.
문제 해결사 호출 및 출력
다음 코드는 솔버를 호출하고 솔루션을 출력합니다.
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;
자바
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}");
이 솔루션은 모든 아이템을 포장하는 데 필요한 용기의 최소 개수를 보여줍니다. 솔루션은 사용되는 각 용기의 포장 상자, 용기의 총 무게를 보여줍니다.
프로그램 출력
프로그램을 실행하면 다음과 같은 출력이 표시됩니다.
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
프로그램 완료
다음은 휴지통 포장 문제를 위한 전체 프로그램입니다.
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;
}
자바
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}");
}
}