תחילת העבודה עם OR-Tools עבור .Net

בקטעים הבאים תוכלו להתחיל בעבודה עם כלי OR עבור .Net:

מהי בעיית אופטימיזציה?

מטרת האופטימיזציה היא למצוא את הפתרון הטוב ביותר לבעיה מתוך קבוצה גדולה של פתרונות אפשריים. (לפעמים תהיו מרוצים ממציאת פתרון ישים כלשהו; גם אתם יכולים לעשות זאת באמצעות OR-Tools).

בהמשך מתוארת בעיית אופטימיזציה אופיינית. נניח שחברת משלוחים שולחת חבילות ללקוחות שלה באמצעות צי משאיות. בכל יום, החברה צריכה להקצות חבילות למשאיות, ואז לבחור מסלול לכל משאית כדי למסור את החבילות שלה. לכל הקצאה אפשרית של חבילות ומסלולים יש עלות בהתאם למרחק הנסיעה הכולל של המשאיות, ואולי גם לגורמים אחרים. הבעיה היא לבחור את ההקצאות של חבילות ומסלולים בעלות הנמוכה ביותר.

בדומה לכל בעיות האופטימיזציה, בעיה זו כוללת את הרכיבים הבאים:

  • המטרה – הכמות שרוצים לבצע אופטימיזציה שלה. בדוגמה שלמעלה, המטרה היא למזער את העלות. כדי להגדיר בעיית אופטימיזציה, צריך להגדיר פונקציה שמחשבת את ערך המטרה עבור כל פתרון אפשרי. היא נקראת פונקציית האובייקט. בדוגמה הקודמת, פונקציית המטרה מחשבת את העלות הכוללת של כל הקצאה של חבילות ומסלולים.

    פתרון אופטימלי הוא פתרון שבו הערך של פונקציית המטרה הוא הטוב ביותר. ('הטוב ביותר' יכול להיות מקסימום או מינימום).

  • המגבלות – הגבלות על קבוצת הפתרונות האפשריים, בהתאם לדרישות הספציפיות של הבעיה. לדוגמה, במקרה שחברת המשלוחים לא יכולה להקצות למשאיות חבילות בעלות משקל מסוים, הדבר ייצור מגבלה על הפתרונות.

    פתרון בר-ביצוע הוא פתרון שעומד בכל המגבלות הנתונים של הבעיה, בלי להיות אופטימלי.

השלב הראשון בפתרון בעיית אופטימיזציה הוא זיהוי היעד והאילוצים.

פתרון בעיית אופטימיזציה ב-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());
  • מגדירים את האילוצים. שני האילוצים הראשונים, 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());
    ה-method 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, שממחישות איך לפתור סוגים שונים של בעיות אופטימיזציה, ראו דוגמאות.

זיהוי סוג הבעיה שברצונך לפתור

יש הרבה סוגים שונים של בעיות אופטימיזציה בעולם. לכל סוג של בעיה יש גישות ואלגוריתמים שונים למציאת פתרון אופטימלי.

לפני שתוכלו להתחיל לכתוב תוכנית לפתרון בעיית אופטימיזציה, עליכם לזהות את סוג הבעיה שבה אתם מתמודדים ולבחור פותר מתאים – אלגוריתם למציאת פתרון אופטימלי.

בהמשך מופיעה סקירה קצרה של סוגי הבעיות שנפתרות באמצעות OR-Tools, וקישורים לקטעים במדריך זה שמסבירים איך לפתור כל סוג של בעיה.

אופטימיזציה לינארית

כפי שלמדתם בקטע הקודם, בעיית אופטימיזציה לינארית היא בעיה שבה פונקציית המטרה והאילוצים הם ביטויים לינאריים במשתנים.

הפותר הראשי בכלי OR-כלים לפתרון בעיות כאלה הוא פותר האופטימיזציה הלינארית, שהוא למעשה wrapper של כמה ספריות שונות, לאופטימיזציה לינארית ולאופטימיזציה של מספרים שלמים מעורבים, כולל ספריות של צד שלישי.

מידע נוסף על אופטימיזציה לינארית

אופטימיזציה של מספרים מעורבים שלמים

