Resource allocation in classification task with feature-based sample-based constraints

הרקע לפרויקט:

הפרויקט עוסק בבעית סיווג שמשלבות הקצאת משאבים עם סוגי אילוצים שונים. את הבעיה אנו פותרים בעזרת מודל דו שלבי שמשלב מודל קלסיפיקציה ומודל חקר ביצועים לפתרון של הקצאת המשאבים עם אילוצים משני סוגים. הסוג הראשון זה אילוץ על בסיס תכונה (feature in the dataset) והוא מתייחס לאילוץ על כמות הרשומות שיכולות להיות מסווגות לכל קלאס לפי ערך של תכונה מסויימת. האילוץ השני הוא על בסיס רשומות, והוא מתייחס לאילוץ על רשומות שצריכות להיות מסווגות ביחד לאותו הקלס. האילוצים הנידונים ובעיית חקר הביצועים היא חדשנית וישנם שני מידולים מוצעים לפתרון המבוססים על הרחבה של בעיית התרמיל.

מטרת הפרויקט:

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

תכולת הפרויקט:

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

קורסי קדם:

חקר ביצועים, כריית מידע/למידת מכונה, פייתון

דרישות נוספות:

מקורות:

1. Lin Chen and Guochuan Zhang. Packing groups of items into multiple knapsacks. ACM Transactions on Algorithms (TALG), 14(4):1–24, 2018
2. Geir Dahl and Nj˚al Foldnes. Lp based heuristics for the multiple knapsack problem with assignment restrictions. Annals of Operations Research, 146:91–104, 2006.
3. Milind Dawande, Jayant Kalagnanam, Pinar Keskinocak, F Sibel Salman, and Ramamoorthi Ravi. Approximation algorithms for the multiple knapsack problem with assignment restrictions. Journal of combinatorial optimization, 4:171–186, 2000.
4. Simona Mancini, Michele Ciavotta, and Carlo Meloni. The multiple multidimensional knapsack with family-split penalties. European Journal of Operational Research, 289(3):987–998, 2021.
5. Skackauskas, Jonas, and Tatiana Kalganova. "Dynamic Multidimensional Knapsack Problem benchmark datasets." Systems and Soft Computing 4 (2022): 200041.