נתוני גרסה של OR-כלים

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

אם נתקלתם בבעיות בהתקנה של OR-Tools, עיינו בקטע פתרון בעיות בהוראות ההתקנה של OR-Tools. אם הבעיה לא מופיעה שם, כדאי לבדוק את הבעיות ב-GitHub או לפתוח אחת חדשה, ונשמח לעזור.

בהמשך מוצגות נתוני הגרסה של כלי OR, החל מהגרסה האחרונה.

מרץ 2024

הודעה על פרסום גרסה 9.9 של OR-Tools

השקנו את גרסה 9.9 של 'OR-כלים'. כדי לעדכן את הגרסה, קראו את הקטע המתאים בהתקנת OR-Tools.

נתוני הגרסה זמינים ב-github

נובמבר 2023

הודעה על פרסום גרסה 9.8 של OR-Tools

השקנו את גרסה 9.8 של 'OR-כלים'. כדי לעדכן את הגרסה, קראו את הקטע המתאים בהתקנת OR-Tools.

שינויים בפלטפורמות

  • מוסיפים את Python 3.12.
  • הוספת תמיכה ב-Ubuntu 23.10

פותר לינארי

  • יציאה ModelBuilder אל Net.
  • שינוי השם של LogCallback ל-MbLogCallback כדי למנוע התנגשות עם SAT LogCallback.
  • Extend ModelBuilder API:
    • הוספת מגבלות על אינדיקטורים.
    • הוספת תמיכה ברמז.
    • הוספת שכפול של מודל.

אפשרויות למתמטיקה

  • עבודה מחדש עמוקה.

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

  • הוספת הסטטוס ROUTING_OPTIMAL.
  • צריך להגדיר את RoutingModel שלא ניתן להעתיק או להעביר.
  • תיקון לולאה אינסופית באופרטורים של חיפוש מקומי.
  • הוספת מבנה פנימי PickupDeliveryPosition.
  • יש להוסיף שיטות מסוג IsPickup() ו-IsDelivery().

SAT

  • הפחתת טביעת הרגל של הזיכרון במודל גדול.
  • חיפוש משופר של תזמון.
  • הוספת Packing_precedences_nns.
  • אופטימיזציה ותיקון של קפיצות בהיתכנות.
  • אופטימיזציה של Presolve לינארי ורישום טוב יותר ביומן.
  • שיפור התיקון של int_abs, int_mod, int_prod ו-lin_max.
  • שיפור התמיכה ב-Panda
  • מעט תיקוני באגים.

יומן שינוי של GitHub

אוגוסט 2023

הודעה על פרסום גרסה 9.7 של OR-Tools

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

שינויים בפלטפורמות

  • Drop Centos-8 (EOL)
  • משחררים את Debian 10.
  • Drop Fedora [33, 36] (EOL)
  • Drop Ubuntu 18.04 LTS (EOL)
  • יש לשחרר את Python 3.7 (EOL).
  • השבתת התמיכה ב-netcore3.1 ב-CMake (EOL).

python לבניית דגמים

  • מתן הרשאה לשימוש במסגרות נתונים ובסדרות של Pandas כדי ליצור משתנים.
  • השלמת פרטי ההקלדה

PDLP

  • עדכונים שונים.

CP-SAT

  • שיפורי ביצועים. (feasibility_jump, lin_max)
  • שיפור ניהול החיתוך
  • worker חדש של destination_shaving_search שמטרתו לשפר את הגבול התחתון של המטרה (כשמצמצמים אותה)
  • הקלדת הערות עבור python cp_model.py
  • תמיכה חלקית ניסיונית בפנדות ב-cp_model.py
  • עובדים ניסיוניים המבוססים על הפרות של החיפוש המקומי:
    • מופעלת עם פרמטרים: num_violation_ls:xxx
    • אופטימיזציה למודל לינארי (linear, bool_or, bool_and, at_most_one, exactly_one)
    • פועל כראוי עם lin_max, מוצר, חלוקה
    • תמיכה ב-no_חפיפה, מצטבר, מעגל, מסלולים
    • מושבת עם no_overlap_2d
    • המספר המומלץ של עובדים: num_workers -> num_violation_ls: (8, 1), (16, 2) (24, 3), (32, 4)

יומן שינוי של GitHub

מרץ 2023

הודעה על פרסום גרסה 9.6 של OR-Tools

השקנו את גרסה 9.6 של 'OR-כלים'. כדי לעדכן את הגרסה, קראו את הקטע המתאים בהתקנת OR-Tools.

שינויים בפלטפורמות

  • הוספת תמיכה ב-Fedora 37, 38.
  • יש לשחרר את Python 3.6 (לא נתמך על ידי protobuf).
  • שחרור Python 3.7 ב-macOS (לא נתמך על ידי scipy).
  • הוספת תמיכה ב-net7.0 ב-CMake (יש להשתמש ב--DUSE_DOTNET_7=ON)
  • שחרור netcore3.1 בחבילות nuget .org

יחסי תלות

  • SCIP v801 -> v803 (הערה: מעכשיו, פרוטוקול SCIP משתמש ברישיון שתואם ל-OSI)
  • ברזיל 20220623.1 -> 20230105.0
  • Protobuf v21.5 -> v21.12
  • פעולת SWIG 4.1.1
  • Java JNA 5.11.0 -> 5.12.1

Bazel

  • הוספת תמיכה ב-pybind11.
  • הוספת תמיכה ב-Java wrapper

פותרים

  • PDLP: dd python wrapper.
  • CP-SAT: שיפורים בביצועים.
  • GOP: שינוי התיקון.
  • ModelBuilder: Python: שיפור התמיכה במספר הטלפון.
  • ניתוב: שיפורי ביצועים (חיפוש מקומי)

בעיות ידועות:

  • CP-SAT: אם מתעלמים מהפרמטר המשני pseudo_costs ומחזירים פרמטרים לא חוקיים (ראו 3706).

נובמבר 2022

הודעה על פרסום גרסה 9.5 של OR-Tools

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

שינויים בפלטפורמות

  • הוספת תמיכה ב-Debian Sid
  • הוספת תמיכה ב-Fedora 35, 36.
  • הוספת תמיכה ב-Ubuntu 22.10.
  • שחרור Python 3.6 ב-macOS.
  • הוספת תמיכה ב-Python 3.11

עדכון של יחסי התלות

  • Protobuf v19.4 -> v21.5.
  • SCIP Solver v800 -> v801.

CP-SAT

  • שיפורים לפתרון: max(array), אילוצים בוליאניים, אילוצים לינאריים.
  • חיפוש משולב צריך להיות דטרמיניסטי במקביל.
  • חתכים לינאריים: ניקוי ריבועים וקיצוצים int_prod; שכתוב צינור עיבוד הנתונים של החיתוך.
  • מודל הקלט והפתרון של טביעת האצבע (גלויים ביומן).
  • שיפורים בתזמון.
  • הקבוצה הרגילה של תיקוני באגים (קריסה במהלך תיקון, קריסה בחיתוך, פתרונות לא מעשיים, המודל לא ניתן לביצוע ב-LNS).

GLOP

  • האצה על ידי שכתוב של האלגברה הלינארית ושל כלל בחירת הציר.

פותר לינארי

  • הוספה של knapsack_interface.cc.
  • מעבירים את model_builder API לספרייה לינארי_solver (כותרות ודוגמאות).
  • הוספת תמיכה ב-Gurobi 10.

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

  • שחרר מנתח מעט בשביל אתגרי ניתוב שונים.

אוגוסט 2022

הודעה על פרסום גרסה 9.4 של OR-Tools

השקנו את גרסה 9.4 של 'OR-כלים'. כדי לעדכן את הגרסה, קראו את הקטע המתאים בהתקנת OR-Tools.

