एमआईपी समस्या को हल करना

नीचे दिए गए सेक्शन में, एमआईपी समस्या का एक उदाहरण दिया गया है. साथ ही, इसे हल करने का तरीका भी बताया गया है. इस समस्या की जानकारी नीचे दी गई है:

x + 10y को इन शर्तों के आधार पर बढ़ाएं:

  1. x + 7y ≤ 17.5
  2. 0 ≤ x ≤ 3.5
  3. 0 ≤ y
  4. x, y पूर्णांक

कंस्ट्रेंट लीनियर होते हैं, इसलिए यह सिर्फ़ लीनियर ऑप्टिमाइज़ेशन की समस्या है. इसमें पूर्णांक होने के लिए, समाधान की ज़रूरत होती है. नीचे दिए गए ग्राफ़ में, समस्या के लिए जिस इलाके का इस्तेमाल किया जा सकता है वहां के पूर्णांकों में पॉइंट दिखाए गए हैं.

संभव क्षेत्र

ध्यान दें कि यह समस्या, एलपी समस्या को हल करने में बताए गए लीनियर ऑप्टिमाइज़ेशन के समस्या से काफ़ी मिलते-जुलते हैं. हालांकि, इस मामले में हमें समस्याओं के हल पूर्णांक बनाने चाहिए.

MIP समस्या को हल करने के बुनियादी चरण

एमआईपी की समस्या को हल करने के लिए, आपके प्रोग्राम में ये चरण शामिल होने चाहिए:

  1. लीनियर सॉल्वर रैपर इंपोर्ट करें.
  2. MIP सॉल्वर का एलान करो
  3. और वैरिएबल तय करें,
  4. उन सीमाओं को तय करते हैं,
  5. और हमारे प्रॉडक्ट का मकसद
  6. एमआईपी सॉल्वर को कॉल करो और
  7. समाधान दिखाएं

एमपीसॉल्वर की मदद से समाधान पाना

इस सेक्शन में एक ऐसा प्रोग्राम दिया गया है जो MPSolver रैपर और एमआईपी सॉल्वर की मदद से सवाल हल करता है.

OR-टूल एमआईपी सॉल्वर, डिफ़ॉल्ट तौर पर SCIP है.

लीनियर सॉल्वर रैपर इंपोर्ट करना

OR-टूल लीनियर सॉल्वर रैपर, इंपोर्ट (या शामिल करें) करें. यह एमआईपी सॉल्वर और लीनियर सॉल्वर के लिए एक इंटरफ़ेस है, जैसा कि यहां दिखाया गया है.

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;

एमआईपी सॉल्वर का एलान करना

नीचे दिया गया कोड, सवाल के लिए एमआईपी सॉल्वर का एलान करता है. इस उदाहरण में, थर्ड पार्टी सॉल्वर 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());

यह प्रोग्राम, x और y वैरिएबल बनाने के लिए 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. हालांकि, जैसा कि आपको आगे दिखेगा हालांकि, ऐसा नहीं है.

लीनियर सवाल को हल करने के लिए, पिछले सेक्शन में दिए गए प्रोग्राम में आसानी से बदलाव किया जा सकता है. इसके लिए, आपको ये बदलाव करने होंगे:

  • एमआईपी सॉल्वर को बदलना

    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

    # 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 के बराबर होता है. इस ग्राफ़ में लीनियर और इंटीजर, दोनों से जुड़े सवालों का हल दिखाया गया है.

ध्यान दें कि संभव क्षेत्र में अन्य पूर्णांकों की तुलना में, पूर्णांक समाधान लीनियर सलूशन के करीब नहीं है. आम तौर पर, लीनियर ऑप्टिमाइज़ेशन समस्या के समाधान और उससे जुड़े पूर्णांक ऑप्टिमाइज़ेशन की समस्याओं के समाधान, काफ़ी अलग हो सकते हैं. इस वजह से, दोनों तरह की समस्याओं को हल करने के लिए अलग-अलग तरीकों की ज़रूरत होती है.