CP-SAT और Python के साथ constraint programming का व्यावहारिक परिचय

 (pganalyze.com)
1 पॉइंट द्वारा GN⁺ 2024-07-05 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Constraint Programming (CP) डिस्क्रीट optimization समस्याओं को procedural code की बजाय variables, domains और constraints के रूप में model करता है, ताकि solver शर्तों को पूरा करने वाला समाधान खोज सके
  • मॉडल का मूल आधार वे variables हैं जिनके मान खोजने हैं, possible values की range यानी domain, और variables के बीच संबंध सीमित करने वाले constraints; जरूरत होने पर objective function से बेहतर समाधान चुना जा सकता है
  • Alice, Bob, Carol के candy cost sharing उदाहरण में alldifferent, maximum, minimize के जरिए valid solution को अधिक balanced solution में बेहतर बनाने का flow दिखता है
  • व्यावहारिक उदाहरण में Google OR-Tools के open source solver CP-SAT और Python से 4 कर्मचारियों के लिए 7 दिन, 3 shifts और 2 roles वाला साप्ताहिक कार्य-शेड्यूल बनाया जाता है
  • इसी मॉडल में साप्ताहिक 40 घंटे की upper limit, class schedule, साथ काम न कर सकने वाले combinations, weekend duty का समान बंटवारा, छुट्टी अनुरोध, और shifts की संख्या में न्यूनतम अंतर जैसी शर्तें चरणबद्ध तरीके से जोड़ी जा सकती हैं

constraint programming की बुनियादी सोच

  • Constraint Programming (CP) डिस्क्रीट optimization समस्याओं को हल करने के लिए एक declarative paradigm है
  • Imperative programming में परिणाम तक पहुँचने की प्रक्रिया क्रमवार लिखी जाती है, जबकि declarative approach में इच्छित परिणाम की शर्तें लिखी जाती हैं और execution system उस परिणाम को खोजता है
  • वयस्कों की सूची निकालने के उदाहरण में imperative code लोगों की सूची को iterate करके Age >= 18 जाँचता है, जबकि declarative SQL SELECT person_name FROM people WHERE age >= 18; की तरह शर्त को सीधे व्यक्त करता है
  • CP भी इच्छित परिणाम को एक model के रूप में व्यक्त करता है, और इसके मुख्य घटक variables, domains और constraints हैं
    • variable यह बताता है कि क्या खोजना है
    • domain उन values का set है जो variable ले सकता है
    • constraint variables के बीच संबंधों को सीमित करता है

variables, domains, constraints, objective function

  • समाधान वह assignment है जिसमें हर variable अपने domain के भीतर value ले और सभी constraints पूरे हों
  • candy cost उदाहरण में Alice, Bob, Carol के पास अधिकतम 20 डॉलर हैं और वे 50 डॉलर की candy खरीदने के लिए पैसा जोड़ते हैं
    • variable a, b, c प्रत्येक व्यक्ति द्वारा दिया गया amount हैं
    • तीनों variables का domain {0, ..., 20} है
    • a + b + c == 50 से कुल राशि तय होती है
    • a >= b से यह सुनिश्चित होता है कि Alice, Bob से कम न दे
    • c % 5 == 0 से Carol की राशि 5 के multiple तक सीमित होती है
    • तीनों लोग समान राशि न दें, इसके लिए a != b, a != c, b != c रखा जा सकता है
  • कई variables पर फैली शर्तों को global constraints के रूप में व्यक्त किया जा सकता है, और alldifferent(a, b, c) यह सुनिश्चित करता है कि तीनों variables अलग-अलग values लें
  • solver model को input के रूप में लेकर valid solution लौटाता है
    • उदाहरण समाधान a = 19, b = 11, c = 20 सभी constraints को पूरा करता है
    • लेकिन Carol, Bob की लगभग दोगुनी राशि दे रही है, इसलिए अधिक balanced solution हो सकता है
  • objective function constraints को पूरा करने वाले समाधानों में किसी expression को minimize या maximize करता है
    • नया variable x सबसे बड़े contribution के रूप में रखा जाता है और maximum(x, [a, b, c]) का उपयोग होता है
    • minimize: x लगाने पर a = 18, b = 17, c = 15, x = 18 मिलता है
    • सबसे बड़े और सबसे छोटे contribution के बीच का अंतर 9 डॉलर से घटकर 3 डॉलर रह जाता है

