ما الخوارزميات (الخوارزميات) التي يمكن أن تحل مشكلة برمجة القيد هذه؟

Question

أحتاج إلى حل مشكلة تأثير الوظيفة وأود أن أجد خوارزميات فعالة بشكل افضل لحل هذه المشكلة.

دعنا نقول أن هناك بعض العمال الذين يمكن أن يفعلوا عدة أنواع من المهام. لدينا أيضا مجموعة من المهام التي يجب القيام بها كل أسبوع. كل مهمة يستغرق بعض الوقت. يجب أن تؤخذ كل مهمة من قبل شخص ما. يجب أن يعمل كل عامل بين ساعة واحدة في الأسبوع.

يبدو أن هذا الجزء الأول من المشكلة مرشح جيد لخوارزمية البرمجة القيد.

ولكن هنا هو المضاعفات: لأن العامل يمكن أن يفعل مهام مختلفة قد يكون لديهم أيضا تفضيلات (أو رغبات). إذا أراد المرء إرضاء جميع رغبات الجميع، فلا يوجد حل للمشكلة (الكثير من القيود).

لذلك أحتاج إلى خوارزمية لحل هذه المشكلة. لا أريد إعادة اختراع العجلة إذا كانت العجلة المثالية موجودة بالفعل.

يجب أن تكون الخوارزمية عادلة (إذا كان يمكن للمرء أن يحدد هذه الكلمة)، لذلك يجب أن أكون قادرا على إضافة قيود مثل "محاولة تلبية رغبة واحدة على الأقل لكل شخص". لست متأكدا من أن هذه المشكلة يمكن حلها عن طريق تقييد الطرق الهرمية الموصوفة هنا: القيد الضائر. وبعد في الواقع، لست متأكدا من أن "الإنصاف" والرغبات يمكن التعبير عنها من خلال قيود صالحة لهذه الفئة من الخوارزميات.

هل هناك خبير برمجة قيد الإعطاء لي بعض النصائح؟ هل أحتاج إلى تطوير عجلة جديدة مع بعض الاستدلال بدلا من استخدام خوارزميات CP فعالة؟

شكرا !

Answer 1

مشكلتك معقدة بما فيه الكفاية بحيث يحتاج الحل العام إلى صياغة ك عدد صحيح خطي مشكلة. إذا كنت قادرا على الاسترخاء مع بعض المتطلبات، فقد تكون قادرا على استخدام نهج أبسط. علي سبيل المثال، المباريات المطابقة سيسمح لك بجدولة العديد من العمال إلى وظائف متعددة، ويمكنهم حتى التعامل مع التفضيلات، لكن لن تكون قادرا على فرض قيود "الإنصاف" العام. انظر على سبيل المثال ذات الصلة حتى السؤال. قمة التلوين لديه خوارزميات فعالة لفرض قيود فصل الوظائف.

وقد ذكرت الملصقات الأخرى البسيط و جدولة متجر العمل. وبعد Simplex هي خوارزمية تحسين - إنها عبور مساحة حل تسعى إلى زيادة بعض الوظائف الموضوعية. من المؤكد أن صياغة الوظيفة الموضوعية يمكن القيام به بالتأكيد، ولكن غير تافهة. جدولة متجر الوظائف الكلاسيكية، مثل المطابقة الثمانية، يمكن أن نموذج بعض جوانب مشكلتك، ولكن ليس كل شيء. لا توجد قيود مسبق، على سبيل المثال. هناك إصدارات ممتدة يمكنها التعامل مع بعض القيود، على سبيل المثال وضع حدود الوقت على المهام.

إذا كنت مهتما بالتطبيقات الموجودة، فإن بيثون networkx. المكتبة لديها تنفيذ هذه الخوارزمية المطابقة. وبعد مثال على برنامج توقيت مفتوح المصدر قد يكون اهتماما هو tablix..

Answer 2

لقد فعلت جدول زمني، والتي يمكن اعتبارها شكل من أشكال البرمجة القيدية. لديك قيود صلبة (مصنعة) والقيود الناعمة (مثل تفضيلات الفاصل).

عادة ما تصبح البرمجة العصرية الخطية عادة عديمة الفائدة بعد أكثر من 30 متغيرات، ويمكن أيضا أن يقال ذلك عن البسيط.

كان من خلال التحسينات الخاصة بالمجال من الخوارزميات المثيرة التي تم العثور على حل.

كانت الخوارزميات غير الأصلية المستخدمة تسخيم الصلب, الخوارزميات الوراثية, metaheuristic الخوارزميات ومثلها، ولكن في النهاية تم توفير أفضل نتيجة بواسطة مجال "ذكي" مخصص البحث الجشع خوارزمية.

في الأساس، قد تحصل على بعض النتائج اللائقة مع أحد الاستدلال هنا، لكن المشكلة الرئيسية تتمكن من تمييزها عند إفراط مشكلة.

أداة رائعة مفتوحة المصدر للبحث heuristiclab..

Answer 3

وأنا أتفق مع ما تم اقتراحه هنا. ومع ذلك، فإن MIP (مشاكل برمجة عدد صحيح مختلطة) من حجم كبير جدا (بعيدا عن 30 متغيرات!) تم حلها عمليا في الوقت الحاضر بفضل الرموز التجارية (Xpress، Cplex، Gurobi) أو المصدر المفتوح (COIN-OR / CBC). علاوة على ذلك، فإن لغات النمذجة الفاخرة مثل OPL Studio و Gams و Ampl والتخبط ... السماح للكتابة بسهولة نماذج رياضيات بدلا من استخدام واجهات برمجة التطبيقات.

يمكنك الاستفادة من خادم Neos (http://neos.mcs.anl.gov/neos/solvers/index.html.) لمحاولة Esaily MIPs المختلفة المتاحة. يمكنك إرسال النموذج الخاص بك بتنسيق ampl. على الرغم من أن ampl يأتي كنسخة محدودة مجانية، يمكن لنيوز التعامل مع مثيلات غير محدودة.

لغات النمذجة موجودة أيضا ل CP (COMET / OPL Studio) والبحث المحلي (Comet).

لا تتردد في التواصل معي من خلال موقع الويب الخاص بي www.rostudel.com ('اتصل' الصفحة)

ديفيد

Answer 4

هذا يبدو وكأنه جدولة متجر العمل.