이 페이지는 Cloud Translation API를 통해 번역되었습니다.

배열을 사용하여 모델 정의

이전 섹션에서는 몇 가지 변수만 사용하여 MIP를 해결하는 방법을 살펴보았습니다. 개별적으로 정의됩니다. 큰 문제에는 배열을 반복함으로써 변수와 제약 조건을 정의하는 데 편리합니다. 이 다음 예시를 통해 이를 확인할 수 있습니다.

예

이 예에서는 다음 문제를 해결해 보겠습니다.

최대 7x₁ + 8x₂ + 2x₃ + 9x₄ + 6x₅는 다음 제약 조건이 적용됩니다.

5 x₁ + 7x₂ 이상 9x₃ 이상 2 x₄ + 1x₅ &leq; 250명
18x₁ 이상 4 x₂ - 9x₃ 이상 10x₄ 이상 12 x₅ &leq; 285명
4x₁ 이상 7x₂ 이상 3 x₃ + 8x₄ 이상 5x₅ &leq; 211명
5 x₁ + 13 x₂ + 16x₃ 이상 3 x₄ - 7x₅ &leq; 315명

여기서 x₁, x₂, ..., x₅는 음수가 아닙니다. 정수입니다.

다음 섹션에서는 이 문제를 해결하는 프로그램을 보여줍니다. 프로그램 이전 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;
};

자바

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;

자바

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

자바

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

자바

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). 이 메서드는 변수의 계수를 할당합니다. 제약조건 i의 x[j]가 배열의 [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();

자바

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

자바

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

자바

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

자바

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

자바

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