เริ่มต้นใช้งาน OR-Tools สำหรับ .Net

ส่วนต่อไปนี้จะช่วยคุณเริ่มต้นใช้งาน "หรือ" เครื่องมือสำหรับ .Net:

ปัญหาในการเพิ่มประสิทธิภาพคืออะไร

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

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

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

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

    วิธีแก้ปัญหาที่เหมาะสมที่สุดคือวิธีที่ค่าของฟังก์ชันวัตถุประสงค์นั้นดีที่สุด ("ดีที่สุด" อาจเป็นจำนวนสูงสุดหรือต่ำสุดก็ได้)

  • ข้อจำกัด - ข้อจำกัดในวิธีแก้ปัญหาที่เป็นไปได้โดยอิงตามข้อกำหนดเฉพาะของปัญหา เช่น หากบริษัทจัดส่งไม่สามารถกำหนดพัสดุที่มีน้ำหนักเกินกว่าที่กำหนดสำหรับรถบรรทุกได้ จะทำให้เกิดข้อจำกัดในโซลูชัน

    วิธีแก้ปัญหาที่ทำได้คือวิธีที่ทำตามข้อจำกัดทั้งหมดที่กำหนดของปัญหาได้โดยไม่จำเป็นต้องมีประสิทธิภาพสูงสุด

ขั้นตอนแรกในการแก้ปัญหาการเพิ่มประสิทธิภาพคือการระบุวัตถุประสงค์และข้อจำกัด

การแก้ไขปัญหาการเพิ่มประสิทธิภาพในไฟล์ .Net

ต่อไป เราจะยกตัวอย่างปัญหาการเพิ่มประสิทธิภาพ และแสดงวิธีตั้งค่าและแก้ปัญหาในไฟล์ .Net

ตัวอย่างการเพิ่มประสิทธิภาพเชิงเส้น

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

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

  1. 0 ≤ x ≤ 1
  2. 0 ≤ y ≤ 2
  3. x + y ≤ 2

ฟังก์ชันวัตถุประสงค์ในตัวอย่างนี้คือ 3x + y นิพจน์เชิงเส้นจะเป็นตัวกำหนดทั้งฟังก์ชันวัตถุประสงค์และข้อจำกัดต่างๆ ซึ่งทำให้เป็นปัญหาเชิงเส้น

ขั้นตอนหลักในการแก้ปัญหา

ขั้นตอนพื้นฐานในการตั้งค่าและแก้ปัญหาสำหรับแต่ละภาษาจะเหมือนกัน

  1. นำเข้าไลบรารีที่จำเป็น
  2. ประกาศเครื่องมือแก้โจทย์
  3. สร้างตัวแปร
  4. กำหนดข้อจำกัด
  5. กำหนดฟังก์ชันวัตถุประสงค์
  6. เรียกใช้เครื่องมือแก้โจทย์และ
  7. แสดงผลลัพธ์

โปรแกรม .Net

หัวข้อนี้จะอธิบายถึงโปรแกรม .Net ที่ตั้งและแก้ปัญหา

มีขั้นตอนดังนี้

  • นำเข้าไลบรารีที่จำเป็น 
    using System;
using Google.OrTools.Init;
using Google.OrTools.LinearSolver;
  • ประกาศเครื่องมือแก้โจทย์ 
    // Create the linear solver with the GLOP backend.
Solver solver = Solver.CreateSolver("GLOP");
if (solver is null)
{
    Console.WriteLine("Could not create solver GLOP");
    return;
}
    MPSolver เป็น Wrapper สำหรับการแก้ปัญหาการเขียนโปรแกรมเชิงเส้นหรือการเขียนโปรแกรมจำนวนเต็มผสม
  • สร้างตัวแปร 
    // Create the variables x and y.
Variable x = solver.MakeNumVar(0.0, 1.0, "x");
Variable y = solver.MakeNumVar(0.0, 2.0, "y");

Console.WriteLine("Number of variables = " + solver.NumVariables());
  • กำหนดข้อจำกัด ข้อจำกัด 2 รายการแรก ได้แก่ 0 ≤ x ≤ 1 และ 0 ≤ y ≤ 2 กำหนดตามคำนิยามของตัวแปรแล้ว โค้ดต่อไปนี้เป็นตัวกำหนดข้อจำกัด x + y ≤ 2: 
    // Create a linear constraint, x + y <= 2.
Constraint constraint = solver.MakeConstraint(double.NegativeInfinity, 2.0, "constraint");
constraint.SetCoefficient(x, 1);
constraint.SetCoefficient(y, 1);

Console.WriteLine("Number of constraints = " + solver.NumConstraints());
    เมธอด SetCoefficient ตั้งค่าสัมประสิทธิ์ของ x และ y ในนิพจน์สำหรับข้อจำกัด
  • กำหนดฟังก์ชันวัตถุประสงค์ 
    // Create the objective function, 3 * x + y.
