حل مشکل MIP

بخش های زیر نمونه ای از یک مشکل MIP را ارائه می دهند و نحوه حل آن را نشان می دهند. مشکل اینجاست:

x + 10y با توجه به محدودیت‌های زیر به حداکثر برسانید:

  1. x + 7y ≤ 17.5
  2. 0 ≤ x ≤ 3.5
  3. 0 ≤ y
  4. x , y اعداد صحیح

از آنجایی که محدودیت ها خطی هستند، این فقط یک مسئله بهینه سازی خطی است که در آن باید راه حل ها اعداد صحیح باشند. نمودار زیر نقاط عدد صحیح را در ناحیه امکان پذیر برای مسئله نشان می دهد.

منطقه امکان پذیر

توجه داشته باشید که این مسئله بسیار شبیه به مسئله بهینه سازی خطی است که در حل مسئله LP توضیح داده شده است، اما در این مورد ما نیاز داریم که راه حل ها اعداد صحیح باشند.

مراحل اساسی برای حل یک مشکل MIP

برای حل مشکل MIP، برنامه شما باید شامل مراحل زیر باشد:

  1. وارد کردن لفاف حل خطی،
  2. حل کننده MIP را اعلام کنید،
  3. متغیرها را تعریف کنید،
  4. محدودیت ها را تعریف کنید،
  5. هدف را تعریف کنید،
  6. با حل کننده MIP تماس بگیرید و
  7. راه حل را نمایش دهید

راه حل با استفاده از MPSolver

بخش زیر برنامه ای را ارائه می دهد که با استفاده از Wrapper MPSolver و حل کننده MIP مشکل را حل می کند.

حل کننده پیش فرض OR-Tools MIP SCIP است.

لفاف حل خطی را وارد کنید

همانطور که در زیر نشان داده شده است، بسته‌بندی حل‌کننده خطی OR-Tools، رابطی برای حل‌کننده‌های MIP و حل‌کننده‌های خطی، وارد کنید (یا شامل کنید).

پایتون

from ortools.linear_solver import pywraplp

C++

#include <memory>

#include "ortools/linear_solver/linear_solver.h"

جاوا

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;

سی شارپ

using System;
using Google.OrTools.LinearSolver;

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

کد زیر حل کننده MIP مشکل را اعلام می کند. این مثال از حل کننده شخص ثالث SCIP استفاده می کند.

پایتون

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

جاوا

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

جاوا

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 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 که مقادیر صحیح غیر منفی می گیرند استفاده می کند.

محدودیت ها را تعریف کنید

کد زیر محدودیت های مشکل را تعریف می کند.

پایتون

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

جاوا

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

سی شارپ

// 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 برای مشکل تعریف می کند.

پایتون

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

جاوا

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

سی شارپ

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

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

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

پایتون

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

جاوا

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

سی شارپ

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

C++

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

جاوا

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

سی شارپ

// 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 رخ می دهد.

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

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

پایتون

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

جاوا

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

سی شارپ

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 را جایگزین کنید

    پایتون

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

    جاوا

    // 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;
}
    با حل کننده LP

    پایتون

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

    جاوا

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

    سی شارپ

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

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

    جاوا

    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 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());
    با متغیرهای پیوسته

    پایتون

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

    جاوا

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

    سی شارپ

    // 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 است.

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