Giải quyết vấn đề MIP

Các phần sau đây trình bày ví dụ về vấn đề MIP và cho biết cách giải quyết. Sau đây là vấn đề:

Tối đa hoá x + 10y tuân theo các điều kiện ràng buộc sau:

1. x + 7y ≤ 17,5
2. 0 ≤ x ≤ 3,5
3. 0 ≤ y
4. x, y số nguyên

Vì các điều kiện ràng buộc là tuyến tính, nên đây chỉ là bài toán tối ưu hoá tuyến tính, trong đó nghiệm bắt buộc phải là số nguyên. Biểu đồ dưới đây cho thấy các điểm số nguyên trong khu vực khả thi cho vấn đề.

Xin lưu ý rằng vấn đề này rất giống với bài toán tối ưu hoá tuyến tính được mô tả trong bài viết Giải quyết vấn đề LP, nhưng trong trường hợp này, chúng tôi yêu cầu giải pháp phải là số nguyên.

Các bước cơ bản để giải bài tập MIP

Để giải quyết vấn đề MIP, chương trình của bạn nên bao gồm các bước sau:

1. Nhập trình bao bọc trình giải tuyến tính
2. khai báo trình giải MIP,
3. xác định các biến,
4. xác định các điều kiện ràng buộc
5. xác định mục tiêu,
6. gọi trình giải MIP và
7. hiển thị giải pháp

Giải pháp sử dụng MPSolver

Phần sau đây trình bày một chương trình giải quyết vấn đề bằng cách sử dụng trình bao bọc MPSolver và trình giải MIP.

Lưu ý: Để chạy chương trình bên dưới, bạn cần cài đặt OR-Tools.

Trình phân giải MIP của công cụ OR-Tools mặc định là SCIP.

Nhập trình bao bọc trình giải tuyến tính

Nhập (hoặc thêm) trình bao bọc trình phân giải tuyến tính OR-Tools, một giao diện dành cho trình phân giải MIP và trình phân giải tuyến tính, như được hiển thị dưới đây.

Python

from ortools.linear_solver import pywraplp

C++

#include <memory>

#include "ortools/linear_solver/linear_solver.h"

Java

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;

Khai báo trình giải MIP

Mã sau đây khai báo trình giải MIP cho bài toán. Ví dụ này sử dụng trình giải toán SCIP của bên thứ ba.

Lưu ý: Nếu bạn tạo OR-Tools từ nguồn và muốn cài đặt cũng như sử dụng một trình phân giải khác, hãy xem hướng dẫn hướng dẫn cài đặt cho nền tảng của bạn.

Python

# Create the mip solver with the SCIP backend.
solver = pywraplp.Solver.CreateSolver("SAT")
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;
}

Xác định các biến

Đoạn mã sau đây xác định các biến trong bài toán.

Python

infinity = solver.infinity()
# x and y are integer non-negative variables.
x = solver.IntVar(0.0, infinity, "x")
y = solver.IntVar(0.0, infinity, "y")

print("Number of variables =", solver.NumVariables())

C++

const double infinity = solver->infinity();
// x and y are integer non-negative variables.
MPVariable* const x = solver->MakeIntVar(0.0, infinity, "x");
MPVariable* const y = solver->MakeIntVar(0.0, infinity, "y");

LOG(INFO) << "Number of variables = " << solver->NumVariables();

Java

double infinity = java.lang.Double.POSITIVE_INFINITY;
// x and y are integer non-negative variables.
MPVariable x = solver.makeIntVar(0.0, infinity, "x");
MPVariable y = solver.makeIntVar(0.0, infinity, "y");

System.out.println("Number of variables = " + solver.numVariables());

C#

// x and y are integer non-negative variables.
Variable x = solver.MakeIntVar(0.0, double.PositiveInfinity, "x");
Variable y = solver.MakeIntVar(0.0, double.PositiveInfinity, "y");

Console.WriteLine("Number of variables = " + solver.NumVariables());

Chương trình dùng phương thức MakeIntVar (hoặc một biến thể, tuỳ thuộc vào ngôn ngữ lập trình) để tạo các biến x và y nhận giá trị số nguyên không âm.

Xác định các điều kiện ràng buộc

Đoạn mã sau đây xác định các quy tắc ràng buộc cho bài toán.

Python

# x + 7 * y <= 17.5.
solver.Add(x + 7 * y <= 17.5)

# x <= 3.5.
solver.Add(x <= 3.5)

print("Number of constraints =", solver.NumConstraints())

C++

