การแก้ปัญหา MIP

ส่วนต่อไปนี้แสดงตัวอย่างปัญหา MIP และแสดงวิธีแก้โจทย์ ปัญหามีดังต่อไปนี้

เพิ่ม x + 10y ให้มากที่สุดภายใต้ข้อจำกัดต่อไปนี้

  1. x + 7y ≤ 17.5
  2. 0 ≤ x ≤ 3.5
  3. 0 ≤ y
  4. x, จำนวนเต็ม y รายการ

เนื่องจากข้อจำกัดเป็นแบบเชิงเส้น นี่จึงเป็นเพียงปัญหาการเพิ่มประสิทธิภาพเชิงเส้นเท่านั้น ซึ่งคำตอบนั้นต้องเป็นจำนวนเต็ม กราฟด้านล่างแสดงจุดจำนวนเต็มในบริเวณที่เป็นไปได้ของปัญหา

ภูมิภาคที่เป็นไปได้

โปรดสังเกตว่าปัญหานี้คล้ายกับโจทย์การเพิ่มประสิทธิภาพเชิงเส้นมากที่อธิบายไว้ในการแก้ปัญหาหน้า LP แต่ในกรณีนี้เราต้องการคำตอบที่เป็นจำนวนเต็ม

ขั้นตอนพื้นฐานสำหรับการแก้ปัญหา MIP

หากต้องการแก้ไขปัญหา MIP โปรแกรมของคุณควรมีขั้นตอนต่อไปนี้

  1. นำเข้า Wrapper ของตัวแก้วิดีโอเชิงเส้น
  2. ประกาศเครื่องมือแก้โจทย์ MIP
  3. กำหนดตัวแปร
  4. กำหนดข้อจำกัด
  5. กำหนดวัตถุประสงค์
  6. เรียกใช้โปรแกรมแก้ MIP และ
  7. แสดงโซลูชัน

โซลูชันที่ใช้ MPSolver

ส่วนต่อไปนี้จะแสดงโปรแกรมที่แก้ปัญหาโดยใช้ Wrapper ของ MPSolver และเครื่องมือแก้โจทย์ MIP

โปรแกรมแก้โจทย์ MIP ของ OR-Tools เริ่มต้นคือ SCIP

นำเข้า Wrapper เครื่องมือแก้โจทย์เชิงเส้น

นำเข้า (หรือรวม) Wrapper เครื่องมือแก้โจทย์เชิงเส้น "หรือ" ซึ่งเป็นอินเทอร์เฟซสำหรับเครื่องมือแก้ปัญหา MIP และเครื่องมือแก้โจทย์เชิงเส้นดังที่แสดงด้านล่าง

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;

ประกาศเครื่องมือแก้โจทย์ MIP

โค้ดต่อไปนี้ประกาศโปรแกรมแก้ MIP ของโจทย์ ตัวอย่างนี้ใช้ SCIP ซึ่งเป็นเครื่องมือแก้โจทย์ของบุคคลที่สาม

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

กำหนดตัวแปร

รหัสต่อไปนี้จะกำหนดตัวแปรที่มีปัญหา

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

โปรแกรมจะใช้เมธอด MakeIntVar (หรือตัวแปรโดยขึ้นอยู่กับภาษาที่เขียนโค้ด) เพื่อสร้างตัวแปร x และ y ที่ใช้ค่าจำนวนเต็มที่ไม่ติดลบ

กําหนดข้อจํากัด

รหัสต่อไปนี้จะระบุข้อจำกัดสำหรับปัญหาดังกล่าว

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

กําหนดวัตถุประสงค์

รหัสต่อไปนี้กำหนด objective function สำหรับปัญหาดังกล่าว

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

เรียกใช้เครื่องมือแก้โจทย์

โค้ดต่อไปนี้จะเรียกตัวแก้โจทย์

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

แสดงคำตอบ

โค้ดต่อไปนี้จะแสดงโซลูชัน

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

วิธีแก้ปัญหามีดังนี้

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

ค่าที่เหมาะสมที่สุดของฟังก์ชันวัตถุประสงค์คือ 23 ซึ่งจะเกิดขึ้นที่จุด x = 3, y = 2

เข้าร่วมโปรแกรม

โปรแกรมทั้งหมดมีดังนี้

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

การเปรียบเทียบการเพิ่มประสิทธิภาพเชิงเส้นและจำนวนเต็ม

มาเปรียบเทียบวิธีการแก้โจทย์การเพิ่มประสิทธิภาพจำนวนเต็มที่แสดงด้านบนกับวิธีแก้ปัญหาการเพิ่มประสิทธิภาพเชิงเส้นที่ตรงกัน ซึ่งมีการนำข้อจำกัดจำนวนเต็มออก คุณอาจเดาได้ว่าคำตอบของจำนวนเต็มจะเป็นจุดจำนวนเต็มในภูมิภาคที่เป็นไปได้และใกล้กับคำตอบเชิงเส้นที่สุด นั่นคือจุด x = 0 ซึ่งก็คือ y = 2 แต่อย่างที่คุณจะเห็นในลำดับต่อไป คงไม่เป็นเช่นนั้นแล้ว

คุณแก้ไขโปรแกรมในส่วนก่อนหน้าเพื่อแก้ปัญหาเชิงเส้นได้ง่ายๆ โดยทำการเปลี่ยนแปลงต่อไปนี้

  • แทนที่เครื่องมือแก้โจทย์ 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;
}
    ด้วยโปรแกรมแก้ 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;
}
  • แทนที่ตัวแปรจำนวนเต็ม

    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());
    ที่มีตัวแปรต่อเนื่อง

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

หลังจากทำการเปลี่ยนแปลงเหล่านี้และเรียกใช้โปรแกรมอีกครั้งแล้ว คุณจะได้ผลลัพธ์ต่อไปนี้

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

การแก้โจทย์เชิงเส้นจะเกิดขึ้นที่จุด x = 0 ซึ่งเท่ากับ y = 2.5 ซึ่งฟังก์ชันวัตถุประสงค์เท่ากับ 25 นี่คือกราฟแสดงวิธีแก้ปัญหาทั้ง แบบเชิงเส้นและจำนวนเต็ม

โปรดสังเกตว่าคำตอบที่เป็นจำนวนเต็มไม่ได้ใกล้เคียงกับผลเฉลยเชิงเส้น เมื่อเทียบกับจุดที่เป็นจำนวนเต็มอื่นๆ ส่วนใหญ่ในบริเวณที่เป็นไปได้ โดยทั่วไป วิธีแก้ปัญหาการเพิ่มประสิทธิภาพเชิงเส้นและปัญหาการเพิ่มประสิทธิภาพจำนวนเต็มที่เกี่ยวข้องอาจอยู่ห่างกันมาก ด้วยเหตุนี้ ปัญหาทั้ง 2 ประเภทนี้จึงต้องการ วิธีแก้ปัญหาที่ต่างกัน