תחילת העבודה עם כלי OR-כלים ל-C++

הקטעים הבאים יעזרו לך להתחיל בעבודה עם כלי OR עם ++C:

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

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

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

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

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

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

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

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

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

פתרון בעיית אופטימיזציה ב-C++

בשלב הבא נותנים דוגמה לבעיית אופטימיזציה, ומראים איך מגדירים ופותרים אותה ב-C++.

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

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

אפשר למקסם 3x + y בכפוף למגבלות הבאות:

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

פונקציית היעד בדוגמה הזו היא 3x + y. גם הפונקציה האובייקטית וגם האילוצים נקבעים באמצעות ביטויים ליניאריים, ולכן זוהי בעיה לינארית.

השלבים העיקריים לפתרון הבעיה

בכל שפה, השלבים הבסיסיים להגדרה ולפתרון של בעיה הם זהים:

  1. מייבאים את הספריות הנדרשות,
  2. מצהירים על הפותר,
  3. יוצרים את המשתנים,
  4. מגדירים את האילוצים
  5. מגדירים את פונקציית המטרה
  6. מפעילים את הפותר
  7. מציגים את התוצאות.

תוכנית C++

בקטע הזה מתוארת תוכנית C++ שמגדירה את הבעיה ופותרת אותה.

אלה השלבים:

  • מייבאים את הספריות הנדרשות. 
    #include <cstdlib>
#include <memory>

#include "absl/flags/flag.h"
#include "absl/log/flags.h"
#include "ortools/base/init_google.h"
#include "ortools/base/logging.h"
#include "ortools/init/init.h"
#include "ortools/linear_solver/linear_solver.h"
  • מצהירים על הפותר. 
    // Create the linear solver with the GLOP backend.
std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("GLOP"));
if (!solver) {
  LOG(WARNING) << "Could not create solver GLOP";
  return;
}
    MPSolver הוא wrapper לפתרון כל בעיה שקשורה לתכנות לינארי או לתכנות מספרים שלמים מעורבים.
  • יוצרים את המשתנים. 
    // Create the variables x and y.
MPVariable* const x = solver->MakeNumVar(0.0, 1, "x");
MPVariable* const y = solver->MakeNumVar(0.0, 2, "y");

LOG(INFO) << "Number of variables = " << solver->NumVariables();
  • מגדירים את האילוצים. שני האילוצים הראשונים, 0 &leq; x ≤ 1 ו-0 &leq; y ≤ 2, כבר מוגדרים על ידי ההגדרות של המשתנים. הקוד הבא מגדיר את האילוץ x + y &leq; 2:
    // Create a linear constraint, x + y <= 2.
const double infinity = solver->infinity();
MPConstraint* const ct = solver->MakeRowConstraint(-infinity, 2.0, "ct");
ct->SetCoefficient(x, 1);
ct->SetCoefficient(y, 1);

LOG(INFO) << "Number of constraints = " << solver->NumConstraints();
    ה-method SetCoefficient מגדירה את המקדמים של x ו-y בביטוי של האילוץ.
  • מגדירים את פונקציית המטרה. 
    // Create the objective function, 3 * x + y.
MPObjective* const objective = solver->MutableObjective();
objective->SetCoefficient(x, 3);
objective->SetCoefficient(y, 1);
objective->SetMaximization();
    השיטה SetMaximization מצהירה כי זו בעיית אופטימיזציה.
  • מפעילים את הפותר ומציגים את התוצאות. 
    LOG(INFO) << "Solving with " << solver->SolverVersion();
const MPSolver::ResultStatus result_status = solver->Solve();
// Check that the problem has an optimal solution.
LOG(INFO) << "Status: " << result_status;
if (result_status != MPSolver::OPTIMAL) {
  LOG(INFO) << "The problem does not have an optimal solution!";
  if (result_status == MPSolver::FEASIBLE) {
    LOG(INFO) << "A potentially suboptimal solution was found";
  } else {
    LOG(WARNING) << "The solver could not solve the problem.";
    return;
  }
}

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

