این صفحه به‌وسیله ‏Cloud Translation API‏ ترجمه شده است.

استفاده از آرایه ها برای تعریف مدل

بخش قبل نشان داد که چگونه می توان یک MIP را تنها با چند متغیر و محدودیت که به صورت جداگانه تعریف می شوند، حل کرد. برای مشکلات بزرگ‌تر، تعریف متغیرها و محدودیت‌ها با حلقه زدن روی آرایه‌ها راحت‌تر است. مثال بعدی این را نشان می دهد.

مثال

در این مثال مشکل زیر را حل خواهیم کرد.

7 x ₁ + 8 x ₂ + 2 x ₃ + 9 x ₄ + 6 x ₅ را با توجه به محدودیت‌های زیر به حداکثر برسانید:

5 x ₁ + 7 x ₂ + 9 x ₃ + 2 x ₄ + 1 x ₅ ≤ 250
18 x ₁ + 4 x ₂ - 9 x ₃ + 10 x ₄ + 12 x ₅ ≤ 285
4 x ₁ + 7 x ₂ + 3 x ₃ + 8 x ₄ + 5 x ₅ ≤ 211
5 x ₁ + 13 x ₂ + 16 x ₃ + 3 x ₄ - 7 x ₅ ≤ 315

که در آن x ₁ ، x ₂ ، ...، x ₅ اعداد صحیح غیر منفی هستند.

در بخش های زیر برنامه هایی ارائه می شود که این مشکل را حل می کنند. برنامه‌ها از روش‌های مشابه مثال قبلی MIP استفاده می‌کنند، اما در این مورد آنها را روی مقادیر آرایه در یک حلقه اعمال می‌کنند.

حل کننده را اعلام کنید

در هر برنامه MIP، همانطور که در مثال MIP قبلی نشان داده شده است، با وارد کردن پوشش حل کننده خطی و اعلام حل کننده MIP شروع می کنید.

داده ها را ایجاد کنید

کد زیر آرایه هایی حاوی داده های مثال ایجاد می کند: ضرایب متغیر برای محدودیت ها و تابع هدف، و کران هایی برای محدودیت ها.

پایتون

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;
};

جاوا

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;
}

سی شارپ

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;
}

نمونه سازی داده ها

کد زیر مدل داده را نمونه سازی می کند.

پایتون

data = create_data_model()

C++

DataModel data;

جاوا

final DataModel data = new DataModel();

سی شارپ

DataModel data = new DataModel();

حل کننده را نمونه سازی کنید

کد زیر حل کننده را نمونه سازی می کند.

پایتون

# 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;
}

سی شارپ

// Create the linear solver with the SCIP backend.
Solver solver = Solver.CreateSolver("SCIP");
if (solver is null)
{
    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())

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();

جاوا

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());

سی شارپ

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 اختصاص می‌دهد.

پایتون

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();

جاوا

// 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());

سی شارپ

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 این را به عنوان یک مشکل حداکثر سازی تعریف می کند.

پایتون

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();

جاوا

MPObjective objective = solver.objective();
for (int j = 0; j < data.numVars; ++j) {
  objective.setCoefficient(x[j], data.objCoeffs[j]);
}
objective.setMaximization();

سی شارپ

Objective objective = solver.Objective();
for (int j = 0; j < data.NumVars; ++j)
{
    objective.SetCoefficient(x[j], data.ObjCoeffs[j]);
}
objective.SetMaximization();

با حل کننده تماس بگیرید

کد زیر حل کننده را فراخوانی می کند.

پایتون

print(f"Solving with {solver.SolverVersion()}")
status = solver.Solve()

C++

const MPSolver::ResultStatus result_status = solver->Solve();

جاوا

final MPSolver.ResultStatus resultStatus = solver.solve();

سی شارپ

Solver.ResultStatus resultStatus = 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.")

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();
}

جاوا

// 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.");
}

سی شارپ

// 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

برنامه های کامل

در اینجا برنامه های کامل وجود دارد.

پایتون

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;
}

جاوا

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() {}
}

سی شارپ

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");
    }
}