פלטפורמות

  • הוספת תמיכה ב-Debian-10 (ראו 3029).
  • הוספת תמיכה ב-Ubuntu 22.04 LTS (ראו #3276). הערה: לא תהיה תמיכה ב-Net 3.1 (ראו dotnet/core#7038).
  • הסרת התמיכה ב-Ubuntu 21.10.

שונות

  • מפצלים את הארכיון לפי שפות ומוסיפים את תצורת CMake אל C++ One (#3200).

תרשים

פיצול ortools.graph.pywrapgraph ל:

  • ortools.graph.python.linear_sum_assignment.
  • ortools.graph.python.max_flow.
  • ortools.graph.python.min_cost_flow.

פעולה זו מאפשרת להשתמש ב-numpy כדי לזרז את הגדרת הבעיות.

CP-SAT

שיפור מסוים לגבי:

  • תזמון (הפצה, חיתוך, גבולות תחתונים).
  • MaxSAT (היוריסטיקה מבוססת ליבה).
  • ביצועי MIP (תיקון, חיתוך).

מרץ 2022

הודעה על פרסום גרסה 9.3 של OR-Tools

השקנו את גרסה 9.3 של 'OR-כלים'. כדי לעדכן את הגרסה, קראו את הקטע המתאים בהתקנת OR-Tools.

שינויים בפלטפורמות

  • הפסקת התמיכה ב-Debian-10.
  • משחררים את התמיכה ב-Ubuntu-16.04.
  • לשחרר את .NET Framework 4.5.2.

עדכון של יחסי התלות

  • הוספת Eigen 3.4.0.
  • צריך להוסיף את Google re2 2021-11-01.
  • Protobuf 3.19.1 -> 3.19.4.
  • SCIP 7.0.1 -> v800.

Python

  • מוסיפים את pybind11.

פיצ'רים

  • הוספת PDLP כניסוי.
  • הוספת MathOpt כניסיוני.

CP-SAT

  • שינו כמה שמות של API כדי לשמור על עקביות, למשל LinearExpr.ScalProd. -> LinearExpr.WeightedSum..
  • צריך להוסיף שיטות מסוג AddAtLeastOne/AddAtMostOne/AddExactlyOne.
  • הוספת AddMultiplicationConstraint(z, x, y) בכל השפות.
  • הוספת AddMultipleCircuit() בכל השפות.

C++

  • בורר מפורש IntVar(BoolVar).
  • הסרת את המשתנה LinearExpr::Add* והוחלפה על ידי אופרטור, למשל LinearExpr +=.
  • חברו בין אופרטורים אריתמטיים בביטוי לינארי.
  • בוצעה הסרה של LinearExpr::BooleanSum/BooleanScalProd, שימוש ב-Sum/WeightedSum.
  • מוסיפים את הערך CpModelBuilder::FixVariable() שיחליף את הדומיין של המשתנה לערך בודד.

Java

  • כותבים מחדש את LinearExpr ומוסיפים מחלקה מצטברת של builder: LinearExpr.newBuilder().add(x).addSum(<array of variables>).build().
  • עוקבים אחרי C++ API: Circuit, MultipleCircuit, Cumulative, Reservoir, AllowedAssignment ו-ForbiddenAssignment מחזירים עכשיו מחלקה מיוחדת עם ממשק API מצטבר להוספת משתנים, מונחים, ביקוש חדשים...

C

  • חשוב לתעד את כל השיטות.
  • עוקבים אחרי C++ API: Circuit, MultipleCircuit, Cumulative, Reservoir, AllowedAssignment ו-ForbiddenAssignment מחזירים עכשיו מחלקה מיוחדת עם ממשק API מצטבר להוספת משתנים, מונחים, ביקוש חדשים...
  • צריך להוסיף מחלקה LinearExprBuilder כדי ליצור ביטויים בהדרגה.

מערכת Build

CMake

  • נדרש לפחות CMake >= 3.18.

יצרן

  • עכשיו צריך להשתמש ב-build שמבוסס על CMake באופן פנימי.

דצמבר 2021

הודעה על פרסום גרסה 9.2 של OR-Tools

השקנו את גרסה 9.2 של 'OR-כלים'. כדי לעדכן את הגרסה, קראו את הקטע המתאים בהתקנת OR-Tools.

שינויים בפלטפורמות

  • הוספת תמיכה ב-Ubuntu 21:10 (גרסה אחרונה מתגלגלת).

עדכון של יחסי התלות

  • .Net TFM update net5.0 -> net6.0 (נדרש .Net SDK 6.0 LTS ו-.Net SDK 3.1 LTS).
  • ABeil-cpp 20210324.2 -> 20211102.0.
  • Protobuf 3.18.0 -> 3.19.1.
  • Googletest 1.10.0 -> 1.11.0.
  • Python: הוסף numpy >= 1.13.3.
  • ב-MacOS, יש לבצע הידור של Coin-OR ב--O1 כדי למנוע קריסת מחשב.

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

  • שיפור במסננים.
  • שפר את היוריסטיקה של פתרון ראשון.
  • שיפור המיקומים שבהם יש הפסקות בזמן.

CP-SAT

שינויי תוכנה שעלולים לגרום לכשלים

  • מאגר הפרוטוקולים הבסיסי לא תואם לגרסאות קודמות. צריך ליצור מחדש את מאגר הפרוטוקולים שנשמר באמצעות ממשקי ה-API המעודכנים של ה-builder (ב-C++ , ב-Python, ב-Java וב-NET.)
  • באופן ספציפי, פרוטובף המרווח היה נקי כשהסרנו את השדות הישנים (התחלה, גודל וסוף) ושינינו את השם של השדות החדשים (באמצעות _view) כך שישתמשו בשם של השדות שהוסרו.

תכונות חדשות

  • האילוצים all_different, reservoir, modulo, multiplication ו-division מקבלים ביטויים בעלי זיקה (a * var + b) בכל מקום שבו נדרשים משתנים של מספרים שלמים.
  • המטרה מקבלת מקדמי נקודה צפה (ראו את המחלקה DoubleLinearExpr ב-C++/Java/.NET. ראו את הדוגמה של knapsack_2d_sat.py ב-Python).
  • האילוץ no_overlap_2d תומך במרווחים אופציונליים.
  • ה-API של C++ מטמיע את האופרטורים + ו-* כדי ליצור ביטויים.

שיפורים

  • קוד Presolve משופר.
  • בודק מודלים מדויק יותר.
  • מגבלה של מאגר הנתונים.
  • הוסף חיתוך אנרגטי לאילוץ no_overlap_2d.
  • שיפור הקלה לינארית במגבלות הקידוד (literal implies var == value).

שיטות שהוצאו משימוש והוסרו

  • C++ BooleanSum ו-BooleanScalProd הוצאו משימוש. פשוט משתמשים ב-Sum וב-ScalProd.
  • הסרת את C++ AddLinMinEquality ואת AddLinMaxEquality. פשוט משתמשים ב-AddMinEquality וב-AddMaxEquality.

חוסר תאימות עתידי

  • בשלב כלשהו בעתיד, נכתוב מחדש את שכבת המודלים של Java כדי שתהיה קרובה יותר לשכבת C++.
  • בשכבה של בניית המודלים C++, נציין שה-IntVar(BoolVar var) פועל כמפורש.
  • אנחנו שוקלים להתאים את python API ל-PEP 8 (באמצעות השמות של snake_case). במקרה כזה, נספק קובץ sed כדי לנייד את הקוד.

מערכת Build

Bazel

  • תיקון ה-build של Windows.

CMake

  • הוספת האפשרות FETCH_PYTHON_DEPS (ברירת המחדל היא ON).
  • הוספת תמיכה אופציונלית לפותר הבעיות של GPLK (ברירת המחדל היא -DUSE_GLPK=OFF).

Python

  • תמיכה במספרים שלמים numpy ברוב ה-CP-SAT API.
  • תיקון הבעיות החסרות: __version__.

ספטמבר 2021

הודעה על השקת גרסה 9.1 של OR-Tools

השקנו את גרסה 9.1 של 'OR-כלים'. כדי לעדכן את הגרסה, קראו את הקטע המתאים בהתקנת OR-Tools.

שינויים בפלטפורמות

  • Python: השתמשו בתמונה manylinux2014 (ראו PEP 599).
  • Python: הוספת תמיכה ב-aarch64 Linux באמצעות קובץ האימג' manylinux2014_aarch64.
  • .Net: הוספת תמיכה ב-.Net 5.0.

עדכון של יחסי התלות

  • ABeil-cpp 20210324.1 -> 20210324.2.
  • Protobuf 3.15.8 -> 3.18.0.
  • SCIP 7.0.1 -> מאסטר.
  • Googletest 1.8.0 -> 1.10.0.
  • python: שימוש ב-warning ב-cp_model.py (ראה #2530).
  • python: bl-py 0.11 -> 0.13.

CMake

  • הוספת הגרסה המינימלית שנדרשת הוא 3.14 -> 3.15 (פרטים נוספים זמינים ב-#2528).
  • Python: העברת הגרסה המינימלית הנדרשת של 3.14 -> 3.18 (פרטים נוספים זמינים ב-#2774).

יצרן

build מבוסס build הוצא משימוש, כדי ליצור אותו מגרסת המקור צריך לעבור ל-CMake או Bazel.

Java

  • לשפר את האמינות של טוען הספרייה המקורית (ראו #2742).
  • תיקון הקריסה של JVM Garbage Collector במהלך הניתוב של מודל הניתוב או של פתרון האילוצים (עיינו ב-#2091) (ראו #2466).
  • תיקון קריסה של קריאה חוזרת ברישום ביומן של CP-SAT כשמשתמשים במספר עובדים (למידע נוסף, ראו 2775).

CP-SAT

  • לשפר את התקינות של קוד ה-LNS (למידע נוסף, אפשר לעיין ב-#2525).
  • שיפור קוד התזמון: שיטות חדשות מהמפעל ליצירת מרווחים קבועים, היוריסטיקה חדשה של חיפוש, תיקון presolve משופר וחיתוך לינארי חדש.
  • שיפור קוד הניתוב: LNS ייעודי חדש.
  • שיפור בודק המודלים. עכשיו הוא יותר מדוקדק, במיוחד שפע של אפשרויות.
  • שיפור קוד ה-MIP: פתרון בעיות טוב יותר ושיפורים רבים ברגישות הלינארית של מודלים של MIP ו-CP.
  • שפר את מגוון החיפוש. כשמשתמשים ביותר מ-12 עובדים, צריך להוסיף עובדים שמטרתם לשפר את הגבול התחתון של המטרה.
  • שנו את קוד המקבילות: כברירת מחדל, הפותר ישתמש עכשיו בכל הליבות הזמינות. השתמשו ב-num_search_parameters על מנת לציין את רמת המקבילות.
  • הוצאה משימוש של SearchAllSolutions ושל SolveWithSolutionCallback.
  • Python API: בדיקות קפדניות יותר כשמשתמשים ב-var == ... או ב-var != ... מחוץ לקריאה ל-model.Add().

אפריל 2021

הודעה על השקת גרסה 9.0 של OR-Tools

השקנו את גרסה 9.0 של 'OR-כלים'. כדי לעדכן את הגרסה, קראו את הקטע המתאים בהתקנת OR-Tools.

עדכונים לגבי תלות

Java

תיקוני באגים

  • להשתמש בפתרון ריבוי שרשורים כשמשתמשים בפותר הבעיות CP-SAT (ראו 1588).
  • תיקון התמיכה ב-wrapper של Python ב-std::vector&ltstd::string&gt (למידע נוסף, ראו 2453).
  • תמיכה מחדש ב-CPLEX (ראו #2470).

שינויי תוכנה ידועים שעלולים לגרום לכשלים

  • הוספת גישת יומן ב-Python, Java ו-Net (ראו 2245).
  • החלפה של כל סוגי Google בהתאמה אישית על ידי הסוגים שסופקו בcstdint.

CP-SAT

  • השיטות SearchForAllSolutions(), SearchAllSolutions() ו-SolveWithSolutionCallback() הוצאו משימוש. במקומם יש להשתמש ב-Solve().
  • שיפור התמיכה באופרטורים סטנדרטיים של Python. מצב כזה עלול לשבור קוד קיים שגוי.

מרץ 2021

הודעה על פרסום גרסה 8.2 של OR-Tools

השקנו את גרסה 8.2 של 'OR-כלים'. כדי לעדכן את הגרסה, קראו את הקטע המתאים בהתקנת OR-Tools.

עדכונים לגבי תלות

  • Abseil-cpp 20200923.2 עודכן ל-LTS 20200923.3.
  • Protobuf 3.14.0 שעודכנה ל-3.15.3.

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

  • הוספת את RoutingModel.RegisterTransitMatrix() ואת RoutingModel.RegisterUnaryTransitVector().
  • משנים את ההחזרה של RoutingModel.AddVectorDimension() ושל RoutingModel.AddMatrixDimension() ל-std::pair&ltint, bool&gt ש-int הוא מזהה מעריך התחבורה הציבורית.

בדצמבר 2020

הודעה על השקת גרסה 8.1 של OR-Tools

השקנו את גרסה 8.1 של 'OR-כלים'. כדי לעדכן את הגרסה, קראו את הקטע המתאים בהתקנת OR-Tools.

עדכונים לגבי תלות

  • Abseil-cpp 20200923 עודכן ל-LTS 20200923.2.
  • Protobuf 3.13.0 שעודכנה ל-3.14.
  • הוספת תמיכה ב-Gurobi 9.1.0
  • תלות ב-GLog (במקום בהטמעה מותאמת אישית בהתאם לדגלי ABeil-cpp)
  • תלות ב-Gflags (הוחלפה על ידי רכיב דגלי gcloud-cpp)

תיקוני באגים

  • תיקון ספירה כפולה של רישיון צף של Gurobi (ראו #2227).
  • תיקון Windows build (ראו 2200#).

אוקטובר 2020

הודעה על השקת גרסה 8.0 של OR-Tools

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

שינויים בפלטפורמות

  • נוספה תמיכה ב-Python 3.9 (#2187)
  • התמיכה ב-Python 3.5 בוטלה
    • נוספה תמיכה ב-Ubuntu 20.10 (#2188) -->
  • בוטלה התמיכה ב-Ubuntu 16.04 LTS (#2188)
  • בוטלה התמיכה ב-Ubuntu 19.10 (#2188)

עדכונים לגבי תלות

  • Abseil-cpp 20200225.2 עודכן ל-LTS 20200923.
  • Protobuf 3.12.2 עודכנה ל-3.13.0.

שינויי תוכנה ידועים שעלולים לגרום לכשלים

  • עכשיו, הניתוב וקוד המקור של CP-SAT משתמשים בכמה תכונות של C++17. אזהרה: אם אתם משתמשים בגרסה משלכם של abseil-cpp, צריך לוודא שהיא נבנתה גם נגד C++17.
  • החתימה של MPSolver::CreateSolver שונתה. הארגומנט של שם המודל הוסר.

CMake

  • תיקון של השבתת התמיכה ב-SCIP כשמשתמשים ב--DUSE_SCIP=OFF (למידע נוסף, ראו 2129#).
  • שלבו דוגמאות ודוגמאות במערכת ה-build של CMake. הערה: אפשר להשבית את התכונה באמצעות -DBUILD_SAMPLES=OFF ו--DBUILD_EXAMPLES=OFF. הערה: אפשר להשבית לשפה מסוימת באמצעות -DBUILD_<LANG>_SAMPLES=OFF או -DBUILD_<LANG>_EXAMPLES=OFF.
    • עם <LANG> בין:
    • CXX,
    • PYTHON,
    • JAVA וגם
    • DOTNET.

יצרן

  • נדרש Make >= 4.3 (באמצעות ביצוע פונקציית הערכה).
  • נדרש CMake >= 3.14 (שימוש באפשרות CMake --verbose).
  • כדי להשבית את התמיכה ב-SCIP באמצעות -DUSE_SCIP=OFF, מוסיפים אפשרות (ראו 2134).
  • הוספת אפשרות להשבתת התמיכה ב-CLP וב-CBC באמצעות -DUSE_COINOR=OFF.

Java

  • OR-Tools יוצר חבילות Maven (ראו #202).

תיקוני באגים

  • איך לתקן את גרסאות ה-build של C++ ו-Python ב-FreeBSD (ראו 2126).
  • תיקון השגיאות ב-build בניפוי באגים ב-Windows (מידע נוסף זמין ב-#2077).
  • תיקון קריסת מחשב ארוכה במקביל ב-CP-SAT ב-Windows (למידע נוסף: #2001, #2019).

יולי 2020

הודעה על פרסום גרסה 7.8 של OR-Tools

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

עדכונים לגבי תלות

  • Gurobi 9.0.2 משולב כעת מראש בקבצים בינאריים מובנים מראש. הוא יחפש את הספרייה המשותפת gurobi 90 בנתיב ההתקנה המוגדר כברירת מחדל לתוכנות ההתקנה של Gurobi ב-MAC OS X וב-Windows, או בספרייה GUROBI_HOME.
  • SCIP 7.0.1 משולב כעת בקבצים בינאריים מוגדרים מראש. חשוב לוודא שאתם מצייתים לרישיון SCIP לפני שמשתמשים בו.
  • נוספה תמיכה ב-Xpress Solver 8.9.0 האופציונלי.

פותר לינארי

  • נוספה שיטת LinearSolver::CreateSolver() סטטית כדי לפשט את בדיקת התמיכה בקצוות עורפיים משולבים של פתרון לינארי. היא פועלת בכל השפות.

תיקוני באגים

  • גרסת CMake קבועה שמבוססת על FreeBSD.
  • תוקן מיון CP-SAT ביצירת חיתוך מצטבר.
  • תוקנה דליפת זיכרון של פותר לינארי ב-Net wrapper.

יוני 2020

הודעה על ההשקה של גרסה 7.7 של OR-Tools

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

עדכונים לגבי תלות

  • Abseil-cpp b832dce עודכן ל-c51510d (LTS 20200225.2).
  • Protobuf 3.11.4 עודכן ל-3.12.2.

תכונות חדשות ושיפורים

  • הפותר של CP-SAT מחזיר עכשיו Optimal במקום Feasible במודל שביעות רצון (כלומר, בלי מטרה).
  • הוספנו את היוריסטיקה של משאבת היתכנות מקהילת MIP.

תיקוני באגים

תוקנו קריסות של CP-SAT בריבוי שרשורים (ראו 2005#).

אפריל 2020

הודעה על פרסום גרסה 7.6 של OR-Tools

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

תכונות חדשות של CP-SAT

הוספנו את התכונות החדשות הבאות לפותר הבעיות של CP-SAT:

  • ניהול משופר של מישורים עבור LPs.
  • כלים לניפוי באגים.

עדכונים לגבי תלות

8ba96a8 של Abseil-cpp עודכנו ל-b832dce (LTS 20200225).

תיקוני באגים

  • תוקן באג CP-SAT UNSAT ב-presolve (הסבר על #1908).
  • תוקנה כתובת ה-URL של swigwin.exe.
  • תיקון ניהול מפת טיפוסים מסוג SWIG עבור Java ו-Net.

ינואר 2020

הודעה על השקת גרסה 7.5 של OR-Tools

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

שינויים בפלטפורמות

  • נוספה תמיכה ב-Python 3.8 (#1719)
  • אוסף התמיכה הוסר ממקורות ב-Visual Studio 2017 (#1852).
  • התמיכה עודכנה מ-Centos 7 ל-Cenos 8 (#1827).

עדכון של התלות

תיקוני באגים

הבעיות הבאות תוקנו בגרסה 7.5 של OR-Tools (לרשימה מלאה, אפשר לעיין ב-Milestone v7.5).

הקפידו במיוחד על הדברים הבאים:

  • טעינת הרכבה תוקנה. למידע נוסף, ראו #1421.
  • נחשפו השיטות GetStartIndex() ו-GetEndIndex() של RouteIndexManager (#1843).
  • תוקן SWIG להסרת שיטות לא תקינות (#1838, #1276).

אוקטובר 2019

הודעה על השקת גרסה 7.4 של OR-Tools

השקנו את גרסה 7.4 של 'OR-כלים'. כדי לעדכן את הגרסה, קראו את הקטע המתאים בהתקנת OR-Tools.

תכונות חדשות ושיפורים

  • הפותר של CP-SAT בודק עכשיו אם יש אילוצים שלא תומכים בליטרליות של האכיפה. אם לאילוץ כזה יש ליטרל אכיפה, בודק המודלים יחזיר שגיאה לפני פתרון הבעיה.
  • חיפוש מקומי טוב ומהיר יותר אחר ספריית הניתוב.
  • הפותר הלינארי תומך עכשיו בתוכנת צד שלישי Xpress-MP. כדי להשתמש בהם תצטרכו ליצור מחדש את כלי ה-OR מהמקור.
  • הארכיטקטורה של חבילת NuGet שוכתבה לחלוטין. באופן ספציפי, הוא תומך עכשיו ב- .NET framework >= 4.5.2 בפלטפורמות Windows.

פלטפורמה שהוצאה משימוש

כפי שהודענו בנתוני הגרסה ביולי 2019, OR-Tools כבר לא תומך ב-Python 2.7.

עדכון של התלות

גרסה 3.9.0 של Protobuf עודכנה ל-3.10.0.

אוגוסט 2019

הודעה על פרסום גרסה 7.3 של OR-Tools

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

פלטפורמה שהוצאה משימוש

אנחנו מוציאים משימוש את התמיכה ב-Python 2.7 כדי להתאים למעבר של Google ל-Python 3. זו תהיה הגרסה האחרונה של כלי OR-כלים שתומכים ב-Python 2.7.

עדכון של התלות

Protobuf 3.8.0 עודכן ל-3.9.0.

תיקוני באגים

הבעיות הבאות תוקנו בגרסה 7.3 של OR-Tools. (לרשימה המלאה, ראו Kanban v7.3).

הקפידו במיוחד על הדברים הבאים:

  • תוקנה בעיה בהעברה של init/int64 ב-Java (#1448),
  • תוקנה בדיקת presolve במהלך עיבוד מגבלות מצטברות ריקות.

יולי 2019

הודעה על ההשקה של גרסה 7.2 של OR-Tools

השקנו את גרסה 7.2 של 'OR-כלים'. כדי לעדכן את הגרסה, קראו את הקטע המתאים בהתקנת OR-Tools.

שינויים בפלטפורמות

  • אנחנו מוציאים משימוש את התמיכה ב-Python 2.7 כדי להתאים למעבר של Google ל-Python 3. תהיה רק גרסה אחת נוספת של OR-Tools שתומכת ב-Python 2.7.
  • Ubuntu 18.10 עודכנה ל-Ubuntu 19.04.
  • נוספה תמיכה באוסף ממקורות של Visual Studio 2019.
  • Python 3.5 כבר לא נתמך ב-Windows; יש להשתמש ב-Python 3.6 ואילך.

עדכונים בקשרי תלות

  • אנחנו מטרגטים עכשיו את CBC 2.10.3.
  • עכשיו אנחנו מטרגטים את Protobuf 3.8.0.

CP-SAT

  • ביצענו מספר שיפורים בחיפוש, במקבילות ובריכוז הלינארי.
  • נוספו ממשקי API של LinearExpr.Sum() ו-LinearExpr.ScalProd() ב-Python.
  • ממשקי ה-API IntVar[].Sum() ו-IntVar[].ScalProd() הוצאו משימוש ב-C#.
  • C++: בוצעה הסרה של SolveWithModel() כי הוא היה עותק כפול של SolveCpModel().
  • נוספו שיטות CpModel.addGreaterThan() ו-CpModel.addLessThan() ל-Java API.

פתרון לינארי

  • נוספה MPSolver.SetHint() ל-Python, Java ו-C# (נתמך על ידי SCIP ו-Gurobi).
  • נוספו MPSolver.SetNumThreads() ל-Python, ל-Java ול-C# (נתמך על ידי CBC, Gurobi ו-SCIP).
  • נכתב מחדש תמיכה עבור SCIP 6.0.1.

מסמכי עזר

  • הוספנו מדריכי עזר המבוססים על doxygen ו-pdoc3 לכל השפות ולכל הכלים (אלגוריתמים, ניתוב, גרף, לינארי_סולבר ו-CP-SAT). עיינו במדריכים של OR-Tools.
  • התיעוד מלא עבור C++ (כל המוצרים) ו-CP-SAT (C++ , Python ו-Java).
  • אנחנו בתהליך של ייצוא כל מסמכי התיעוד של C++ ל-Python ול-Java.
  • אין מספיק מסמכי תיעוד של .NET, ואין לנו פתרון בעתיד הקרוב כדי לשפר זאת. שמרנו אותו כי הוא עדיין מציג את ה-API הזמין.

מאי 2019

הודעה על השקת גרסה 7.1 של OR-Tools

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

שינויים ביחסי התלות הנדרשים

גרסה 7.1 של OR-Tools כוללת את יחסי התלות החדשים והמעודכנים הבאים:

  • glog v0.3.5 עודכן ל-v0.4.0
  • protobuf v3.6.1 עודכן ל-v3.7.1
  • Cbc 2.9.9 עודכן ל-2.10.1
  • גרסה 0.59.10 של Cgl עודכנה ל-0.60.1
  • גרסה 1.16.11 של Clp עודכנה ל-1.77.1
  • 0.107.9 של Osi עודכן ל-0.108.1
  • CoinUtils בגרסה 2.10.14 עודכנה ל-2.11.1

שינויים ב-CP-SAT API

בקטעים הבאים מתוארים השינויים ב-CP-SAT API בגרסה 7.1 של OR-Tools.

שימוש בדומיין ליצירת משתנים

הדוגמאות הבאות מראות איך ליצור משתנה מסוג מספר שלם עם דומיינים לא רציפים. הפעולה הזו מחליפה את השיטה שהוסרה NewEnumeratedIntVar(). כאן, המשתנה x יכול להיות כל אחד מ-1, 3, 4 או 6:

Python

model.NewIntVarFromDomain(cp_model.Domain.FromValues([1, 3, 4, 6]), 'x')

C++

model.NewIntVar(Domain::FromValues({1, 3, 4, 6}));

Java

model.newIntVarFromDomain(Domain.fromValues(new long[] {1, 3, 4, 6}), "x");

C#

model.NewIntVarFromDomain(Domain.FromValues(new long[] {1, 3, 4, 6}), "x");

ניתן גם ליצור משתנים באמצעות רשימת מרווחים. בדוגמה הבאה, המשתנה x מוגבל ל-1, 2, 4, 5 או 6:

Python

model.NewIntVarFromDomain(cp_model.Domain.FromIntervals([[1, 2], [4, 6]]), 'x')

C++

model.NewIntVar(Domain::FromIntervals({ {1, 2}, {4, 6} }));

Java

model.newIntVarFromDomain(Domain.fromIntervals(new long[][] { {1, 2}, {4, 6} }), "x");

C#

model.NewIntVarFromDomain(Domain.FromIntervals(new long[][] { new long[] {1, 2}, new long[] {4, 6} }), "x");

שימוש בדומיין בביטוי לינארי

הדוגמאות הבאות מראות איך להגביל ביטוי לינארי בדומיין לא רציף. כאן, הביטוי הלינארי לינארי מ-Google expr מוגדר ב-5, ב-6, ב-8, ב-9 וב-10:

Python

model.AddLinearExpressionInDomain(linear_expr, cp_model.Domain.FromIntervals([(5, 6), (8, 10)]))

C++

model.AddLinearConstraint(linear_expr, Domain::FromIntervals({ {5, 6}, {8, 10} }))

Java

model.addLinearExpressionInDomain(linear_expr, Domain.fromIntervals(new long[][] { {5, 6}, {8, 10} }))

.Net

model.AddLinearExpressionInDomain(linear_expr, Domain.FromIntervals(new long[][] {new long[] {5, 6}, new long[] {8, 10} }));

שימוש בכלים מסייעים לביטויים ליניאריים

הדוגמאות הבאות מראות איך להשתמש בשיטות מסייעות כדי ליצור סכומים ומוצרים סקלריים. הנה דוגמאות שבהן אנחנו רוצים את x + y == 20 ואת 4 * x + 2 * y = 56:\

Python

model.Add(x + y == 20)
model.Add(4 * x + 2 * y == 56)

C++

cp_model.AddEquality(LinearExpr::Sum({x, y}), 20);
cp_model.AddEquality(LinearExpr::ScalProd({x, y}, {4, 2}), 56);

Java

model.addEquality(LinearExpr.sum(new IntVar[] {x, y}), 20);
model.addEquality(LinearExpr.scalProd(new IntVar[] {x, y}, new long[] {4, 2}), 56);

.Net

model.Add(x + y == 20);
model.Add(4 * x + 2 * y == 56);

מרץ 2019

הודעה על השקת גרסה 7.0 של OR-Tools

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

שינויים בפלטפורמות הנתמכות

גרסה 7.0 OR-Tools כבר לא תומכת בפלטפורמות הבאות:

  • חזותי ב-C++ 2015
  • Ubuntu 14.04
  • Python 3.4 ב-Linux

אם אתם משתמשים באחת מהפלטפורמות האלה, עדיין תוכלו להתקין את OR-Tools v6.10.

שינויים ביחסי התלות הנדרשים

גרסה 7.0 של OR-Tools כוללת את יחסי התלות החדשים והמעודכנים הבאים:

בקטעים הבאים מתוארים התכונות והשיפורים החדשים בגרסה 7.0 OR-Tools.

מנהל אינדקס חדש לתוכניות ניתוב

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

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

הכללה/ייבוא של RoutingIndexManager

ב-OR-Tools 7.0, תוכניות ניתוב ב-C++ וב-Java חייבות לכלול או לייבא את RoutingIndexManager, כפי שמוצג בדוגמאות הבאות:

C++

#include "ortools/constraint_solver/routing_index_manager.h"

Java

import com.google.ortools.constraintsolver.RoutingIndexManager;

אין שינוי בייבוא של Python ו-C#.

הצהרה על RoutingIndexManager

בגרסה 7.0 של OR-Tools, תוכנות הניתוב צריכות להצהיר על RoutingIndexManager וליצור את מודל הניתוב, כפי שמוצג בדוגמאות הבאות:

Python

manager = pywrapcp.RoutingIndexManager(num_locations, num_vehicles, depot)
routing = pywrapcp.RoutingModel(manager)

C++

RoutingIndexManager manager(num_locations, num_vehicles, depot);
RoutingModel routing(manager);

Java

RoutingIndexManager manager = new RoutingIndexManager(numLocations, numVehicles, depot);
RoutingModel routing = new RoutingModel(manager);

.Net

RoutingIndexManager manager = new RoutingIndexManager(numLocations, numVehicles, depot);
RoutingModel routing = new RoutingModel(manager);

הארגומנטים של RoutingIndexManager הם:

  • מספר המיקומים
  • מספר כלי הרכב
  • אינדקס התחנה (מיקום ההתחלה והסיום של כל כלי הרכב)

התקשרות חזרה

בגרסה 7.0 של OR-Tools, צריך להשתמש ב-RoutingIndexManager כדי ליצור קריאות חוזרות (callback), כמו קריאה חוזרת מרחוק, שאותה מעבירים לפותר. בדוגמאות הבאות מוסבר איך ליצור קריאה חוזרת (callback) מרחוק.

Python

    def distance_callback(from_index, to_index):
        """Returns the distance between the two nodes."""
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data["distance_matrix"][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

C++

  const int transit_callback_index = routing.RegisterTransitCallback(
      [&data, &manager](const int64_t from_index,
                        const int64_t to_index) -> int64_t {
        // Convert from routing variable Index to distance matrix NodeIndex.
        const int from_node = manager.IndexToNode(from_index).value();
        const int to_node = manager.IndexToNode(to_index).value();
        return data.distance_matrix[from_node][to_node];
      });
  routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);

Java

    final int transitCallbackIndex =
        routing.registerTransitCallback((long fromIndex, long toIndex) -> {
          // Convert from routing variable Index to user NodeIndex.
          int fromNode = manager.indexToNode(fromIndex);
          int toNode = manager.indexToNode(toIndex);
          return data.distanceMatrix[fromNode][toNode];
        });
    routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

.Net

        int transitCallbackIndex = routing.RegisterTransitCallback((long fromIndex, long toIndex) =>
                                                                   {
                                                                       // Convert from routing variable Index to
                                                                       // distance matrix NodeIndex.
                                                                       var fromNode = manager.IndexToNode(fromIndex);
                                                                       var toNode = manager.IndexToNode(toIndex);
                                                                       return data.DistanceMatrix[fromNode, toNode];
                                                                   });
        routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

השיטה IndexToNode ממירה את אינדקסי המיקום הפנימיים שבהם משתמש הפותר לאינדקסים הרגילים של מטריצת המרחק.

במקום להעביר את הקריאה החוזרת ישירות לפותר, כמו בגרסאות קודמות, בגרסה 7.0 קודם יוצרים transit&nbsp;callback&nbsp;index, הפניה לקריאה החוזרת (callback) ומעבירים אותה לפותר (במקרה הזה עד SetArcCostEvaluatorOfAllVehicles).

מאפיינים

הדוגמאות הבאות מראות איך ליצור מאפיין לביקוש ולקיבולת כדי לפתור את הבעיה של ניתוב כלי רכב עם קיבולת (CVR).

Python

    def demand_callback(from_index):
        """Returns the demand of the node."""
        # Convert from routing variable Index to demands NodeIndex.
        from_node = manager.IndexToNode(from_index)
        return data["demands"][from_node]

    demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
    routing.AddDimensionWithVehicleCapacity(
        demand_callback_index,
        0,  # null capacity slack
        data["vehicle_capacities"],  # vehicle maximum capacities
        True,  # start cumul to zero
        "Capacity",
    )

C++

  const int demand_callback_index = routing.RegisterUnaryTransitCallback(
      [&data, &manager](const int64_t from_index) -> int64_t {
        // Convert from routing variable Index to demand NodeIndex.
        const int from_node = manager.IndexToNode(from_index).value();
        return data.demands[from_node];
      });
  routing.AddDimensionWithVehicleCapacity(
      demand_callback_index,    // transit callback index
      int64_t{0},               // null capacity slack
      data.vehicle_capacities,  // vehicle maximum capacities
      true,                     // start cumul to zero
      "Capacity");

Java

    final int demandCallbackIndex = routing.registerUnaryTransitCallback((long fromIndex) -> {
      // Convert from routing variable Index to user NodeIndex.
      int fromNode = manager.indexToNode(fromIndex);
      return data.demands[fromNode];
    });
    routing.addDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack
        data.vehicleCapacities, // vehicle maximum capacities
        true, // start cumul to zero
        "Capacity");

.Net

        int demandCallbackIndex = routing.RegisterUnaryTransitCallback((long fromIndex) =>
                                                                       {
                                                                           // Convert from routing variable Index to
                                                                           // demand NodeIndex.
                                                                           var fromNode =
                                                                               manager.IndexToNode(fromIndex);
                                                                           return data.Demands[fromNode];
                                                                       });
        routing.AddDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack
                                                data.VehicleCapacities, // vehicle maximum capacities
                                                true,                   // start cumul to zero
                                                "Capacity");

פתרונות הדפסה

בגרסה 7.0 של OR-Tools, צריך להשתמש ב-RoutingIndexManager כדי להציג את מסלולי הרכב בפתרון. בדוגמאות הבאות מוסבר איך להדפיס פתרונות בכל השפות הנתמכות.

Python

def print_solution(manager, routing, solution):
    """Prints solution on console."""
    print(f"Objective: {solution.ObjectiveValue()}")
    index = routing.Start(0)
    plan_output = "Route for vehicle 0:\n"
    route_distance = 0
    while not routing.IsEnd(index):
        plan_output += f" {manager.IndexToNode(index)} ->"
        previous_index = index
        index = solution.Value(routing.NextVar(index))
        route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
    plan_output += f" {manager.IndexToNode(index)}\n"
    plan_output += f"Distance of the route: {route_distance}m\n"
    print(plan_output)

C++

//! @brief Print the solution
//! @param[in] manager Index manager used.
//! @param[in] routing Routing solver used.
//! @param[in] solution Solution found by the solver.
void PrintSolution(const RoutingIndexManager& manager,
                   const RoutingModel& routing, const Assignment& solution) {
  LOG(INFO) << "Objective: " << solution.ObjectiveValue();
  // Inspect solution.
  int64_t index = routing.Start(0);
  LOG(INFO) << "Route for Vehicle 0:";
  int64_t distance{0};
  std::stringstream route;
  while (!routing.IsEnd(index)) {
    route << manager.IndexToNode(index).value() << " -> ";
    const int64_t previous_index = index;
    index = solution.Value(routing.NextVar(index));
    distance += routing.GetArcCostForVehicle(previous_index, index, int64_t{0});
  }
  LOG(INFO) << route.str() << manager.IndexToNode(index).value();
  LOG(INFO) << "Distance of the route: " << distance << "m";
  LOG(INFO) << "";
  LOG(INFO) << "Advanced usage:";
  LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
}

Java

  /// @brief Print the solution.
  static void printSolution(
      DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) {
    // Solution cost.
    logger.info("Objective : " + solution.objectiveValue());
    // Inspect solution.
    logger.info("Route for Vehicle 0:");
    long routeDistance = 0;
    String route = "";
    long index = routing.start(0);
    while (!routing.isEnd(index)) {
      route += manager.indexToNode(index) + " -> ";
      long previousIndex = index;
      index = solution.value(routing.nextVar(index));
      routeDistance += routing.getArcCostForVehicle(previousIndex, index, 0);
    }
    route += manager.indexToNode(routing.end(0));
    logger.info(route);
    logger.info("Distance of the route: " + routeDistance + "m");
  }

.Net

    /// <summary>
    ///   Print the solution.
    /// </summary>
    static void PrintSolution(in RoutingModel routing, in RoutingIndexManager manager, in Assignment solution)
    {
        Console.WriteLine("Objective: {0}", solution.ObjectiveValue());
        // Inspect solution.
        Console.WriteLine("Route for Vehicle 0:");
        long routeDistance = 0;
        var index = routing.Start(0);
        while (routing.IsEnd(index) == false)
        {
            Console.Write("{0} -> ", manager.IndexToNode((int)index));
            var previousIndex = index;
            index = solution.Value(routing.NextVar(index));
            routeDistance += routing.GetArcCostForVehicle(previousIndex, index, 0);
        }
        Console.WriteLine("{0}", manager.IndexToNode((int)index));
        Console.WriteLine("Distance of the route: {0}m", routeDistance);
    }

תמיכה במודעות VRP עם איסוף ומשלוחים

גרסה 7.0 של OR-Tools מספקת תמיכה בפתרון בעיות שקשורות לניתוב רכבים (VRP) באסופיות ובמשלוחים, שבמסגרתה המטרה היא למצוא את המסלולים הקצרים ביותר לצי כלי רכב שאוספים ומעבירים פריטים במיקומים שונים. הגדרת הבעיה דומה להגדרת VRP רגילה, אבל בנוסף לכך אתם מציינים צמד של (i, j) מיקומים לכל פריט, כאשר i הוא מיקום האיסוף ו-j הוא נקודת ההורדה. פתרון הניתוב מחזיר מסלולי רכב כך שלכל זוג (i, j), i ו-j נמצאים באותו מסלול, והרכב מבקר ב-i לפני j.

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

תמיכה בפונקציות lambda

גרסה 7.0 OR-Tools כוללת עכשיו תמיכה בפונקציות lambda ב-C# וב-Java (בנוסף ל-C++ ול-Python, שכבר נתמכות). הפונקציות של Lambda מספקות דרך נוחה להגדיר קריאות חוזרות (callback) בתוכניות ניתוב. עם זאת, תוכלו להגדיר קריאות חוזרות באמצעות פונקציות סטנדרטיות, אם לדעתכם הקוד קריא יותר.

הדוגמאות C# ו-Java לקריאה חוזרת (callback) שלמעלה ממחישות איך להגדיר קריאות חוזרות באמצעות פונקציות lambda.

נובמבר 2018

הודעה על השקת גרסה 6.10

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

בחלקים הבאים מתוארים התכונות והשיפורים החדשים בגרסה 6.10.

פקודות פשוטות יותר ליצירה ולהפעלה של תוכניות

בגרסה 6.10 אפשר ליצור ולהפעיל תוכנות באמצעות הזנת פקודות כמו: 

make run SOURCE=relative/path/to/program.cc
כאשר <var>relative/path/to</var> הוא הנתיב לספרייה שמכילה את התוכנה.

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

make build SOURCE=relative/path/to/program.cc
הוראות ספציפיות להרצת תוכנות לפי שפה זמינות במאמר תחילת העבודה עם OR-Tools.

תמיכה ב-SCIP 6.0.0

OR-Tools מספק כעת תמיכה ב-SCIP 6.0.0.

קבצים בינאריים

הפצות בינאריות נבנו באמצעות Java JDK 8 (JDK 7 עבור Ubuntu 14.04).

פתרון בעיות CP-SAT

עדכון ה-API

  • הוספת API של C++ CP-SAT CpModelBuilder.

דוגמאות

חלק מהדוגמאות הועברו.

  • העברת דוגמאות של קהילות אל examples/contrib.
  • כדאי להעביר כמה דוגמאות אל ortools/<var>component</var>/samples (למשל ortools/linear_solver/samples/simple_program.java)

ספטמבר 2018

הכרזה על גרסה 6.9

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

יחסי התלות שעודכנו

  • Protobuf 3.5.1 -> 3.6.1.
  • SCIP 4.0 -> 6.0.

פתרון בעיות CP-SAT

  • שינויי תוכנה ב-API – הפרטים המלאים מופיעים כאן:
  • שינוי השם של SolveWithSolutionObserver ל-SolveWithSolutionCallback ב-Python.

  • שינוי השם של NewSolution ל-OnSolutionCallback בכיתה CpSolverSolutionCallback ב-Python. בדוגמה הבאה מוצגת הדרך החדשה ליצור קריאה חוזרת (callback) של פתרון ב-Python. 

    class MySolutionCallback(cp_model.CpSolverSolutionCallback):
def init(self):
cpmodel.CpSolverSolutionCallback.init(self)
self._solution_count = 0
    


    def OnSolutionCallback(self):
print('Solution {}, time = {}s, objective = {}, makespan = {}'.format(
  self.solution_count,
  self.WallTime(),
  self.ObjectiveValue(),
  self.Value(makespan)))
self.solution_count += 1

  • חשיפה של StopSearch בקריאה חוזרת (callback) של פתרון ב-Python, Java ו-C#. תיעוד זמין כאן.

  • חשיפה של ModelStats ו-CpSolverResponseStats ב-Python, Java ו-C#.

  • שיפור התיעוד של docstring ב-Python. תיעוד זמין כאן.

  • עדכונים בהטמעת Java של ממשק הפותר וספר המתכונים.

  • הטמעת מודול.

  • שינוי היישום של מאגר: הוספת API עם ערך בוליאני כדי לציין אירועים אופציונליים של ניקוז/מילוי.

פותר לינארי

  • חשיפה של InterruptSolve ב-Java וב-C#.

פתרון בעיות CP

  • חשיפה של מנהל אחד (SolutionCollector) ב-C#.

Python

  • הוספת תמיכה ב-Python 3.7.
  • כשמבצעים הידור מהמקור: עדיף python3 על פני python2 בזיהוי python.

‎.NET

  • צריך להשלים את השכתוב של שכבת ה- .NET.
  • יש לספק חבילת Google.OrTools NetStandard 2.0 Nuget שתואמת למזהה זמן ריצה win-x64, linux-x64 ו-osx-x64.
  • יש לספק חבילת Nuget בנפח Google.OrTools.FSharp.
  • צריך להוסיף קובץ פרויקט לכל הדוגמאות של .NET
  • מעדכנים את כל הדוגמאות של סקריפט F# (.fsx) לפרויקט F# רגיל (.fs).
  • אפשר להוסיף כאן תיעוד על יצירת גרסת build של חבילת NET.

פלאציץ

  • הוספת תמיכה בקבוצות ב-flatzinc (באמצעות nosets.mzn).

תכנים שהוספת

  • הוספת תמיכה ב-Biter. תודה ל-Kevin Mader.
  • הגדרת DecisionVisitor כסוג מנהל בקישורים של Java. תודה ל-Jeremy Apthorp.

יולי 2018

הכרזה על גרסה 6.8

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

הודעה על פתרון בעיות בתוכנית CP-SAT

CP-SAT Solr הוא פתרון חדש לתכנות אילוצים. הפותר CP-SAT מהיר יותר מהפותר המקורי של ה-CP, ועדיף להשתמש בו במקרה של בעיות CP.

כדי לראות דוגמאות שמשתמשות בפותר הבעיות CP-SAT, חפשו בספרייה examples ב-GitHub קבצים ששמם כולל את _sat.

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

אפשרויות חדשות לפותר הבעיות של CP-SAT

אלה האפשרויות החדשות לפותר הבעיות של CP-SAT בגרסה הזו:

  • חיפוש מקומי מקומי (LNS): אפשר להשתמש באפשרות SatParameters.use_lns כדי להפעיל את LNS.
  • חיפוש מקביל: משתמשים באפשרות SatParameters.num_search_workers כדי להפעיל מספר שרשורים במהלך חיפוש. לכל שרשור יכולים להיות פרמטרים שונים וזרעים אקראיים שונים. כך אפשר למקסם את הגיוון, ואת הסבירות למצוא פתרונות לפחות ב-thread אחד.

שיפורי ביצועים לפותרים

ערכנו שיפורי ביצועים בפותרי הבעיות CP-SAT ו-Glop.

מרץ 2018

הכרזה על גרסה 6.7

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

עדכון של יחסי התלות הנדרשים

  • Protobuf 3.5.0 -> 3.5.1.

שונות

  • ארגון מחדש של הבסיס כדי להכין שילוב של abseil-cpp.
  • שימוש בשירותי אינטגרציה רציפה (CI) של Travis CI ושל Appveyor.

SAT

  • שיפור ביצועים.
  • משפר את Python API.
  • מוסיפים C# API, נקרא גם CpSolver.cs (ניסיוני).

גלופ

  • ארגון הקוד מחדש של הקוד.
  • שיפור ביצועים.

תמיכה ב-CMake (ניסיוני)

  • הוספת תמיכה ב-C++ OR-Tools CMake.
  • להיות מסוגלים לבנות כלי OR-כלים כפרויקט CMake עצמאי.
  • להיות מסוגלת לשלב כלי OR בפרויקט קיים ב-CMake.
  • מוסיפים build מבוסס CMake של Python OR-Tools.
  • יוצרים חבילת Python (גלגל) באמצעות CMake.

תכנים שהוספת

  • תיקון הגדרה מחדש של minsock2.h ב-Windows. תודה ל-Florent Tollin de Rivarol.
  • הוספת תמיכה ב-F# (ניסיוני). תודה למתיו מור. הערה: האפשרות הזו זמינה רק בכלי ליצירת קבצים ב-Makefile.
  • הוספת תמיכה סטנדרטית עם הסיומת .NET (ניסיוני). תודה לזיאד אל מלכי. הערה: האפשרות הזו זמינה רק בכלי ליצירת קבצים ב-Makefile.

נובמבר 2017

הכרזה על גרסה 6.6

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

עדכונים של יחסי התלות הנדרשים

  • Protobuf ל-3.3.0 -> 3.5.0.
  • gflags ל-2.2.0 -> 2.2.1.
  • CBC 2.9.8 -> 2.9.9.
  • מוסיפים את מודול Python שש (1.10) לפי התלות הנדרשת ב-Python.

תיקוני באגים

  • שליפת בקשה מס' 494 ארגון מחדש של השם. להוסיף תגובות ל-IntelliSense בחלק מהעורכים. תודה למתיו מור.
  • שליפת בקשה מס' 516 לקובץ בינארי עצמאי של F#. תודה למתיו מור.
  • משפרים את הדיוק ב-Glop.

פתרון SAT

  • שיפור פותר SAT פנימי, תיקון באגים שונים.
  • מוסיפים אילוץ VRP לפותר SAT, שמקושר לפותר LP.
  • משנים את בודק הפתרונות בפותר ה-SAT כדי לקחת פרמטר CpSolverResponse בתור פרמטר.
  • שיפור השימוש ב-Glop ב-SAT Solver.
  • מהירות חיבור SAT-LP.
  • מוסיפים אילוץ של מאגר מים לפורמט protobuf של SAT cp_model.

SAT/Python

דוגמאות

  • משכתבים את rcpsp_parser כדי להשתמש בפורמט ProtoBuf כדי לאחסן את הבעיה.
  • שיפור מנתח ה-RCPSP.

אוקטובר 2017

הכרזה על גרסה 6.5

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

שינוי בפלטפורמות

  • מודול pypi py3-ortools מוזג עם מודול Ortools. עכשיו יש רק מודול אחד: 'ortools'.
  • הפורמט הראשי למודולים האלה של Python הוא עכשיו קובצי גלגל. כדי להתקין את OR-Tools עבור python מ-pypi, פשוט מריצים את pip install ortools. נדרשת גרסה עדכנית של PIP מותקנת (>= 9.0.1). פעולה זו אמורה למשוך את הגרסה העדכנית ביותר (גרסה 6.5).

הבאג תוקן

קובץ המאגר של protobuf נוצר עכשיו באופן תקין עם מחלקות מקומפלות.

דוגמאות חדשות

  • דוגמאות נוספות של F# נתרמו לספריית הדוגמאות/fsharp. (תודה שוב למתיו מור).
  • נוספו גם דוגמאות של Java MIP (תודה דריאן).

ספטמבר 2017

הכרזה על גרסה 6.4

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

שינוי בפלטפורמות

  • מודולי Pypi בפלטפורמות Linux מסופקים כקובצי גלגל באמצעות התג Manylinux1. תודה ל-Federico Ficarelli. בעקבות השינוי, החזרנו את המודולים לכל גרסה בגרסת לינוקס שהושקו בגרסת יולי 2017.

תכונות חדשות

  • שיטה משופרת לשינוי קנה מידה שנעשה בה שימוש ב-GLOP.
  • תיקון גלישת המעריכים בספריית הניתוב C#. תודה ל-DevNamedZed.
  • שיפור הביצועים של פשיטת פלגזינק לדגמים גדולים.
  • השתמש ב-SAT המגובה עבור Flatzinc כברירת מחדל.
  • שיפור הביצועים של הגישה מבוססת הליבה לפותר הבעיות.
  • תיקון באג באלגוריתם ההקצאה הלינארית שנכשל בצורה שגויה.
  • נוספו דוגמאות F# ב-ortools/examples/fsharp.
  • יש להסיר את הסימון של עונשים חיוביים בספריית הניתוב.

אוגוסט 2017

הכרזה על גרסה 6.3

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

קבצים חדשים להורדה

קובצי גלגל Python ל-Linux זמינים עכשיו להורדה בדף הגרסה של OR-Tools, לצד הגרסאות האחרונות של כל ההורדות.

פתרון מיני-זינק

הגרסה הזו מכילה את קוד ה-sat וה-flatzinc הסופי שנשלח עבור אתגר Minizinc 2017.

יולי 2017

הכרזה על גרסה 6.2

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

שינוי בפלטפורמות

  • אנחנו תומכים עכשיו בכמה גרסאות בינאריות של Linux (Ubuntu 14.04, 16.04, 17.04, CentOS 7, Debian 9).
  • מודולי Pypi בפלטפורמות Linux כוללים עכשיו תג שמתאר את ההפצה (ubuntu-14.04, ubuntu-16.04, ubuntu-17.04, centos-7, debian-9).

תכונות חדשות

הוספנו תמיכה ב-Docker לפיתוח ארטיפקטים של Linux. נכנסים לקטע or-tools/tools/docker ובוחנים את Makefile כדי לראות יעדים אפשריים (make archive, make pypi ו-make pypi3).

הפקודות האלה ייצרו ספריית משנה export ויוסיפו אליה פריטי מידע בינאריים (Artifact).

יוני 2017

הכרזה על גרסה 6.1

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

שינוי בפלטפורמות

  • יש תמיכה ב-Visual Studio 2017; אין יותר תמיכה ב-Visual Studio 2013.
  • אנחנו תומכים ב-macOS בגרסאות 10.9 ואילך.

תכונות חדשות

הוספנו פורמט Protobuf חדש לפותר הבעיות CP-SAT. ראו ortools/sat/cp_model.proto כדי להגדיר את המודל שלכם, ו-ortools/sat/cp_model_solver.h כדי לפתור את הבעיה.

תיקוני באגים

בעיה מס' 420: תיקנו את המאפיין __version__ החסר במודולים של Python pypi בכל הפלטפורמות.

מאי 2017

הכרזה על גרסה 6.0

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

מבנה ספריות חדש ב-C++

שינינו את מבנה המקור/ההכללה של OR-Tools בעת שימוש ב-C++. המטרה היא לספק מעטפת טובה יותר של קובצי ה-include. יש לו גם את היתרון של התאמת המבנים של ספריית C++ והספרייה של Python.

  • השם של src/ השתנה ל-ortools/.
  • לכל הפקודות #include בקובצי C++ נוספה כעת הקידומת ortools. #include "constraint/constraint_solver.h" נקראת עכשיו #include "ortools/constraint/constraint_solver.h".

תכונות חדשות

  • תמיכה ב-Bazel. עכשיו אפשר לפתח OR-Tools באמצעות bazel, כלי ה-build של Google. הוא פועל ב-Linux וב-Mac OS X. אחרי שמורידים את Bazel גרסה 0.4.5 ואילך, משנים את הספרייה ל-or-tools ויוצרים את הדוגמאות: bazel build examples/cpp/....

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

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

תמיכה ב-SCIP

wrapper של הפותר הלינארי תומך עכשיו ב-SCIP 4.0. עכשיו אתם צריכים לפתח קודם SCIP, ואז לומר לכלים שתשתמשו בו. הוראות מופיעות כאן.

תמיכה ב-GLPK

שינינו גם את הדרך שבה אנחנו משתמשים ב-build עם GLPK. כאן מוסבר איך בוחרים אפשרות.

ניקיונות

  • הסרנו את כל השימוש ב-hash_map וב-hash_set ב-codebase של C++ מאחר שהם הוצאו משימוש. הם הוחלפו ב-unorder_map וב-unorder_set מ-STL.
  • ניקוי קובצי C#, באדיבות מייקל פאוול.

ינואר 2017

הכרזה על גרסה 5.1

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

תכונות חדשות

בתהליך התקנה

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

השתמשנו באלגוריתם כדי לחשב את הגבול התחתון Held-Karp במקרה של בעיות סימטריות באנשי מכירות בנסיעות. כך ניתן לחשב את הגבול העליון של הפער בין העלות של פתרון שעשוי להיות לא אופטימלי לבין העלות של הפתרון האופטימלי.

  • נוספה שיטה חדשה לספריית הניתוב של הרכבים, RoutingModel::SetBreakIntervalsOfVehicle, שמאפשרת להוסיף מרווחי זמן בbreak – פרקי זמן שבהם הרכב לא יכול לבצע משימות (כמו נסיעה או ביקור בצומת). דוגמה לשימוש באפשרות הזו זמינה במאמר cvrptw_with_breaks.cc

תזמון

  • נוספה תמיכה בפורמטים נוספים של נתונים בכלי הניתוח של Project Timing Library.

פותר בעיות שבת

  • האילוץ המצטבר של פותר ה-SAT מקבל עכשיו מרווחים אופציונליים, שנוצרו באמצעות השיטה NewOptionalInterval. לדוגמה: https://github.com/google/or-tools/blob/master/examples/cpp/rcpsp_sat.cc.
  • עכשיו אפשר לפתור את בעיית Max-SAT (בעיית שביעות רצון_מקסימלית על ידי ציון המטרה כסכום משוקלל של ליטרלים). כבר אין צורך ליצור משתנה מסוג מספר שלם ביניים.

שיפורי ביצועים

  • פתרון SAT – ביצועים משופרים של פתרון Sat, במיוחד עבור האילוץ המצטבר.
  • פותר Glop — חוסן מספרי משופר של פותר Glop, שמחזיר עכשיו פתרונות מדויקים עוד יותר לבעיות מספריות קשות.
  • פתרון לפלציץ
  • שיפור משמעותי בביצועים של הקצה העורפי ביום שבת עבור המתרגם המפענח פלאטזינק.
  • פישטנו את ממשק C# Flazinc. דוגמה לממשק החדש: https://github.com/google/or-tools/blob/master/examples/csharp/csfz.cs.

תיקוני באגים

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

נובמבר 2016

הכרזה על גרסה 5.0

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

דוגמאות להרצה

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

ש'

FlatZinc

פותר מגבלות

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

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

ספטמבר 2016

הכרזה על גרסה 4.4

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

ש'

  • Extended Schedule API ודוגמאות ששונו לשימוש בו (weighted_tardiness_sat ו-jobshop_sat).

תרשים

  • נוספו תכונות איטרטור למחלקות של גרף.

הפצת OR-כלים

  • חבילת Nuget נתמכת שוב.

אוגוסט 2016

הכרזה על גרסה 4.3

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

פותר האילוצים

  • הטמענו שיטה NotBetween כדי להגביל משתנה כך שיהיה מחוץ להפסקה נתונה.

תכנון מסלול

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

פתרון לינארי

  • דיווח על סטטוס SCIP תוקן.

ש'

  • הטמעת השיטה SolveWithPresolve כדי לפשט את השימוש במקודד SAT.
  • כלים לחיפוש מקובצים מחדש ב- src/sat/util.h|cc.
  • אילוצי תזמון מיושמים ב-SMT (Lazy Clause Generation): אפשר לעיין ב-jobshop_sat.cc וב-weighted_tardiness_sat.cc.

גלופ

  • ביצועים משופרים על ידי ניצול דלות בשלבי חישוב רבים יותר.

פלאציץ

  • תיקנו באגים שנמצאו על ידי אתגר minizinc.

Lp_data

  • פישוט מתמשך של תבניות באיטרטורים.

הפצת OR-כלים

  • להרכבות C# יש עכשיו שמות חזקים כברירת מחדל.
  • שודרג ל-Protobuf3.0.0.
  • הוספנו סקריפט של Python על מנת לבדוק את יחסי התלות בארכיון OR-Tools.

יולי 2016

הכרזה על גרסה 4.2

השקנו את גרסה 4.2 של כלי ה'או-כלים'. כדי לעדכן את הגרסה, קראו את הקטע המתאים במאמר התקנת OR-Tools.

פותר מגבלות (ניתוב)

  • מעכשיו אפשר להגדיר חיתוך באמצעות עוצמה (cardinality), שהיא המספר המקסימלי של צמתים שיכולים להיות פעילים בתוך ההפרדה הזו. לדוגמה, אם מוסיפים הבחנה עם n צמתים ועוצמה של k, הצמתים של k בין הצמתים יכולים להיות פעילים. לשם כך, אפשר להשתמש בהגדרה החדשה של AddDisjunction.
  • נוספה תמיכה במספר הפסקות לכל צומת. לדוגמה, עכשיו אפשר להוסיף צומת, N1, לסירוגין רבים (D1..Dm). כך גובר הסיכוי להיות פעיל במסגרת כל אחד מהם. אלגוריתם לחיפוש ניתוב מהיר יותר לבעיות שקשורות לחלונות זמן מופרדים.
  • נוספו פרמטרים של פתרון אילוצים לפרמטרים של מודל ניתוב ו-log_search לניתוב פרמטרים של חיפוש.
  • האלגוריתם של החיפוש המקומי מהיר יותר בפתרון בעיות הקשורות לחלונות זמן נפרדים. לפרטים נוספים, ראו cvrp_disjoint_tw.cc דוגמה.

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

  • שימוש באלגוריתם סימפלקס מהיר יותר.

הפצת OR-כלים

  • ארכיון אחד לכל פלטפורמה, במקום ארכיונים נפרדים לכל אחד מהסוגים של C++ , Java ו-Net. ארכיונים של Python עדיין מתארחים ב-pypi.
  • ב-pypi, עברנו למודולים של גלגלים (.whl) ב-Mac OS X וב-Windows. הוספנו סכימת מספור מסוג MAJOR.MINOR. המספרים האלה משמשים לשמות הארכיון, הגרסאות ששמורות בספריות משותפות של Mac OS X, מודולים של Python והרכבות NET. הגרסה הראשונה שאנחנו מפרסמים היא עם הסכימה הזו היא v4.2

יוני 2016

הכרזה על גרסה v2016-06

השקנו גרסה v2016-06 של OR-Tools. כדי לעדכן את הגרסה, קראו את הקטע המתאים במאמר התקנת OR-Tools.

פותר מגבלות

  • רוב המופעים של הקריאות חוזרות (src/base/callback.h) הוסרו מהספרייה CP.
  • נוסף NotMemberCt (המשתנה לא יכול להשתייך לקבוצת מרווחים).

ספריית ניתוב

  • שינוי לא תואם: כדי לציין את הקיבולת של כלי רכב ב-AddDimensionWithVehicleCapacity, עכשיו צריך להעביר מערך (וקטור ב-c++ ) במקום קריאה חוזרת (callback).

GLOP

  • שינוי הייצוג הפנימי של מטריצה דלילה.
  • שיפורי ביצועים.

תרשים

  • משכתבים את האלגוריתמים של Dijkstra ו-Bellman-Ford כדי להחליף קריאות חוזרות (callback) באמצעות std::function (C++ ).
  • שינוי ה-API של הטמעות תרשימים שונות כשחוזרים על קשתות וצמתים.

ש'

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

בופ

  • להוסיף שכונות חדשות.

דוגמאות

  • c++: הסרה של Filelinereader בדוגמאות.
  • נתונים: הוספת בעיות תזמון של מכונה יחידה.

מאמרי עזרה

אפריל 2016

הכרזה על גרסה v2016-04

השקנו את גרסה 'או-כלים' גרסה 2016-04. כדי לעדכן את הגרסה, קראו את הקטע המתאים במאמר התקנת OR-Tools.

יחסי התלות שעודכנו

דצמבר 2015

הכרזה על גרסה v2015-12

השקנו את הגרסה 'או-כלים' גרסה 2015-12. כדי לעדכן את הגרסה, קראו את הקטע המתאים במאמר התקנת OR-Tools.

פותר מגבלות

  • אירעה הפרה של תאימות ב'חיפוש שכונות גדולות' (LCP) בפותר הבעיות של CP (ניתן לעיין ב-examples/cpp/ls_api.cc, ב-examples/python/pyls_api.py, ב-examples/csharp/csls_api.cs וב-examples/com/google/ortools/sample/LsApi.java כדי לראות את ה-API החדש).
  • שינינו את האריזה של Python. תמיכה בקבלת החלטות בהתאמה אישית בכלי לפתרון בעיות CP (אפשר לעיין ב-examples/test/test_cp_api.py כדי לראות איך ה-API פועל).
  • שיפורים שונים ותיקוני באגים.

ספטמבר 2015

הודעה על הגרסה הראשונה ב-github.

מעכשיו, הקבצים יישמרו שם.

פלאציץ

  • הוספנו ארכיונים בינאריים למתרגם Flatzinc (ראו www.minizinc.org).
  • כולל מספר תיקונים לגרסה שבה נעשה שימוש באתגר.