// x + 7 * y <= 17.5.
MPConstraint* const c0 = solver->MakeRowConstraint(-infinity, 17.5, "c0");
c0->SetCoefficient(x, 1);
c0->SetCoefficient(y, 7);

// x <= 3.5.
MPConstraint* const c1 = solver->MakeRowConstraint(-infinity, 3.5, "c1");
c1->SetCoefficient(x, 1);
c1->SetCoefficient(y, 0);

LOG(INFO) << "Number of constraints = " << solver->NumConstraints();

Java

// x + 7 * y <= 17.5.
MPConstraint c0 = solver.makeConstraint(-infinity, 17.5, "c0");
c0.setCoefficient(x, 1);
c0.setCoefficient(y, 7);

// x <= 3.5.
MPConstraint c1 = solver.makeConstraint(-infinity, 3.5, "c1");
c1.setCoefficient(x, 1);
c1.setCoefficient(y, 0);

System.out.println("Number of constraints = " + solver.numConstraints());

C#

// x + 7 * y <= 17.5.
solver.Add(x + 7 * y <= 17.5);

// x <= 3.5.
solver.Add(x <= 3.5);

Console.WriteLine("Number of constraints = " + solver.NumConstraints());

Xác định mục tiêu

Đoạn mã sau đây xác định objective function cho vấn đề.

Python

# Maximize x + 10 * y.
solver.Maximize(x + 10 * y)

C++

// Maximize x + 10 * y.
MPObjective* const objective = solver->MutableObjective();
objective->SetCoefficient(x, 1);
objective->SetCoefficient(y, 10);
objective->SetMaximization();

Java

// Maximize x + 10 * y.
MPObjective objective = solver.objective();
objective.setCoefficient(x, 1);
objective.setCoefficient(y, 10);
objective.setMaximization();

C#

// Maximize x + 10 * y.
solver.Maximize(x + 10 * y);

Gọi trình giải

Mã sau đây gọi trình giải quyết.

Python

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

C++

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

Java

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

C#

Solver.ResultStatus resultStatus = solver.Solve();

Hiển thị giải pháp

Mã sau đây sẽ hiển thị giải pháp.

Python

if status == pywraplp.Solver.OPTIMAL:
    print("Solution:")
    print("Objective value =", solver.Objective().Value())
    print("x =", x.solution_value())
    print("y =", y.solution_value())
else:
    print("The problem does not have an optimal solution.")

C++

LOG(INFO) << "Solution:";
LOG(INFO) << "Objective value = " << objective->Value();
LOG(INFO) << "x = " << x->solution_value();
LOG(INFO) << "y = " << y->solution_value();

Java

if (resultStatus == MPSolver.ResultStatus.OPTIMAL) {
  System.out.println("Solution:");
  System.out.println("Objective value = " + objective.value());
  System.out.println("x = " + x.solutionValue());
  System.out.println("y = " + y.solutionValue());
} 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("Objective value = " + solver.Objective().Value());
Console.WriteLine("x = " + x.SolutionValue());
Console.WriteLine("y = " + y.SolutionValue());

Sau đây là giải pháp cho vấn đề này.

Number of variables = 2
Number of constraints = 2
Solution:
Objective value = 23
x = 3
y = 2

Giá trị tối ưu của hàm mục tiêu là 23, xảy ra tại điểm x = 3, y = 2.

Hoàn thành chương trình

Sau đây là các chương trình đầy đủ.

Python

from ortools.linear_solver import pywraplp


def main():
    # Create the mip solver with the SCIP backend.
    solver = pywraplp.Solver.CreateSolver("SAT")
    if not solver:
        return

    infinity = solver.infinity()
    # x and y are integer non-negative variables.
    x = solver.IntVar(0.0, infinity, "x")
    y = solver.IntVar(0.0, infinity, "y")

    print("Number of variables =", solver.NumVariables())

    # x + 7 * y <= 17.5.
    solver.Add(x + 7 * y <= 17.5)

    # x <= 3.5.
    solver.Add(x <= 3.5)

    print("Number of constraints =", solver.NumConstraints())

    # Maximize x + 10 * y.
    solver.Maximize(x + 10 * y)

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

    if status == pywraplp.Solver.OPTIMAL:
        print("Solution:")
        print("Objective value =", solver.Objective().Value())
        print("x =", x.solution_value())
        print("y =", y.solution_value())
    else:
        print("The problem does not have an optimal solution.")

    print("\nAdvanced usage:")
    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")


if __name__ == "__main__":
    main()

C++

#include <memory>

#include "ortools/linear_solver/linear_solver.h"