CP-SAT और Python से shift schedule model बनाना

  • व्यावहारिक उदाहरण एक छोटी दुकान के साप्ताहिक कार्य-शेड्यूल को बनाने की समस्या है
    • दुकान हर दिन सुबह 8 बजे से शाम 8 बजे तक खुली रहती है
    • एक दिन में Morning, Afternoon, Evening तीन shifts हैं और हर shift 4 घंटे की है
    • roles दो हैं: Cashier और Restocker
    • कर्मचारी चार हैं: Phil, Emma, David, Rebecca
  • CP-SAT Google OR-Tools में शामिल एक open source CP solver है
  • खाली model ortools.sat.python के cp_model.CpModel() से बनाया जाता है
  • प्रत्येक कर्मचारी की eligible roles इस प्रकार हैं
    • Phil: Restocker
    • Emma: Cashier, Restocker
    • David: Cashier, Restocker
    • Rebecca: Cashier
  • schedule को कर्मचारी, role, weekday और shift के संयोजन वाले Boolean variables से व्यक्त किया जाता है
    • schedule["Emma"]["Restocker"]["Monday"]["Evening"] का मतलब है कि Emma सोमवार की Evening shift में Restocker के रूप में काम करती है तो 1, अन्यथा 0
    • model.new_bool_var() ऐसा variable बनाता है जिसका domain {0, 1} होता है

बुनियादी कार्य constraints

  • Cashier हर समय स्लॉट में ठीक एक चाहिए, इसलिए हर weekday और shift के लिए Cashier role का sum 1 होना चाहिए
  • Restocker के लिए एक दिन में केवल एक shift चाहिए, इसलिए हर weekday में Restocker role का कुल sum 1 रखा जाता है
  • पिछली रात की Evening Restocker shift और अगले दिन की Morning Restocker shift लगातार न आएँ, इसके लिए दोनों assignments का sum 1 से अधिक न हो
  • एक कर्मचारी एक ही shift में दो roles साथ नहीं कर सकता, इसलिए कर्मचारी, weekday और shift के अनुसार roles का sum 1 या उससे कम होना चाहिए
  • अयोग्य role assign न हो, इसके लिए उस कर्मचारी द्वारा न किए जा सकने वाले role variables को 0 पर fix कर दिया जाता है
  • एक दिन में अधिकतम 8 घंटे, यानी 2 shifts काम किया जा सकता है
    • अगर Morning और Evening दोनों एक ही दिन assign हों, तो Afternoon में 4 घंटे का idle gap बनता है
    • कर्मचारी और weekday के हिसाब से Morning और Evening assignments का sum 1 या उससे कम रखकर 2 shifts से अधिक काम और बीच का idle gap, दोनों रोके जाते हैं

solver चलाना और शुरुआती परिणाम

  • model हल करने के लिए cp_model.CpSolver() बनाया जाता है और solver.solve(model) कॉल किया जाता है
  • समाधान मिलने के बाद solver.value(...) से schedule variables की values पढ़ी जाती हैं
  • शुरुआती schedule सभी बुनियादी constraints पूरे करता है, लेकिन Rebecca को एक सप्ताह में 14 shifts मिलती हैं
  • overtime से बचने के लिए हर कर्मचारी के साप्ताहिक काम को अधिकतम 40 घंटे, यानी 10 shifts तक सीमित करने वाला constraint जोड़ा जाता है
  • Phil full-time student है, इसलिए वह सप्ताह में ठीक 4 shifts ही काम करता है, और weekday Morning तथा Afternoon में classes के कारण काम नहीं कर सकता
  • Phil और Emma एक ही shift में साथ काम न करें, इसके लिए हर weekday और shift पर दोनों के assignments का sum 1 या उससे कम रखा जाता है
  • सबको नापसंद weekend duty के लिए Saturday और Sunday की कुल 8 shifts चारों कर्मचारियों में 2-2 shifts के रूप में बाँटने का constraint रखा जाता है

