Halaman ini diterjemahkan oleh Cloud Translation API.

Menggunakan Array untuk Menentukan Model

Bagian sebelumnya menunjukkan cara menyelesaikan MIP hanya dengan beberapa variabel dan batasan data, yang ditentukan satu per satu. Untuk masalah yang lebih besar, akan lebih lebih mudah untuk menentukan variabel dan batasan dengan melakukan loop pada array. Tujuan contoh berikutnya menggambarkan hal ini.

Contoh

Dalam contoh ini, kita akan menyelesaikan masalah berikut.

Maksimalkan 7x₁ + 8x₂ + 2x₃ + 9x₄ + 6x₅ dengan batasan berikut:

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

dengan x₁, x₂, ..., x₅ adalah non-negatif bilangan bulat.

Bagian berikut menampilkan program yang dapat memecahkan masalah ini. Program gunakan metode yang sama seperti contoh MIP sebelumnya, tetapi dalam hal ini menerapkannya ke nilai-nilai array dalam sebuah loop.

Mendeklarasikan pemecah

Dalam program MIP apa pun, Anda mulai dengan mengimpor mendeklarasikan pemecah masalah MIP, seperti dalam contoh MIP sebelumnya.

Membuat data

Kode berikut membuat array yang berisi data untuk contoh: koefisien variabel untuk batasan dan fungsi objektif, dan batas untuk batasan-batasannya.

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

Membuat instance data

Kode berikut membuat instance model data.

Python

data = create_data_model()

C++

DataModel data;

Java

final DataModel data = new DataModel();

C#

DataModel data = new DataModel();

Membuat instance pemecah

Kode berikut membuat instance pemecah.

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

Menentukan variabel

Kode berikut menentukan variabel untuk contoh dalam sebuah loop. Untuk ukuran besar masalah, ini lebih mudah daripada mendefinisikan variabel satu per satu, seperti contoh sebelumnya.

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

Menentukan batasan

Kode berikut membuat batasan untuk contoh, menggunakan metode MakeRowConstraint (atau varian tertentu, bergantung pada bahasa coding). Tujuan dua argumen pertama untuk metode ini adalah batas bawah dan atas untuk batasan data. Argumen ketiga, nama untuk batasan, bersifat opsional.

Untuk setiap batasan, Anda menentukan koefisien variabel menggunakan metode SetCoefficient. Metode ini menetapkan koefisien variabel x[j] dalam batasan i untuk menjadi entri [i][j] dari array 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());

Menentukan tujuan

Kode berikut menentukan fungsi objektif untuk contoh. Tujuan Metode SetCoefficient menetapkan koefisien untuk tujuan, sedangkan SetMaximization mendefinisikan hal ini sebagai masalah pemaksimalan.

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

Memanggil pemecah masalah

Kode berikut memanggil pemecah.

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

Menampilkan solusi

Kode berikut menampilkan solusinya.

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

Berikut adalah solusi untuk masalah tersebut.

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

Selesaikan program

Berikut adalah program lengkapnya.

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