namespace operations_research {
void SimpleMipProgram() {
  // 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 and y are integer non-negative variables.
  MPVariable* const x = solver->MakeIntVar(0.0, infinity, "x");
  MPVariable* const y = solver->MakeIntVar(0.0, infinity, "y");

  LOG(INFO) << "Number of variables = " << solver->NumVariables();

  // x + 7 * y <= 17.5.
  MPConstraint* const c0 = solver->MakeRowConstraint(-infinity, 17.5, "c0");
  c0->SetCoefficient(x, 1);
  c0->SetCoefficient(y, 7);

  // x <= 3.5.
  MPConstraint* const c1 = solver->MakeRowConstraint(-infinity, 3.5, "c1");
  c1->SetCoefficient(x, 1);
  c1->SetCoefficient(y, 0);

  LOG(INFO) << "Number of constraints = " << solver->NumConstraints();

  // Maximize x + 10 * y.
  MPObjective* const objective = solver->MutableObjective();
  objective->SetCoefficient(x, 1);
  objective->SetCoefficient(y, 10);
  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) << "Objective value = " << objective->Value();
  LOG(INFO) << "x = " << x->solution_value();
  LOG(INFO) << "y = " << y->solution_value();

  LOG(INFO) << "\nAdvanced usage:";
  LOG(INFO) << "Problem solved in " << solver->wall_time() << " milliseconds";
  LOG(INFO) << "Problem solved in " << solver->iterations() << " iterations";
  LOG(INFO) << "Problem solved in " << solver->nodes()
            << " branch-and-bound nodes";
}
}  // namespace operations_research

int main(int argc, char** argv) {
  operations_research::SimpleMipProgram();
  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;

/** Minimal Mixed Integer Programming example to showcase calling the solver. */
public final class SimpleMipProgram {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();
    // 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;
    // x and y are integer non-negative variables.
    MPVariable x = solver.makeIntVar(0.0, infinity, "x");
    MPVariable y = solver.makeIntVar(0.0, infinity, "y");

    System.out.println("Number of variables = " + solver.numVariables());

    // x + 7 * y <= 17.5.
    MPConstraint c0 = solver.makeConstraint(-infinity, 17.5, "c0");
    c0.setCoefficient(x, 1);
    c0.setCoefficient(y, 7);

    // x <= 3.5.
    MPConstraint c1 = solver.makeConstraint(-infinity, 3.5, "c1");
    c1.setCoefficient(x, 1);
    c1.setCoefficient(y, 0);

    System.out.println("Number of constraints = " + solver.numConstraints());

    // Maximize x + 10 * y.
    MPObjective objective = solver.objective();
    objective.setCoefficient(x, 1);
    objective.setCoefficient(y, 10);
    objective.setMaximization();

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

    if (resultStatus == MPSolver.ResultStatus.OPTIMAL) {
      System.out.println("Solution:");
      System.out.println("Objective value = " + objective.value());
      System.out.println("x = " + x.solutionValue());
      System.out.println("y = " + y.solutionValue());
    } else {
      System.err.println("The problem does not have an optimal solution!");
    }

    System.out.println("\nAdvanced usage:");
    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");
  }

  private SimpleMipProgram() {}
}

C#

using System;
using Google.OrTools.LinearSolver;

public class SimpleMipProgram
{
    static void Main()
    {
        // Create the linear solver with the SCIP backend.
        Solver solver = Solver.CreateSolver("SCIP");
        if (solver is null)
        {
            return;
        }

        // x and y are integer non-negative variables.
        Variable x = solver.MakeIntVar(0.0, double.PositiveInfinity, "x");
        Variable y = solver.MakeIntVar(0.0, double.PositiveInfinity, "y");

        Console.WriteLine("Number of variables = " + solver.NumVariables());

        // x + 7 * y <= 17.5.
        solver.Add(x + 7 * y <= 17.5);

        // x <= 3.5.
        solver.Add(x <= 3.5);

        Console.WriteLine("Number of constraints = " + solver.NumConstraints());

        // Maximize x + 10 * y.
        solver.Maximize(x + 10 * y);

        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("Objective value = " + solver.Objective().Value());
        Console.WriteLine("x = " + x.SolutionValue());
        Console.WriteLine("y = " + y.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");
    }
}

So sánh tính năng tối ưu hoá tuyến tính và số nguyên

Hãy so sánh lời giải cho bài toán tối ưu hoá số nguyên như trình bày ở trên với giải pháp cho bài toán tối ưu hoá tuyến tính tương ứng, trong đó các điều kiện ràng buộc là số nguyên bị xoá. Bạn có thể đoán rằng giải pháp cho vấn đề số nguyên sẽ là điểm số nguyên trong vùng khả thi gần với nghiệm tuyến tính nhất — cụ thể là điểm x = 0, y = 2. Nhưng như bạn sẽ thấy tiếp theo, không phải vậy.

Bạn có thể dễ dàng sửa đổi chương trình trong phần trước để giải quyết vấn đề tuyến tính bằng cách thực hiện những thay đổi sau:

• Thay thế trình giải MIP

