أظهر القسم السابق كيفية حل MIP باستخدام عدد قليل فقط من المتغيرات والقيود، والتي يتم تعريفها بشكل فردي. بالنسبة للمشكلات الأكبر، من الأنسب تحديد المتغيرات والقيود عن طريق التكرار فوق الصفائف. يوضح المثال التالي ذلك.
مثال
في هذا المثال، سنحل المشكلة التالية.
زيادة العرض إلى أقصى حد 7x1 + 8x2 + 2x3 + 9x4 + 6x5 مع مراعاة القيود التالية:
- 5 x1 + 7 x2 + 9 x3 + 2 x4 + 1 x5 ≤ 250
- 18 x1 + 4 x2 - 9 x3 + 10 x4 + 12 x5 ≤ 285
- 4 x1 + 7 x2 + 3 x3 + 8 x4 + 5 x5 ≤ 211
- 5 x1 + 13 x2 + 16 x3 + 3 x4 - 7 x5 ≤ 315
حيث تكون x1 وx2 و... وx5 أعدادًا صحيحة غير سالبة.
تعرض الأقسام التالية البرامج التي تحل هذه المشكلة. تستخدم البرامج نفس الطرق المستخدمة في مثال MIP السابق، ولكن في هذه الحالة تُطبقها على قيم الصفيف في حلقة تكرارية.
تعريف أداة الحلّ
في أي من برامج MIP، تبدأ باستيراد برنامج تضمين أداة الحلّ الخطي والإعلان عن أداة حلّ MIP، كما هو موضّح في مثال MIP السابق.
إنشاء البيانات
تنشئ التعليمة البرمجية التالية صفائف تحتوي على البيانات للمثال: معاملات المتغير للقيود والدالة الموضوعية، وحدود القيود.
Python
def create_data_model():
"""Stores the data for the problem."""
data = {}
data["constraint_coeffs"] = [
[5, 7, 9, 2, 1],
[18, 4, -9, 10, 12],
[4, 7, 3, 8, 5],
[5, 13, 16, 3, -7],
]
data["bounds"] = [250, 285, 211, 315]
data["obj_coeffs"] = [7, 8, 2, 9, 6]
data["num_vars"] = 5
data["num_constraints"] = 4
return data
C++
struct DataModel {
const std::vector<std::vector<double>> constraint_coeffs{
{5, 7, 9, 2, 1},
{18, 4, -9, 10, 12},
{4, 7, 3, 8, 5},
{5, 13, 16, 3, -7},
};
const std::vector<double> bounds{250, 285, 211, 315};
const std::vector<double> obj_coeffs{7, 8, 2, 9, 6};
const int num_vars = 5;
const int num_constraints = 4;
};
Java
static class DataModel {
public final double[][] constraintCoeffs = {
{5, 7, 9, 2, 1},
{18, 4, -9, 10, 12},
{4, 7, 3, 8, 5},
{5, 13, 16, 3, -7},
};
public final double[] bounds = {250, 285, 211, 315};
public final double[] objCoeffs = {7, 8, 2, 9, 6};
public final int numVars = 5;
public final int numConstraints = 4;
}
C#
class DataModel
{
public double[,] ConstraintCoeffs = {
{ 5, 7, 9, 2, 1 },
{ 18, 4, -9, 10, 12 },
{ 4, 7, 3, 8, 5 },
{ 5, 13, 16, 3, -7 },
};
public double[] Bounds = { 250, 285, 211, 315 };
public double[] ObjCoeffs = { 7, 8, 2, 9, 6 };
public int NumVars = 5;
public int NumConstraints = 4;
}
إنشاء مثيل للبيانات
ينشئ الكود التالي مثيلاً لنموذج البيانات.
Python
data = create_data_model()
C++
DataModel data;
Java
final DataModel data = new DataModel();
C#
DataModel data = new DataModel();
إنشاء مثيل للأداة
يُنشئ الرمز التالي مثيلاً للأداة.
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;
}
تحديد المتغيّرات
تحدد التعليمة البرمجية التالية المتغيرات للمثال في حلقة تكرار. بالنسبة إلى المسائل الكبيرة، يكون ذلك أسهل من تحديد المتغيّرات بشكل فردي، كما في المثال السابق.
Python
infinity = solver.infinity()
x = {}
for j in range(data["num_vars"]):
x[j] = solver.IntVar(0, infinity, "x[%i]" % j)
print("Number of variables =", solver.NumVariables())
C++
const double infinity = solver->infinity();
// x[j] is an array of non-negative, integer variables.
std::vector<const MPVariable*> x(data.num_vars);
for (int j = 0; j < data.num_vars; ++j) {
x[j] = solver->MakeIntVar(0.0, infinity, "");
}
LOG(INFO) << "Number of variables = " << solver->NumVariables();
Java
double infinity = java.lang.Double.POSITIVE_INFINITY;
MPVariable[] x = new MPVariable[data.numVars];
for (int j = 0; j < data.numVars; ++j) {
x[j] = solver.makeIntVar(0.0, infinity, "");
}
System.out.println("Number of variables = " + solver.numVariables());
C#
Variable[] x = new Variable[data.NumVars];
for (int j = 0; j < data.NumVars; j++)
{
x[j] = solver.MakeIntVar(0.0, double.PositiveInfinity, $"x_{j}");
}
Console.WriteLine("Number of variables = " + solver.NumVariables());
تحديد القيود
يضع الرمز التالي قيودًا على المثال باستخدام الطريقة
MakeRowConstraint (أو بعض الصيغ حسب لغة الترميز). أول وسيطتين إلى الطريقة هما الحدان السفليان والأعلى للقيد. الوسيطة الثالثة، وهي اسم للقيد، اختيارية.
لكل قيد، يمكنك تحديد معامِلات المتغيرات باستخدام الطريقة SetCoefficient. تعيّن الطريقة مُعامل المتغير
x[j] في القيد i ليكون الإدخال [i][j] في الصفيف
constraint_coeffs.
Python
for i in range(data["num_constraints"]):
constraint = solver.RowConstraint(0, data["bounds"][i], "")
for j in range(data["num_vars"]):
constraint.SetCoefficient(x[j], data["constraint_coeffs"][i][j])
print("Number of constraints =", solver.NumConstraints())
# In Python, you can also set the constraints as follows.
# for i in range(data['num_constraints']):
# constraint_expr = \
# [data['constraint_coeffs'][i][j] * x[j] for j in range(data['num_vars'])]
# solver.Add(sum(constraint_expr) <= data['bounds'][i])
C++
// Create the constraints.
for (int i = 0; i < data.num_constraints; ++i) {
MPConstraint* constraint = solver->MakeRowConstraint(0, data.bounds[i], "");
for (int j = 0; j < data.num_vars; ++j) {
constraint->SetCoefficient(x[j], data.constraint_coeffs[i][j]);
}
}
LOG(INFO) << "Number of constraints = " << solver->NumConstraints();
Java
// Create the constraints.
for (int i = 0; i < data.numConstraints; ++i) {
MPConstraint constraint = solver.makeConstraint(0, data.bounds[i], "");
for (int j = 0; j < data.numVars; ++j) {
constraint.setCoefficient(x[j], data.constraintCoeffs[i][j]);
}
}
System.out.println("Number of constraints = " + solver.numConstraints());
C#
for (int i = 0; i < data.NumConstraints; ++i)
{
Constraint constraint = solver.MakeConstraint(0, data.Bounds[i], "");
for (int j = 0; j < data.NumVars; ++j)
{
constraint.SetCoefficient(x[j], data.ConstraintCoeffs[i, j]);
}
}
Console.WriteLine("Number of constraints = " + solver.NumConstraints());
تحديد الهدف
تحدد التعليمة البرمجية التالية دالة الهدف للمثال. تحدّد الطريقة SetCoefficient معاملات الهدف، في حين أنّ السمة SetMaximization تعرّف هذه السمة على أنّها مشكلة لأقصى حد.
Python
objective = solver.Objective()
for j in range(data["num_vars"]):
objective.SetCoefficient(x[j], data["obj_coeffs"][j])
objective.SetMaximization()
# In Python, you can also set the objective as follows.
# obj_expr = [data['obj_coeffs'][j] * x[j] for j in range(data['num_vars'])]
# solver.Maximize(solver.Sum(obj_expr))
C++
// Create the objective function.
MPObjective* const objective = solver->MutableObjective();
for (int j = 0; j < data.num_vars; ++j) {
objective->SetCoefficient(x[j], data.obj_coeffs[j]);
}
objective->SetMaximization();
Java
MPObjective objective = solver.objective();
for (int j = 0; j < data.numVars; ++j) {
objective.setCoefficient(x[j], data.objCoeffs[j]);
}
objective.setMaximization();
C#
Objective objective = solver.Objective();
for (int j = 0; j < data.NumVars; ++j)
{
objective.SetCoefficient(x[j], data.ObjCoeffs[j]);
}
objective.SetMaximization();
الاتصال بأداة الحلّ
يستدعي الرمز التالي أداة الحلّ.
Python
print(f"Solving with {solver.SolverVersion()}")
status = solver.Solve()
C++
const MPSolver::ResultStatus result_status = solver->Solve();
Java
final MPSolver.ResultStatus resultStatus = solver.solve();
C#
Solver.ResultStatus resultStatus = solver.Solve();
عرض الحلّ
تعرض التعليمة البرمجية التالية الحل.
Python
if status == pywraplp.Solver.OPTIMAL:
print("Objective value =", solver.Objective().Value())
for j in range(data["num_vars"]):
print(x[j].name(), " = ", x[j].solution_value())
print()
print(f"Problem solved in {solver.wall_time():d} milliseconds")
print(f"Problem solved in {solver.iterations():d} iterations")
print(f"Problem solved in {solver.nodes():d} branch-and-bound nodes")
else:
print("The problem does not have an optimal solution.")
C++
// Check that the problem has an optimal solution.
if (result_status != MPSolver::OPTIMAL) {
LOG(FATAL) << "The problem does not have an optimal solution.";
}
LOG(INFO) << "Solution:";
LOG(INFO) << "Optimal objective value = " << objective->Value();
for (int j = 0; j < data.num_vars; ++j) {
LOG(INFO) << "x[" << j << "] = " << x[j]->solution_value();
}
Java
// Check that the problem has an optimal solution.
if (resultStatus == MPSolver.ResultStatus.OPTIMAL) {
System.out.println("Objective value = " + objective.value());
for (int j = 0; j < data.numVars; ++j) {
System.out.println("x[" + j + "] = " + x[j].solutionValue());
}
System.out.println();
System.out.println("Problem solved in " + solver.wallTime() + " milliseconds");
System.out.println("Problem solved in " + solver.iterations() + " iterations");
System.out.println("Problem solved in " + solver.nodes() + " branch-and-bound nodes");
} else {
System.err.println("The problem does not have an optimal solution.");
}
C#
// 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("Solution:");
Console.WriteLine("Optimal objective value = " + solver.Objective().Value());
for (int j = 0; j < data.NumVars; ++j)
{
Console.WriteLine("x[" + j + "] = " + x[j].SolutionValue());
}
إليك حل المشكلة.
Number of variables = 5 Number of constraints = 4 Objective value = 260.0 x[0] = 10.0 x[1] = 16.0 x[2] = 4.0 x[3] = 4.0 x[4] = 3.0 Problem solved in 29.000000 milliseconds Problem solved in 315 iterations Problem solved in 13 branch-and-bound nodes
البرامج المكتملة
إليك البرامج الكاملة.
Python
from ortools.linear_solver import pywraplp
def create_data_model():
"""Stores the data for the problem."""
data = {}
data["constraint_coeffs"] = [
[5, 7, 9, 2, 1],
[18, 4, -9, 10, 12],
[4, 7, 3, 8, 5],
[5, 13, 16, 3, -7],
]
data["bounds"] = [250, 285, 211, 315]
data["obj_coeffs"] = [7, 8, 2, 9, 6]
data["num_vars"] = 5
data["num_constraints"] = 4
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
infinity = solver.infinity()
x = {}
for j in range(data["num_vars"]):
x[j] = solver.IntVar(0, infinity, "x[%i]" % j)
print("Number of variables =", solver.NumVariables())
for i in range(data["num_constraints"]):
constraint = solver.RowConstraint(0, data["bounds"][i], "")
for j in range(data["num_vars"]):
constraint.SetCoefficient(x[j], data["constraint_coeffs"][i][j])
print("Number of constraints =", solver.NumConstraints())
# In Python, you can also set the constraints as follows.
# for i in range(data['num_constraints']):
# constraint_expr = \
# [data['constraint_coeffs'][i][j] * x[j] for j in range(data['num_vars'])]
# solver.Add(sum(constraint_expr) <= data['bounds'][i])
objective = solver.Objective()
for j in range(data["num_vars"]):
objective.SetCoefficient(x[j], data["obj_coeffs"][j])
objective.SetMaximization()
# In Python, you can also set the objective as follows.
# obj_expr = [data['obj_coeffs'][j] * x[j] for j in range(data['num_vars'])]
# solver.Maximize(solver.Sum(obj_expr))
print(f"Solving with {solver.SolverVersion()}")
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
print("Objective value =", solver.Objective().Value())
for j in range(data["num_vars"]):
print(x[j].name(), " = ", x[j].solution_value())
print()
print(f"Problem solved in {solver.wall_time():d} milliseconds")
print(f"Problem solved in {solver.iterations():d} iterations")
print(f"Problem solved in {solver.nodes():d} branch-and-bound nodes")
else:
print("The problem does not have an optimal solution.")
if __name__ == "__main__":
main()
C++
#include <memory>
#include <vector>
#include "ortools/linear_solver/linear_solver.h"
namespace operations_research {
struct DataModel {
const std::vector<std::vector<double>> constraint_coeffs{
{5, 7, 9, 2, 1},
{18, 4, -9, 10, 12},
{4, 7, 3, 8, 5},
{5, 13, 16, 3, -7},
};
const std::vector<double> bounds{250, 285, 211, 315};
const std::vector<double> obj_coeffs{7, 8, 2, 9, 6};
const int num_vars = 5;
const int num_constraints = 4;
};
void MipVarArray() {
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;
}
const double infinity = solver->infinity();
// x[j] is an array of non-negative, integer variables.
std::vector<const MPVariable*> x(data.num_vars);
for (int j = 0; j < data.num_vars; ++j) {
x[j] = solver->MakeIntVar(0.0, infinity, "");
}
LOG(INFO) << "Number of variables = " << solver->NumVariables();
// Create the constraints.
for (int i = 0; i < data.num_constraints; ++i) {
MPConstraint* constraint = solver->MakeRowConstraint(0, data.bounds[i], "");
for (int j = 0; j < data.num_vars; ++j) {
constraint->SetCoefficient(x[j], data.constraint_coeffs[i][j]);
}
}
LOG(INFO) << "Number of constraints = " << solver->NumConstraints();
// Create the objective function.
MPObjective* const objective = solver->MutableObjective();
for (int j = 0; j < data.num_vars; ++j) {
objective->SetCoefficient(x[j], data.obj_coeffs[j]);
}
objective->SetMaximization();
const MPSolver::ResultStatus result_status = solver->Solve();
// Check that the problem has an optimal solution.
if (result_status != MPSolver::OPTIMAL) {
LOG(FATAL) << "The problem does not have an optimal solution.";
}
LOG(INFO) << "Solution:";
LOG(INFO) << "Optimal objective value = " << objective->Value();
for (int j = 0; j < data.num_vars; ++j) {
LOG(INFO) << "x[" << j << "] = " << x[j]->solution_value();
}
}
} // namespace operations_research
int main(int argc, char** argv) {
operations_research::MipVarArray();
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;
/** MIP example with a variable array. */
public class MipVarArray {
static class DataModel {
public final double[][] constraintCoeffs = {
{5, 7, 9, 2, 1},
{18, 4, -9, 10, 12},
{4, 7, 3, 8, 5},
{5, 13, 16, 3, -7},
};
public final double[] bounds = {250, 285, 211, 315};
public final double[] objCoeffs = {7, 8, 2, 9, 6};
public final int numVars = 5;
public final int numConstraints = 4;
}
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;
}
double infinity = java.lang.Double.POSITIVE_INFINITY;
MPVariable[] x = new MPVariable[data.numVars];
for (int j = 0; j < data.numVars; ++j) {
x[j] = solver.makeIntVar(0.0, infinity, "");
}
System.out.println("Number of variables = " + solver.numVariables());
// Create the constraints.
for (int i = 0; i < data.numConstraints; ++i) {
MPConstraint constraint = solver.makeConstraint(0, data.bounds[i], "");
for (int j = 0; j < data.numVars; ++j) {
constraint.setCoefficient(x[j], data.constraintCoeffs[i][j]);
}
}
System.out.println("Number of constraints = " + solver.numConstraints());
MPObjective objective = solver.objective();
for (int j = 0; j < data.numVars; ++j) {
objective.setCoefficient(x[j], data.objCoeffs[j]);
}
objective.setMaximization();
final MPSolver.ResultStatus resultStatus = solver.solve();
// Check that the problem has an optimal solution.
if (resultStatus == MPSolver.ResultStatus.OPTIMAL) {
System.out.println("Objective value = " + objective.value());
for (int j = 0; j < data.numVars; ++j) {
System.out.println("x[" + j + "] = " + x[j].solutionValue());
}
System.out.println();
System.out.println("Problem solved in " + solver.wallTime() + " milliseconds");
System.out.println("Problem solved in " + solver.iterations() + " iterations");
System.out.println("Problem solved in " + solver.nodes() + " branch-and-bound nodes");
} else {
System.err.println("The problem does not have an optimal solution.");
}
}
private MipVarArray() {}
}
C#
using System;
using Google.OrTools.LinearSolver;
public class MipVarArray
{
class DataModel
{
public double[,] ConstraintCoeffs = {
{ 5, 7, 9, 2, 1 },
{ 18, 4, -9, 10, 12 },
{ 4, 7, 3, 8, 5 },
{ 5, 13, 16, 3, -7 },
};
public double[] Bounds = { 250, 285, 211, 315 };
public double[] ObjCoeffs = { 7, 8, 2, 9, 6 };
public int NumVars = 5;
public int NumConstraints = 4;
}
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.NumVars];
for (int j = 0; j < data.NumVars; j++)
{
x[j] = solver.MakeIntVar(0.0, double.PositiveInfinity, $"x_{j}");
}
Console.WriteLine("Number of variables = " + solver.NumVariables());
for (int i = 0; i < data.NumConstraints; ++i)
{
Constraint constraint = solver.MakeConstraint(0, data.Bounds[i], "");
for (int j = 0; j < data.NumVars; ++j)
{
constraint.SetCoefficient(x[j], data.ConstraintCoeffs[i, j]);
}
}
Console.WriteLine("Number of constraints = " + solver.NumConstraints());
Objective objective = solver.Objective();
for (int j = 0; j < data.NumVars; ++j)
{
objective.SetCoefficient(x[j], data.ObjCoeffs[j]);
}
objective.SetMaximization();
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("Solution:");
Console.WriteLine("Optimal objective value = " + solver.Objective().Value());
for (int j = 0; j < data.NumVars; ++j)
{
Console.WriteLine("x[" + j + "] = " + x[j].SolutionValue());
}
Console.WriteLine("\nAdvanced usage:");
Console.WriteLine("Problem solved in " + solver.WallTime() + " milliseconds");
Console.WriteLine("Problem solved in " + solver.Iterations() + " iterations");
Console.WriteLine("Problem solved in " + solver.Nodes() + " branch-and-bound nodes");
}
}