समाधान की स्थिति: OPTIMAL, INFEASIBLE, FEASIBLE, UNKNOWN

  • solver model को input लेकर status और solution लौटाता है
  • OPTIMAL का अर्थ है कि इससे बेहतर solution मौजूद नहीं है
    • उदाहरण के लिए x + y >= 5 हो और x + y को minimize करना हो, तो (x, y) = (5, 0) एक optimal solution है
    • (x, y) = (3, 2) का objective value भी वही है, इसलिए वह भी optimal solution हो सकता है
  • INFEASIBLE का अर्थ है कि variables को किसी भी तरह assign करने पर constraints पूरे नहीं हो सकते
    • जैसे x ∈ {0, ..., 10} हो लेकिन x >= 15 माँगा जाए, तो यह असंभव है
  • बड़ी समस्या या जटिल objective function के कारण time limit पर solver रोक दिया जाए, तो दो स्थितियाँ मिल सकती हैं
    • FEASIBLE: constraints पूरे करने वाला solution मिला है, लेकिन optimal है या नहीं यह पता नहीं
    • UNKNOWN: कोई solution नहीं मिला, और यह भी पता नहीं कि solution है या नहीं

छुट्टी अनुरोध और निष्पक्ष वितरण

  • अगर Emma के लिए सोमवार से शुक्रवार तक छुट्टी की शर्त जोड़ दी जाए, तो solver status INFEASIBLE हो जाता है
    • क्योंकि अन्य constraints तोड़े बिना schedule भरना संभव नहीं रहता
  • Emma को केवल सोमवार से बुधवार तक छुट्टी देने की शर्त में schedule बन सकता है
    • Phil अपनी इच्छा के अनुसार ठीक 4 shifts काम करता है
    • Emma 6 shifts, David 10 shifts, और Rebecca 8 shifts लेती हैं
  • Emma, David, Rebecca के बीच shifts की संख्या को और balanced करने के लिए objective function जोड़ा जाता है
    • प्रत्येक कर्मचारी की कुल shifts दिखाने वाला integer variable total_shifts बनाया जाता है
    • model.new_int_var(0, 10, ...) से 0 से 10 तक value लेने वाला integer variable बनाया जाता है
    • Phil part-time है, इसलिए उसे छोड़कर model.add_min_equality(...) और model.add_max_equality(...) से minimum और maximum shifts track की जाती हैं
    • model.minimize(max_shifts - min_shifts) से अधिकतम और न्यूनतम shifts के अंतर को minimize किया जाता है
  • अंतिम परिणाम Phil 4 shifts, Emma 6 shifts, David 9 shifts, Rebecca 9 shifts का होता है
    • Emma को 3 दिन की छुट्टी मिलने के कारण उसकी 6 shifts होती हैं
    • David और Rebecca को समान 9-9 shifts दी जाती हैं

उदाहरण code और अगला विषय

  • यह model दुकान के मालिक और कर्मचारियों, दोनों की आवश्यकताओं को पूरा करने वाला schedule बनाता है
  • उसी CP model में लगातार constraints जोड़ते हुए यह जाँचा जा सकता है कि request संभव है या नहीं, और संभव समाधानों में अधिक fair distribution objective function से खोजा जा सकता है
  • उदाहरण code pganalyze GitHub पर उपलब्ध है
  • अगले लेख का विषय Postgres में index selection के लिए constraint programming का उपयोग है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-07-05