  Python

  # Create the mip solver with the SCIP backend.
  solver = pywraplp.Solver.CreateSolver("SAT")
  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;
  }

  với trình giải LP

  Python

  # Create the linear solver with the GLOP backend.
  solver = pywraplp.Solver.CreateSolver("GLOP")
  if not solver:
      return

  C++

  // Create the linear solver with the GLOP backend.
  std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("GLOP"));

  Java

  // Create the linear solver with the GLOP backend.
  MPSolver solver = MPSolver.createSolver("GLOP");
  if (solver == null) {
    System.out.println("Could not create solver SCIP");
    return;
  }

  C#

  // Create the linear solver with the GLOP backend.
  Solver solver = Solver.CreateSolver("GLOP");
  if (solver is null)
  {
      return;
  }

• Thay thế các biến số nguyên

  Python

  infinity = solver.infinity()
  # x and y are integer non-negative variables.
  x = solver.IntVar(0.0, infinity, "x")
  y = solver.IntVar(0.0, infinity, "y")
  
  print("Number of variables =", solver.NumVariables())

  C++

  const double infinity = solver->infinity();
  // x and y are integer non-negative variables.
  MPVariable* const x = solver->MakeIntVar(0.0, infinity, "x");
  MPVariable* const y = solver->MakeIntVar(0.0, infinity, "y");
  
  LOG(INFO) << "Number of variables = " << solver->NumVariables();

  Java

  double infinity = java.lang.Double.POSITIVE_INFINITY;
  // x and y are integer non-negative variables.
  MPVariable x = solver.makeIntVar(0.0, infinity, "x");
  MPVariable y = solver.makeIntVar(0.0, infinity, "y");
  
  System.out.println("Number of variables = " + solver.numVariables());

  C#

  // x and y are integer non-negative variables.
  Variable x = solver.MakeIntVar(0.0, double.PositiveInfinity, "x");
  Variable y = solver.MakeIntVar(0.0, double.PositiveInfinity, "y");
  
  Console.WriteLine("Number of variables = " + solver.NumVariables());

  với các biến liên tục

  Python

  infinity = solver.infinity()
  # Create the variables x and y.
  x = solver.NumVar(0.0, infinity, "x")
  y = solver.NumVar(0.0, infinity, "y")
  
  print("Number of variables =", solver.NumVariables())

  C++

  const double infinity = solver->infinity();
  // Create the variables x and y.
  MPVariable* const x = solver->MakeNumVar(0.0, infinity, "x");
  MPVariable* const y = solver->MakeNumVar(0.0, infinity, "y");
  
  LOG(INFO) << "Number of variables = " << solver->NumVariables();

  Java

  double infinity = java.lang.Double.POSITIVE_INFINITY;
  // Create the variables x and y.
  MPVariable x = solver.makeNumVar(0.0, infinity, "x");
  MPVariable y = solver.makeNumVar(0.0, infinity, "y");
  
  System.out.println("Number of variables = " + solver.numVariables());

  C#

  // Create the variables x and y.
  Variable x = solver.MakeNumVar(0.0, double.PositiveInfinity, "x");
  Variable y = solver.MakeNumVar(0.0, double.PositiveInfinity, "y");
  
  Console.WriteLine("Number of variables = " + solver.NumVariables());

Sau khi thực hiện những thay đổi này và chạy lại chương trình, bạn sẽ nhận được kết quả sau:

Number of variables = 2
Number of constraints = 2
Objective value = 25.000000
x = 0.000000
y = 2.500000

Nghiệm cho bài toán tuyến tính xảy ra tại điểm x = 0, y = 2.5, trong đó hàm mục tiêu bằng 25. Sau đây là biểu đồ minh hoạ các giải pháp cho cả bài toán tuyến tính và bài toán số nguyên.

Lưu ý rằng giải pháp số nguyên không gần với nghiệm tuyến tính, so với hầu hết các điểm số nguyên khác trong khu vực khả thi. Nhìn chung, các giải pháp cho bài toán tối ưu hoá tuyến tính và bài toán tối ưu hoá số nguyên tương ứng có thể khác nhau. Do đó, 2 loại vấn đề này yêu cầu các phương thức khác nhau để tìm giải pháp.