בעיה באופטימיזציה של מספרים שלמים מעורבים היא בעיה שבה חלק מהמשתנים או כולם חייבים להיות מספרים שלמים. בעיה בהקצאה, למשל, היא שצריך להקצות קבוצת עובדים לקבוצת משימות. לכל עובד ומשימה, עליכם להגדיר משתנה שהערך שלו הוא 1 אם העובד הנתון מוקצה למשימה הנתונה, אחרת הערך הוא 0. במקרה הזה, המשתנים יכולים לקבל רק את הערכים 0 או 1.

מידע נוסף על אופטימיזציה של מספרים מעורבים

אופטימיזציה של מגבלות

אופטימיזציה אילוצים, או תכנות אילוצים (CP), מזהה פתרונות אפשריים מתוך קבוצה גדולה מאוד של מועמדים, שבהם ניתן ליצור מודל לבעיה באמצעות אילוצים שרירותיים. הבדיקה מבוססת על היתכנות (מציאת פתרון בר-ביצוע) ולא על אופטימיזציה (מציאת פתרון אופטימלי) ומתמקדת באילוצים ובמשתנים ולא בפונקציה למטרה. אבל אפשר להשתמש ב-CP כדי לפתור בעיות אופטימיזציה פשוט על ידי השוואת הערכים של פונקציית המטרה לכל הפתרונות האפשריים.

מידע נוסף על אופטימיזציה של אילוצים

מטלה

בעיות בהקצאה כוללות הקצאה של קבוצת סוכנים (למשל, עובדים או מכונות) לקבוצת משימות, שבה יש עלות קבועה להקצאה של כל סוכן למשימה ספציפית. הבעיה היא למצוא את המטלה עם העלות הכוללת הנמוכה ביותר. בעיות בהקצאה הן למעשה מקרה מיוחד של בעיות בזרימת הרשת.

למידע נוסף על הקצאה

אריזה

אריזת פחים היא הבעיה באריזת קבוצת אובייקטים בגדלים שונים במיכלים עם קיבולת שונה. המטרה היא לארוז כמה שיותר אובייקטים, בכפוף לקיבולת של הקונטיינרים. מקרה מיוחד לכך הוא בעיית Knapsack, שבה יש רק קונטיינר אחד.

מידע נוסף על אריזה בסל

תזמון

בעיות תזמון כוללות הקצאת משאבים לביצוע סדרת משימות בזמנים ספציפיים. דוגמה חשובה היא בעיה של חנות עבודות, שבה מספר משימות מעובדות במספר מכונות. כל משימה מורכבת מרצף של משימות, שצריכות להתבצע בסדר נתון ושצריך לעבד כל משימה במכונה ספציפית. הבעיה היא להקצות לוח זמנים כדי שכל המשימות יושלמו בפרק זמן קצר ככל האפשר.

מידע נוסף על תזמון

יצירת מסלול מתבצעת

בעיות שקשורות למסלולים כוללות מציאת המסלולים האופטימליים בשביל צי כלי רכב שחוצים רשת, לפי גרף מכוון. הבעיה של הקצאת חבילות למשאיות משלוחים, המתוארת בקטע מהי בעיית אופטימיזציה?, היא אחת הדוגמאות לבעיית מסלול. בעיה אחרת היא הבעיה של אנשי המכירות בנסיעה.

מידע נוסף על מסלולים

זרימות רשת

אפשר לייצג בעיות אופטימיזציה רבות על ידי גרף מכוון שמכיל צמתים וקשתות מכוונות ביניהם. לדוגמה, אפשר לייצג בעיות תחבורה, שבהן סחורות נשלחות ברשת מסילות, בתרשים שבו הקשתות הן קווי רכבת והצמתים הם מרכזי הפצה.

במקרה של בעיית הזרימה המקסימלית, לכל קשת יש קיבולת מקסימלית שאפשר להעביר אליה. הבעיה היא להקצות את כמות הסחורות שצריך לשלוח בכל קשת, כדי שהכמות הכוללת תהיה גדולה ככל האפשר.

מידע נוסף על תהליכי עבודה ברשת