Objective objective = solver.Objective();
objective.SetCoefficient(x, 3);
objective.SetCoefficient(y, 1);
objective.SetMaximization();
    เมธอด setMaximization ประกาศว่านี่เป็นปัญหาการเพิ่มจำนวน (เมธอด C++ ที่ระบุคือ SetMaximization
  • เรียกใช้เครื่องมือแก้โจทย์คณและแสดงผลลัพธ์ 
    Console.WriteLine("Solving with " + solver.SolverVersion());
Solver.ResultStatus resultStatus = solver.Solve();
Console.WriteLine("Status: " + resultStatus);
if (resultStatus != Solver.ResultStatus.OPTIMAL)
{
    Console.WriteLine("The problem does not have an optimal solution!");
    if (resultStatus == Solver.ResultStatus.FEASIBLE)
    {
        Console.WriteLine("A potentially suboptimal solution was found");
    }
    else
    {
        Console.WriteLine("The solver could not solve the problem.");
        return;
    }
}

Console.WriteLine("Solution:");
Console.WriteLine("Objective value = " + solver.Objective().Value());
Console.WriteLine("x = " + x.SolutionValue());
Console.WriteLine("y = " + y.SolutionValue());

ดำเนินการตามโปรแกรมสำเร็จ

โปรดดูโปรแกรมที่สมบูรณ์ด้านล่าง

using System;
using Google.OrTools.Init;
using Google.OrTools.LinearSolver;

public class BasicExample
{
    static void Main()
    {
        Console.WriteLine("Google.OrTools version: " + OrToolsVersion.VersionString());

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

        // Create the variables x and y.
        Variable x = solver.MakeNumVar(0.0, 1.0, "x");
        Variable y = solver.MakeNumVar(0.0, 2.0, "y");

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

        // Create a linear constraint, x + y <= 2.
        Constraint constraint = solver.MakeConstraint(double.NegativeInfinity, 2.0, "constraint");
        constraint.SetCoefficient(x, 1);
        constraint.SetCoefficient(y, 1);

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

        // Create the objective function, 3 * x + y.
        Objective objective = solver.Objective();
        objective.SetCoefficient(x, 3);
        objective.SetCoefficient(y, 1);
        objective.SetMaximization();

        Console.WriteLine("Solving with " + solver.SolverVersion());
        Solver.ResultStatus resultStatus = solver.Solve();

        Console.WriteLine("Status: " + resultStatus);
        if (resultStatus != Solver.ResultStatus.OPTIMAL)
        {
            Console.WriteLine("The problem does not have an optimal solution!");
            if (resultStatus == Solver.ResultStatus.FEASIBLE)
            {
                Console.WriteLine("A potentially suboptimal solution was found");
            }
            else
            {
                Console.WriteLine("The solver could not solve the problem.");
                return;
            }
        }

        Console.WriteLine("Solution:");
        Console.WriteLine("Objective value = " + solver.Objective().Value());
        Console.WriteLine("x = " + x.SolutionValue());
        Console.WriteLine("y = " + y.SolutionValue());

        Console.WriteLine("Advanced usage:");
        Console.WriteLine("Problem solved in " + solver.WallTime() + " milliseconds");
        Console.WriteLine("Problem solved in " + solver.Iterations() + " iterations");
    }
}

การใช้งานโปรแกรม .Net

คุณเรียกใช้โปรแกรมข้างต้นได้โดยทำดังนี้

  1. คัดลอกและวางโค้ดด้านบนลงในไฟล์ใหม่แล้วบันทึกเป็น BasicExample.cs ในไดเรกทอรีย่อย examples/dotnet ของไดเรกทอรีที่คุณติดตั้ง OR-Tools
  2. ในไดเรกทอรีเดียวกัน ให้สร้างไฟล์ BasicExample.csproj ใหม่ แล้วเพิ่มโค้ดต่อไปนี้
    <Project Sdk="Microsoft.NET.Sdk">
  <PropertyGroup>
    <OutputType>Exe</OutputType>
    <LangVersion>7.3</LangVersion>
    <TargetFramework>netcoreapp3.1</TargetFramework>
    <EnableDefaultItems>false</EnableDefaultItems>
    <!-- see https://github.com/dotnet/docs/issues/12237 -->
    <RollForward>LatestMajor</RollForward>
    <RestoreSources>../../../temp_dotnet/packages;$(RestoreSources);https://api.nuget.org/v3/index.json</RestoreSources>
    <AssemblyName>Google.OrTools.BasicExample</AssemblyName>
    <IsPackable>true</IsPackable>
  </PropertyGroup>

  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
    <DebugType>full</DebugType>
    <Optimize>true</Optimize>
    <GenerateTailCalls>true</GenerateTailCalls>
  </PropertyGroup>

  <ItemGroup>
    <Compile Include="BasicExample.cs" />
    <PackageReference Include="Google.OrTools" Version="9.1.*" />
  </ItemGroup>
</Project>
  3. ที่ระดับบนสุดของไดเรกทอรีที่ติดตั้ง "OR-Tools" ให้เปิดหน้าต่างคำสั่งและป้อนข้อมูลต่อไปนี้ 
    make run SOURCE=examples/dotnet/BasicExample.cs

คุณอาจบันทึกและเรียกใช้โปรแกรม .Net ในไดเรกทอรีที่แตกต่างจาก examples/dotnet/ ได้ แต่ยากกว่าเล็กน้อย นั่นคือคุณต้องแก้ไขบรรทัดต่อไปนี้ของไฟล์ csproj ซึ่งแสดงด้านบน 

../../../packages;$(RestoreSources);https://api.nuget.org/v3/index.json
เพื่อให้มีเส้นทางที่ถูกต้องไปยังไดเรกทอรี packages

วิธีแก้ปัญหาที่ง่ายที่สุดคือใส่โปรแกรม .Net ไว้ในไดเรกทอรี examples/dotnet/

โปรแกรมจะแสดงผลค่าของ x และ y ที่เพิ่มฟังก์ชันวัตถุประสงค์สูงสุด:

Solution:
x =  1.0
y =  1.0

หากต้องการคอมไพล์โปรแกรมโดยไม่ต้องเรียกใช้ ให้ป้อน:

make build SOURCE=relative/path/to/SimpleProgram.cs

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

ตัวอย่าง .Net เพิ่มเติม

สำหรับตัวอย่าง .Net เพิ่มเติมที่แสดงวิธีแก้ไขปัญหาการเพิ่มประสิทธิภาพประเภทต่างๆ ดูตัวอย่าง

ระบุประเภทของปัญหาที่คุณต้องการแก้ไข

ปัญหาการเพิ่มประสิทธิภาพเกิดขึ้นได้หลายประเภทในโลก โจทย์แต่ละประเภทมีวิธีการและอัลกอริทึมที่แตกต่างกันในการหาวิธีแก้ปัญหาที่เหมาะสมที่สุด

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

ด้านล่างนี้เป็นภาพรวมคร่าวๆ ของประเภทโจทย์ที่ "หรือ" แก้ไขได้ และลิงก์ไปยังส่วนต่างๆ ในคู่มือนี้ซึ่งอธิบายวิธีแก้โจทย์แต่ละประเภท

การเพิ่มประสิทธิภาพเชิงเส้น

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

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

ดูข้อมูลเพิ่มเติมเกี่ยวกับการเพิ่มประสิทธิภาพเชิงเส้น

การเพิ่มประสิทธิภาพจำนวนเต็มผสม

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

ดูข้อมูลเพิ่มเติมเกี่ยวกับการเพิ่มประสิทธิภาพจำนวนเต็มผสม

การเพิ่มประสิทธิภาพข้อจำกัด

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

ดูข้อมูลเพิ่มเติมเกี่ยวกับการเพิ่มประสิทธิภาพข้อจำกัด

การมอบหมาย

ปัญหาเกี่ยวกับการมอบหมายเกี่ยวข้องกับการมอบหมายกลุ่ม Agent (เช่น ผู้ปฏิบัติงานหรือเครื่อง) ให้กับชุดงาน ซึ่งการมอบหมายตัวแทนแต่ละรายการให้กับงานที่เฉพาะเจาะจงนั้นมีค่าใช้จ่ายคงที่ ปัญหาคือหางานที่มีต้นทุนรวมน้อยที่สุด ปัญหาในการรับงานเป็นกรณีพิเศษของปัญหาการไหลเวียนของเครือข่าย

ดูข้อมูลเพิ่มเติมเกี่ยวกับการมอบหมาย

การบรรจุหีบห่อ

การบรรจุลงในถังคือปัญหาในการบรรจุชุดวัตถุขนาดต่างๆ ลงในภาชนะที่มีความจุแตกต่างกัน เป้าหมายคือบรรจุออบเจ็กต์ให้ได้มากที่สุดเท่าที่จะเป็นไปได้ โดยขึ้นอยู่กับความจุของคอนเทนเนอร์ กรณีพิเศษของกรณีนี้คือปัญหา Knapsack ซึ่งมีเพียงคอนเทนเนอร์เดียว

ดูข้อมูลเพิ่มเติมเกี่ยวกับการบรรจุ Bin

Scheduling

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

ดูข้อมูลเพิ่มเติมเกี่ยวกับการกำหนดเวลา

การกำหนดเส้นทาง

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

ดูข้อมูลเพิ่มเติมเกี่ยวกับการกำหนดเส้นทาง

ขั้นตอนของเครือข่าย

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

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

ดูข้อมูลเพิ่มเติมเกี่ยวกับโฟลว์ของเครือข่าย