أفضل حل مختلط لتحسين الأعداد الصحيحة مفتوحة المصدر [مغلق]
https://stackoverflow.com/questions/502102
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
أنا أستخدم CPLEX لحل نماذج التحسين الضخمة (أكثر من 100 ألف متغير) والآن أود أن أرى ما إذا كان بإمكاني العثور على بديل مفتوح المصدر، وأحل مشكلات الأعداد الصحيحة المختلطة (MILP) ويعمل CPLEX بشكل رائع ولكنه مكلف للغاية إذا كنا أرغب في التوسع، لذا أحتاج حقًا إلى العثور على بديل أو البدء في كتابة مكتبة التحسين المخصصة الخاصة بنا (والتي ستكون مؤلمة)
أي اقتراح/البصيرة سيكون موضع تقدير كبير
المحلول
ولقد وجدت شخصيا GLPK أفضل (أي أسرع) من LP_SOLVE. وهو يدعم تنسيقات الملفات المختلفة، وميزة أخرى هي واجهة المكتبة، والذي يسمح التكامل السلس مع التطبيق الخاص بك.
نصائح أخرى
وتأييد آخر ل عملة-OR . لقد وجدنا أن العنصر الخطي محسن (شلة) كان قويا جدا، ويمكن ضبطها المكون صحيح المختلط (سي بي سي) بشكل جيد مع بعض التحليل. قارنا مع LP-حل وGLPK.
لمشاكل صعبة حقا، حلالا التجاري هو الطريق للذهاب.
وحاول حلالا SCIP. لقد استخدمت لMILP مشاكل مع أكثر من 300K متغيرات مع الأداء الجيد. أداء MILP لها هو أفضل بكثير من GLPK. لديها أيضا Gurobi الأداء الممتاز لمشاكل MILP (وعادة أفضل من SCIP (مايو 2011))، ولكن قد يكون مكلفا إذا لم تكن مستخدم الأكاديمي. سوف Gurobi استخدام multicores لتسريع حلالا.
هل جربت lp_solve؟كانت هناك أيضًا بعض الاقتراحات الأخرى في الأسئلة التالية لجافا:
لو كنت مكانك، فسأحاول استخدام واجهة متعددة الحلول مثل Osi (C++) أو PuLP (python) حتى تتمكن من كتابة التعليمات البرمجية الخاصة بك مرة واحدة، واختبارها باستخدام العديد من الحلول.
إذا كانت برامج الأعداد الصحيحة التي ستقوم بحلها ضخمة، فإنني أوصي بـ python بدلاً من C++، لأن التعليمات البرمجية الخاصة بك ستبدو أكثر نظافة وسيتم قضاء 99٪ من الوقت في الحل.
على العكس من ذلك، إذا كانت المشكلات صغيرة، فلن يتم إهمال وقت نسخ المشكلات من ذاكرة بايثون إلى الحل (ذهابًا وإيابًا):وفي هذه الحالة، يمكنك تجربة بعض التحسينات الملحوظة في الأداء باستخدام لغة مجمعة.
ولكن إذا كانت المشاكل هائلة للغاية، فستفوز اللغات المجمعة مرة أخرى، لأن مساحة الذاكرة سيتم تقسيمها تقريبًا على 2 (لا توجد نسخة من المشكلة في بايثون).
وأوصي سحب المشروع عملة. عملة أو
والعديد من يحلون جيدة هنا، بما في ذلك ipOPT لمشاكل غير الخطية واثنين يحلون صحيح المختلطة كذلك.
SCIP ليست سيئة!
وعلى الرغم من أن هذا هو ربما ليس ما تريد أن تسمعه، ولكن هناك سنة ضوئية بين يحلون التجارية CPLEX وGurobi من جهة ويحلون مفتوحة المصدر من جهة أخرى.
وعلى الرغم من ذلك يمكن أن تكون محظوظا والنموذج الخاص بك يعمل بشكل جيد مع GLPK، عملة أو ما شابه ذلك، ولكن في الحلول مفتوحة المصدر العامة هي وسيلة وراء يحلون التجارية. إذا كان مختلفا، لا يمكن لأحد أن يدفع 12،000 $ للحصول على ترخيص Gurobi وأكثر من ذلك للحصول على ترخيص CPLEX.
في السنوات الماضية لقد رأيت العديد والعديد من النماذج التي كانت مجرد لالصعب على يحلون مفتوحة المصدر. صدقوني ...
وانها ليست كثيرا مسألة الحجم، ولكن من الصعوبة رقمية.
والمتغيرات 100K هي مشكلة كبيرة. العديد من المكتبات مفتوحة المصدر لا تعمل بشكل جيد مع أن العديد من المتغيرات. من ما قرأت lp_solve وقد تم اختبار فقط لحوالي 30K المتغيرات. باستخدام نظام تجاري قد يكون الخيار الوحيد.
ولقد استخدمت DICOPT باستخدام ملقم NEOS ( HTTP: / /www.neos-server.org/neos/solvers/minco:DICOPT/GAMS.html ) لحل (تقريبا 1K المتغيرات و1K القيود) مختلطة صحيح البرامج الكبيرة غير الخطية، ووجدت أنها ممتازة.
لمشكلتي DICOPT فعلت أفضل بكثير من يحلون MINLP الأخرى المدرجة على الخادم الأجسام القريبة من الأرض BARON / KNITRO / LINDO / SBB الخ.
وهناك بعض القيود لتقديم فرص العمل للNEOS وهو مرهق قليلا ولكن حرية الوصول إلى حلالا تجاريا قويا أكثر من يعوض عن ذلك.
وسأضيف ما يلي إلى إجابات ممتازة بالفعل.
وحين، كما أشار آخرون، يحلون التجارية هي أسرع بكثير وأكثر قدرة من البدائل الخالية من المهم أن تفكر في مقدار وجود فجوة المثالية التي يمكن قبوله. لمشاكل كبيرة مع العديد من المتغيرات صحيح قد تحصل على أسرع حل مرات إذا كنت لا يمكن أن يقبل 1٪ أو أكبر فجوة المثالية (التخلف تميل إلى أن تكون في جميع أنحاء 0.01٪ أو أقل).
وبالطبع إذا كنت حل مشكلة حيث يترجم 1٪ إلى الملايين من الدولارات هذا أمر غير مقبول - وبالتالي سوق يحلون أرفع. (بعض المقارنات بين Gurobi إلى يحلون الحر هنا )
وأود أن نتفق مع الآخرين أن استخدام المنصة التي تولد ملفات مشكلة حلالا مستقلة (مثل * .mps، * ملفات .lp) من المجدي كما يمكنك ثم محاولة الخروج يحلون أخرى. أنا باستخدام اللب وأنا في العثور عليه وحلالا COIN_CBC مجانا، ممتازة. وإن كان محدودا لمشاكل مع العديد من المتغيرات عدد صحيح.
وأنا مندهش من أن لا أحد قد ذكر MIPCL ( HTTP: //www.mipcl- cpp.appspot.com/index.html ). يدعي هذا حلالا أن تكون مفتوحة المصدر تحت رخصة LGPL (المصدر: HTTP: //www.mipcl -cpp.appspot.com/licence.html )، وبالتالي فإنه هو أيضا مناسبة لاستخدامها في التطبيقات غير مفتوح المصدر. ولكن ما هو مفقود لتكون مفتوحة حقا مصدر هو رمز مصدر حلالا نفسها.
وهانز Mittelmann قريب جدا (10 سبتمبر 2017) لم مختلطة صحيح البرمجة الخطية المعيار: HTTP: / /plato.asu.edu/ftp/milpc.html (وكنت قد تكون مهتمة ايضا في النظر إلى صفحة النظرة العامة <لأ href = "http://plato.asu.edu/bench.html" يختلط = " نوفولو noreferrer "> http://plato.asu.edu/bench.html أو الشرائح من كلامه: <لأ href =" http://plato.asu.edu/talks/informs2017.pdf "يختلط = "noreferrer نوفولو"> http://plato.asu.edu/talks/informs2017.pdf ).
في المختلطة البرمجة المعيار صحيح الخطي مع 12 المواضيع وسقفا زمنيا قدره 2 ساعة تمكنت MIPCL إلى حل 79 حالة. فقط يحلون التجارية CPLEX، Gurobi وXPRESS تمكنت من حل أكثر في ظل القيود معين (86 أو 87 حالات، على التوالي).
وأيضا من حيث قياس أداء المختار (مرة أخرى باستخدام 12 موضوع) MIPCL أسرع من المشتقات قياسها SCIP (FSCIPC، FSCIPS) ومفتوحة المصدر حلالا CBC. مرة أخرى فقط يحلون التجارية CPLEX، Gurobi وXPRESS تكومبيتي MIPCL بشكل كبير من حيث الأداء.
وليس المصدر المفتوح، ولكن إذا كان لديك ترخيص Microsoft التحالف الأكاديمي، و مؤسسة مايكروسوفت حلالا يتم تضمين (MSF) طبعة المؤسسة. Gurobi مجاني أيضا للأغراض الأكاديمية، كنت استخدمه في البحث أطروحتي.
