कॉम्बिनेटरल ऑप्टिमाइज़ेशन से जुड़ी सबसे जानी-पहचानी समस्याओं में से एक है, असाइनमेंट में समस्या. उदाहरण के लिए: मान लीजिए कि वर्कर के एक ग्रुप को टास्क का एक सेट पूरा करना है और हर वर्कर और टास्क के लिए, वर्कर को यह टास्क असाइन करने की एक लागत आती है. समस्या यह है कि हर वर्कर को ज़्यादा से ज़्यादा एक टास्क असाइन किया जाए. इसमें कोई भी दो वर्कर एक ही काम को न करते हुए कुल लागत को कम करता है.
नीचे दिए गए ग्राफ़ से इस समस्या को विज़ुअलाइज़ किया जा सकता है. इसमें चार कर्मचारी और चार टास्क हैं. किनारे, कर्मचारियों को काम असाइन करने के सभी संभावित तरीकों को दिखाते हैं. किनारों पर दिख रहे लेबल में, कर्मचारियों को काम देने में लगने वाला खर्च शामिल होता है.
असाइनमेंट, किनारों के सबसेट से जुड़ा होता है. इसमें हर वर्कर के एक से ज़्यादा किनारे की शुरुआत होती है. साथ ही, किसी भी दो वर्कर के पास ऐसे किनारे नहीं होते हैं जो एक ही टास्क पर ले जाते हैं. एक असाइनमेंट नीचे दिया गया है.
असाइनमेंट की कुल लागत 70 + 55 + 95 + 45 = 265 है.
अगले सेक्शन में बताया गया है कि एमआईपी सॉल्वर और सीपी-एसएटी सॉल्वर, दोनों का इस्तेमाल करके असाइनमेंट का सवाल कैसे हल किया जाता है.
असाइनमेंट से जुड़े सवालों को हल करने के लिए अन्य टूल
OR-टूल, असाइनमेंट से जुड़ी समस्याओं को हल करने के लिए कुछ दूसरे टूल भी देता है. ये टूल, MIP या CP सॉल्वर से ज़्यादा तेज़ी से काम कर सकते हैं:
हालांकि, इन टूल से असाइनमेंट से जुड़े सिर्फ़ सामान्य सवालों को हल किया जा सकता है. इसलिए, ऐसे सामान्य सॉल्वर जो कई तरह की समस्याओं को हल कर सकते हैं (और ज़्यादातर ऐप्लिकेशन के लिए तेज़ी से काम करते हैं), हम MIP और CP-SAT सॉल्वर का सुझाव देते हैं.