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

 (pganalyze.com)
1 पॉइंट द्वारा GN⁺ 2024-07-05 | 1 टिप्पणियां | WhatsApp पर शेयर करें

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

declarative paradigm
  • constraint programming (CP) discrete optimization समस्याओं को हल करने के लिए एक declarative paradigm है
  • imperative programming से अलग, इसमें आप इच्छित परिणाम का वर्णन करते हैं और प्रोग्राम स्वयं समाधान निकालता है
  • उदाहरण के लिए, वयस्कों की सूची निकालने के मामले में imperative approach और declarative approach के अंतर को समझाया गया है
constraint programming (CP) की बुनियाद
  • model: समस्या के इच्छित परिणाम का वर्णन
  • variables: वे मान जिन्हें खोजना है; हर variable का एक domain होता है, यानी अनुमत मानों का समूह
  • constraints: variables के बीच संबंधों का वर्णन
  • solution: variables को ऐसे मान देना जो constraints को संतुष्ट करें
Python और CP-SAT के साथ व्यावहारिक उदाहरण
  • समस्या: कर्मचारियों के लिए साप्ताहिक कार्य-शेड्यूल बनाना
  • model बनाना: CP-SAT का उपयोग करके एक खाली model बनाना
  • data: कर्मचारियों की सूची और भूमिकाएँ, कार्य-दिन, और शिफ्ट समय को परिभाषित करना
  • variables की परिभाषा: हर कर्मचारी के काम करने या न करने को दर्शाने वाले boolean variables बनाना
  • constraints जोड़ना: समस्या के विवरण के अनुसार variables पर constraints जोड़ना
model को हल करना
  • solve: model को हल करके परिणाम निकालना
  • अतिरिक्त constraints: overtime रोकना, किसी विशेष कर्मचारी के कार्य-घंटों को सीमित करना, और कुछ कर्मचारियों के बीच कार्य-समय के overlap को रोकने जैसे अतिरिक्त constraints जोड़ना
बीच में: solution status
  • solution status: optimal, feasible, infeasible, unknown जैसी स्थितियाँ लौटती हैं
  • उदाहरण: एक सरल उदाहरण के ज़रिये हर स्थिति को समझाया गया है
"माफ़ करना, Emma"
  • infeasible status: Emma का सप्ताह के 5 दिन छुट्टी पर रहना संभव नहीं है
  • वैकल्पिक सुझाव: Emma को सप्ताह में केवल 3 दिन छुट्टी देने का सुझाव
लक्ष्य: कार्य-घंटों का समान वितरण
  • objective जोड़ना: कार्य-घंटों को समान रूप से बाँटने के लिए objective जोड़ना
  • परिणाम: हर कर्मचारी के कार्य-घंटे बराबरी से वितरित होते हैं
निष्कर्ष
  • मूल अवधारणाओं का परिचय: constraint programming की बुनियादी अवधारणाओं का परिचय और उन्हें व्यावहारिक उदाहरणों से समझाया गया है
  • अगले लेख की झलक: अगले लेख में Postgres के index selection में constraint programming के उपयोग पर चर्चा होगी

GN⁺ की राय

  • constraint programming की उपयोगिता: जटिल optimization समस्याओं को हल करने में यह बेहद उपयोगी है
  • CP-SAT की ताकत: Google के OR-Tools प्रोजेक्ट के हिस्से के रूप में विकसित CP-SAT शक्तिशाली performance प्रदान करता है
  • वास्तविक उपयोग के मामले: इसे कर्मचारियों के कार्य-शेड्यूल बनाने जैसी वास्तविक समस्याओं में लागू किया जा सकता है
  • तकनीक अपनाने से पहले विचार: नई तकनीक अपनाते समय learning curve और मौजूदा systems के साथ integration की समस्याओं पर विचार करना चाहिए
  • मिलते-जुलते प्रोजेक्ट्स की सिफारिश: IBM के CPLEX, Gurobi जैसे commercial solvers भी समान क्षमताएँ प्रदान करते हैं

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

1 टिप्पणियां

 
GN⁺ 2024-07-05
Hacker News राय

  • पहले constraint solver इस्तेमाल करने का अनुभव रहा है, और ये टूल्स बेहद शानदार प्रदर्शन करते हैं

    • समस्या यह है कि beginners के लिए सामग्री लगभग नहीं के बराबर है
    • ज़्यादातर सामग्री Sudoku सुलझाने के तरीकों या बहुत ही तकनीकी research material पर आधारित है
    • अच्छा होता अगर ज़्यादा समस्याएँ हल करने वाले टूल्स अधिक सुलभ होते
    • सुलभ होने का मतलब फिर भी यह है कि programmer की ज़रूरत होगी

  • अपनी पुरानी किताब में MiniZinc और Python का इस्तेमाल करने वाले एक छोटे chapter को फिर से लिख रहा हूँ

    • MiniZinc एक constraint programming system है
    • Coursera पर MiniZinc का उपयोग करने वाला एक अच्छा course है

  • बहुत से programs एक ही data representation रखने की कोशिश करते हैं, लेकिन ज़्यादातर मामलों में यह तर्कसंगत नहीं होता

    • algorithm को नए representation पर चलाने के लिए काफी विकृति करनी पड़ती है
    • यह हमेशा खलता है कि representation को ज़्यादा बार transform नहीं किया जाता
    • representation बदलने पर बहुत संक्षिप्त रूप मिल सकता है, जिससे execution तेज़ हो सकता है

  • एक ग्राहक है जो sports camp चलाता है

    • बच्चे अपनी पसंद के sports और दोस्तों का अनुरोध कर सकते हैं
    • इससे ऐसा scheduling problem बनता है जो इंसानों के लिए कठिन है
    • OR-Tools आधारित optimization tool का उपयोग करके एक सरल system बनाया गया
    • अब कुछ clicks में scheduling पूरी हो जाती है

  • 2000 के दशक की शुरुआत में बहुत से solvers इस्तेमाल करने का अनुभव है

    • अभी Python इस्तेमाल करने वाले software (web) पर काम कर रहा हूँ
    • इस विषय पर गहराई से चर्चा देख कर खुशी हुई
    • constraints को model में बदलना काम का 90% है और यही सबसे कठिन हिस्सा है

  • जिज्ञासा है कि क्या ऐसा parametric CAD है जो मुख्य रूप से constraint solver की तरह काम करता हो

    • शुरुआत में उन parameter values का अनुमान लगाना अक्सर असुविधाजनक होता है जिनकी परवाह नहीं होती
    • इसकी बजाय जिन parameters में रुचि है उन्हें constrain करके बाकी को optimize करना चाहूँगा

  • जिज्ञासा है कि mixed integer programming की तुलना में यह कैसा है