השלמת התוכנית

התוכנית המלאה מוצגת למטה.

// Minimal example to call the GLOP solver.
#include <cstdlib>
#include <memory>

#include "absl/flags/flag.h"
#include "absl/log/flags.h"
#include "ortools/base/init_google.h"
#include "ortools/base/logging.h"
#include "ortools/init/init.h"
#include "ortools/linear_solver/linear_solver.h"

namespace operations_research {
void BasicExample() {
  LOG(INFO) << "Google OR-Tools version : " << OrToolsVersion::VersionString();

  // Create the linear solver with the GLOP backend.
  std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("GLOP"));
  if (!solver) {
    LOG(WARNING) << "Could not create solver GLOP";
    return;
  }

  // Create the variables x and y.
  MPVariable* const x = solver->MakeNumVar(0.0, 1, "x");
  MPVariable* const y = solver->MakeNumVar(0.0, 2, "y");

  LOG(INFO) << "Number of variables = " << solver->NumVariables();

  // Create a linear constraint, x + y <= 2.
  const double infinity = solver->infinity();
  MPConstraint* const ct = solver->MakeRowConstraint(-infinity, 2.0, "ct");
  ct->SetCoefficient(x, 1);
  ct->SetCoefficient(y, 1);

  LOG(INFO) << "Number of constraints = " << solver->NumConstraints();

  // Create the objective function, 3 * x + y.
  MPObjective* const objective = solver->MutableObjective();
  objective->SetCoefficient(x, 3);
  objective->SetCoefficient(y, 1);
  objective->SetMaximization();

  LOG(INFO) << "Solving with " << solver->SolverVersion();
  const MPSolver::ResultStatus result_status = solver->Solve();

  // Check that the problem has an optimal solution.
  LOG(INFO) << "Status: " << result_status;
  if (result_status != MPSolver::OPTIMAL) {
    LOG(INFO) << "The problem does not have an optimal solution!";
    if (result_status == MPSolver::FEASIBLE) {
      LOG(INFO) << "A potentially suboptimal solution was found";
    } else {
      LOG(WARNING) << "The solver could not solve the problem.";
      return;
    }
  }

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

  LOG(INFO) << "Advanced usage:";
  LOG(INFO) << "Problem solved in " << solver->wall_time() << " milliseconds";
  LOG(INFO) << "Problem solved in " << solver->iterations() << " iterations";
}
}  // namespace operations_research

int main(int argc, char* argv[]) {
  InitGoogle(argv[0], &argc, &argv, true);
  absl::SetFlag(&FLAGS_stderrthreshold, 0);
  operations_research::BasicExample();
  return EXIT_SUCCESS;
}

הפעלת התוכנית C++

אפשר להריץ את התוכנית שלמעלה באופן הבא:

  1. מעתיקים, מדביקים את הקוד שלמעלה בקובץ חדש, ושומרים אותו בתור program.cc.
  2. פותחים חלון פקודה ברמה העליונה של הספרייה שבה התקנתם את OR-Tools, ומזינים:
    make run SOURCE=relative/path/to/program.cc
    כאשר relative/path/to/ הוא הנתיב לספרייה שבה שמרתם את התוכנה.

התוכנית מחזירה את הערכים של x ו-y שמגדילים את פונקציית המטרה:

Solution:
x =  1.0
y =  1.0

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

make build SOURCE=relative/path/to/program.cc

הידור במצב הסכמה

כדי לבצע הידור במצב O3:

make DEBUG='-O3' all

מריצים את קובץ ההפעלה C++

בזמן הידור של תוכנית OR-Tools C++ עם make, קובץ ההפעלה נוצר בספרייה bin. תוכלו להריץ את קובץ ההפעלה של התוכנית לדוגמה באופן הבא:

cd bin && ./program

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

דוגמאות נוספות ל-C++

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

מטלה

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

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

אריזה

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

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

תזמון

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

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

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

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

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

זרימות רשת

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

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

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