Hacker News टिप्पणियाँ

  • मैंने पहले constraint solver इस्तेमाल किया है, और यह जो कर सकता है वह सचमुच जादू जैसा लगता है। समस्या यह है कि शुरुआती लोगों के लिए सामग्री बहुत कम है
    ज़्यादातर चीज़ें Sudoku solve करने तक सीमित होती हैं — जो इस क्षेत्र का Hello World है — या फिर केवल domain experts के लिए बेहद तकनीकी प्राथमिक research papers होती हैं
    अफ़सोस की बात यह है कि अगर ऐसे tools ज़्यादा accessible हो जाएँ, तो लगता है कि बहुत बड़ी संख्या में समस्याएँ हल की जा सकती हैं। यहाँ accessible से मेरा मतलब यह भी है कि फिर भी programmer की ज़रूरत होगी, और किसी समस्या को constraint DSL में ढालना ऐसा काम नहीं है जो ज़्यादातर लोग अच्छी तरह कर सकें

    • मुझे लगता है कि ऐसे tools पर्याप्त accessible नहीं होने की एक बड़ी वजह यह है कि ज़्यादातर solvers Mixed Integer Programming (MIP) पर आधारित होते हैं, इसलिए domain को mathematical equations के रूप में लिखना पड़ता है। इसके लिए user को domain भी समझना होता है और math भी, तभी constraints सही तरह लिखे जा सकते हैं
      लेकिन solver सिर्फ MIP तक सीमित नहीं हैं। local search आधारित constraint solvers भी होते हैं, और इस तरीके में हर constraint को integer variables के बीच संबंध या equations के रूप में model करना ज़रूरी नहीं होता
      local search solver में constraints को आम तौर पर एक black box की तरह माना जाता है जो बताता है कि कोई candidate solution कितना अच्छा है। इसलिए, जब तक सभी possible solutions आज़माए न जाएँ, optimal solution की guarantee देना कठिन होता है, लेकिन ये अक्सर उचित समय में near-optimal solution ढूँढ लेते हैं
      Timefold Solver ऐसा ही एक local search आधारित solver है। user domain पर annotations लगाता है ताकि solver variables और possible values को समझ सके। इस तरह constraints int की जगह Shift और Employee जैसी चीज़ों को handle करते हैं, और उनके methods तक भी पहुँच सकते हैं
      खुलासा: मैं Timefold Solver में काम करता हूँ
    • बात बिल्कुल सही है। constraint solver की असली syntax या API इतनी सरल होती है कि उसे बहुत जल्दी सीखा जा सकता है। असली समय और विशेषज्ञता जिस चीज़ में लगती है, वह है इस तरह समस्या को model करना, और इस स्तर के वास्तविक size और complexity वाले उदाहरण लगभग न के बराबर मिलते हैं
      मुझे MiniZinc से scheduling problems हल करने का लगभग 5 साल का अनुभव है, लेकिन दुर्भाग्य से वह सारा code private है, इसलिए उसके open source होने की कोई संभावना नहीं है
      मैं containerization, visualization और modeling सहित constraint programming का एक end-to-end उदाहरण बनाना चाहता हूँ, लेकिन ऐसी समस्या ढूँढना जिसमें सचमुच value हो और जिसके लिए usable open source data उपलब्ध हो, यही सबसे बड़ी बाधा है
    • मैं सहमत हूँ कि theory से ज़्यादा मुश्किल reduction है। Dennis Yurichev की "SAT/SMT by Example" (https://smt.st/) इस विषय पर अच्छा resource है, लेकिन काफ़ी intimidating भी है
    • यह बात बिल्कुल सही है कि “ज़्यादातर सामग्री या तो Sudoku solve करने पर होती है या domain experts के लिए research literature होती है।” मैंने rule engine के लिए SAT solver इस्तेमाल करने की कोशिश की थी, लेकिन यह बिल्कुल समझ नहीं आया कि शुरुआत कैसे करूँ
      काफ़ी मेहनत और तर्क-वितर्क के बाद मैं एक basic proof of concept बना पाया, लेकिन उसे उस स्तर तक scale नहीं कर सका जिसकी वास्तव में ज़रूरत थी। toy implementation और उससे ज़्यादा व्यावहारिक चीज़ के बीच बहुत बड़ा फ़ासला था
    • मैंने लंबे समय तक coding की है, लेकिन अब थोड़ा rust हो गया हूँ। पिछले साल मैंने Google के OR-Tools से football team optimizer बनाया था, जिसमें दोस्तों को साथ खेलने देना जैसी selection constraints और टीमों के बीच skill balance जैसी conditions थीं
      LLM ने मुझे काफ़ी जल्दी लगभग सही दिशा में पहुँचा दिया। अभी यह चीज़ों को पूरी तरह सही नहीं कर पाता, लेकिन इतना ज़रूर मदद कर गया कि बाकी हिस्सा मैं खुद पूरा कर सका

  • इन सबका सार यह है कि आपको सीखना होता है कि किसी चीज़ को solver को देने लायक रूप में model कैसे किया जाए। उसके बाद यह समझना होता है कि निकले हुए solution को इंसान के समझने लायक कैसे प्रस्तुत किया जाए
    दुख की बात है कि ज़्यादातर programs data को सिर्फ एक ही representation में रखने की कोशिश करते हैं, और यह सोच उसी के उलट है। अधिकांश मामलों में यह सही तरीका नहीं होता, और algorithms को उस नई representation के हिसाब से मोड़ने के लिए बहुत तरह की पेचीदगियाँ पैदा हो जाती हैं
    यह लेख भी शुरुआत में declarative style को संक्षेप में छूते हुए इसी बात पर आता है। मुझे हमेशा अफ़सोस रहता है कि मेरा code representations के बीच और अधिक बार transform नहीं करता। ऐसा करने से बहुत concise representation मिल सकती है, और concise होने की वजह से performance भी बेहतर हो सकती है — यानी दोहरा फ़ायदा
    बेशक, मुझे पता है कि यह बात आखिरकार बहुत से data pipelines का भी वर्णन करती है। ज़्यादातर समय data transform करने और उसे अलग-अलग compute locations की ओर branch करने में ही जाता है

  • मैंने पहले जो किताब लिखी थी और जिसे अभी फिर से लिख रहा हूँ, उसमें Python से MiniZinc इस्तेमाल करने पर एक छोटा अध्याय है: https://leanpub.com/pythonai/read#constraint-programming-wit...
    MiniZinc एक constraint programming system है। MiniZinc पर एक अच्छा Coursera course भी है

    • क्या उस Coursera course का लिंक है?

  • econometrics पढ़ने के बाद मैंने 2000 के शुरुआती दशक में operations research में master's program के दौरान solvers का बहुत इस्तेमाल किया था। अब मैं Python इस्तेमाल करने वाले web software क्षेत्र में काम करता हूँ, इसलिए इस विषय पर इतना गहरा लेख देखकर अच्छा लगा
    मुझे यह विषय पसंद है, और यह लेख पढ़कर बहुत सी यादें ताज़ा हो गईं। यह बात फिर से महसूस हुई कि constraints को model में बदलना — variables, structures वगैरह — काम का 90% हिस्सा है और वही सबसे कठिन भी है

    • master's के दौरान मैंने GAMS नाम का program इस्तेमाल किया था
      उसकी syntax structure पूरी तरह free-form है
      https://www.gams.com/latest/docs/UG_GAMSPrograms.html#UG_GAM...
    • constraints को model में बदलने में LLM काफ़ी मददगार हो सकते हैं। मैं LLM से constraint model में बदलने वाला एक adapter आज़माना चाहता था
      यह काफ़ी low-hanging fruit जैसा लगता है, लेकिन पता नहीं दूसरे लोगों को भी इससे उतना फ़ायदा होगा या नहीं
    • मेरे हिसाब से सबसे कठिन हिस्सा इसे production environment में कम से कम समस्याओं के साथ चलाना है। इसे scale करना और data changes के प्रति robust बनाना बहुत समय लेता है

  • एक ग्राहक बच्चों के लिए sports camp चलाता है। बच्चे यह अनुरोध कर सकते हैं कि वे कौन-सा sport खेलना चाहते हैं और किस दोस्त के साथ एक ही class में रहना चाहते हैं।
    इसकी वजह से ऐसा scheduling problem पैदा हुआ जिसे इंसानों के लिए हल करना मुश्किल था, और पहले हर साल इस काम में कई हफ्तों की manpower लगती थी। हमने ग्राहक के data को OR-Tools-आधारित optimizer से जोड़ने वाला एक सरल system बना दिया, और अब scheduling कुछ clicks में पूरी हो जाती है

    • सही है। अगर data, constraints, और utility function को system में ठीक से डाल दिया जाए, तो बहुत जल्दी काफी अच्छे solutions बड़ी संख्या में निकाले जा सकते हैं।
      मैं basketball league का coach हूँ, और उसमें 8 periods होते हैं। कोई भी खिलाड़ी किसी दूसरे खिलाड़ी से 2 periods से ज़्यादा नहीं खेल सकता। हर मैच के लिए संभावित lineups की संख्या, playing-time constraints को संतुष्ट करते हुए भी, खगोलीय रूप से बड़ी होती है।
      constraints को संतुष्ट करने वाले lineups के sets ढूँढना बहुत आसान है, लेकिन optimal या near-optimal lineups के sets ढूँढना बहुत मुश्किल है। अगर देर से आने वाले या बिना बताए अनुपस्थित रहने वाले खिलाड़ियों को भी reflect करना हो, तो बात और दिलचस्प हो जाती है।
      *यह हमेशा पूरी तरह संभव नहीं होता
    • इस बारे में आपने यह कैसे किया, इस पर विस्तार से लिखा गया blog post निश्चित रूप से बहुत लोकप्रिय होगा

  • मुझे जिज्ञासा है कि क्या ऐसा parametric CAD मौजूद है जो मुख्य रूप से constraint solver की तरह काम करता हो।
    शुरुआत में मुझे अक्सर यह बात खटकती है कि जिन parameter values की मुझे परवाह नहीं होती, उनका भी कोई मोटा अनुमान लगाना पड़ता है। अच्छा होगा अगर जिन parameters में रुचि है उन्हें constraints की तरह रखा जा सके और बाकी को optimize किया जा सके

  • मैं जानना चाहता हूँ कि यह तरीका mixed integer programming की तुलना में कैसा है। Physical problems में यह कैसा रहेगा?

    • बहुत-सी problems को दोनों तरीकों से formulate किया जा सकता है। MILP में हमेशा एक objective function होता है, और constraints हमेशा decision variables के linear combinations होते हैं।
      Gurobi अविश्वसनीय रूप से तेज़ है, इसलिए solution पाने के लिए problem को थोड़ा मोड़कर भी MILP में फिट करना फायदेमंद हो सकता है
    • CP-SAT सिर्फ integers के लिए है, इसलिए physical problems के लिए यह बहुत अच्छा नहीं लगेगा। Real numbers को scale किया जा सकता है, लेकिन यह floating point को सीधे handle करने जितना अच्छा नहीं है।
      CP-SAT का फायदा यह है that यह boolean और integer variables व constraints को MIP solver की तुलना में कहीं अधिक कुशलता से संभालता है, खासकर all_different जैसे high-level constraints में
    • मेरा अंदाज़ा है कि कुल मिलाकर यह काफ़ी similar है। https://www.amazon.com/gp/product/1107658799/ इस विषय पर मेरी आख़िरी पढ़ी हुई किताब थी, और उसमें भी कई वही ideas आते हैं।
      खासकर, इस लेख में किसी value को minimize करने की जो बात है, वह मुझे मूलतः उसी बात को सीधे लिखना लगता है