DOI: https://doi.org/10.1038/s41598-024-67168-6
PMID: https://pubmed.ncbi.nlm.nih.gov/39039122
تاريخ النشر: 2024-07-22
المؤلف: Luis Fernando Pérez Armas وآخرون
الموضوع الرئيسي: جدولة المشاريع ذات الموارد المحدودة
نظرة عامة
تعتبر هذه الدراسة رائدة في تطبيق التبريد الكمي على مشكلة جدولة المشاريع ذات القيود على الموارد (RCPSP)، وهي تحدي جدولة معقد. يقوم المؤلفون بتحليل 12 صيغة معروفة للبرمجة الخطية المختلطة (MILP)، وفي النهاية يقومون بتحويل الصيغة الأكثر كفاءة من حيث الكيوبت إلى نموذج تحسين ثنائي غير مقيد تربيعي (QUBO). باستخدام جهاز التبريد الكمي D-Wave Advantage 6.3، يقارنون أدائه مع الحلول التقليدية، مما يكشف عن مزايا كبيرة، خاصة بالنسبة لحالات المشاكل الصغيرة إلى المتوسطة الحجم.
لتقييم فعالية التبريد الكمي والتبريد الكمي العكسي، يقدم الباحثون مقاييس جديدة: الوقت للوصول إلى الهدف ودرجة Q-score من Atos. بالإضافة إلى ذلك، تتناول الورقة تقنيات تحسين كمي متقدمة، بما في ذلك جداول التبريد المخصصة، مما يعزز الفهم والتطبيق العملي للحوسبة الكمية في مجال بحوث العمليات.
الطرق
في هذا القسم، يوضح المؤلفون المنهجية التجريبية المستخدمة في دراستهم، باستخدام جهاز التبريد الكمي D-Wave Advantage 6.3، الذي يتكون من 5640 كيوبت مع اتصال يبلغ 15. تم إنشاء التضمينات الثانوية باستخدام خوارزمية “minor-miner” من D-Wave، وتم حل كل حالة بوقت تبريد كمي قدره 20 ميكروثانية، بناءً على التحليل السابق. بالنسبة للتبريد الكمي العكسي (RQA)، تم تنفيذ جدول زمني محدد من 4 نقاط، يتضمن تطورات عكسية وأمامية مع فترات توقف، مما يسمح بتقييم شامل لتأثير أوقات التبريد والفترات على الأداء. سجلت الدراسة 10,000 عينة لكل حالة وقارنت أداء طرق التبريد الكمي مع تقنيات التحسين التقليدية، بما في ذلك العينة العشوائية (RS) والتبريد المحاكي (SA)، بالإضافة إلى الحلول مثل GUROBI وCOIN-CBC وGLPK.
تشير النتائج إلى أن RQA تفوقت على جميع طرق التحسين المختبرة، بما في ذلك GUROBI، خاصة في تحقيق طاقة الحالة الأساسية بشكل أسرع. ومع ذلك، لم تجد كل من QA وRQA، على الرغم من فعاليتهما في تقديم حلول عالية الجودة، الحالات الأساسية بشكل متسق، خاصة في الحالات الأكبر، كما يتضح من الانحراف النسبي عن طاقة الحالة الأساسية. لاحظ المؤلفون أنه بينما حافظت GUROBI على تفوقها في الكوانتيلات ذات الطاقة العالية، تفوقت QA وRQA في الكوانتيلات ذات الطاقة المنخفضة. من الجدير بالذكر أن أداء RQA كان أفضل من QA في السيناريوهات ذات الطاقة المنخفضة، على الرغم من أن SA تفوقت على كلاهما في معظم الحالات. تختتم الدراسة بأن الحد الأقصى لحجم الحالة القابل للحل بواسطة جهاز التبريد الكمي D-Wave هو سبع أنشطة غير وهمية، وبعد ذلك تتدهور جودة الحل بشكل كبير بسبب زيادة نسب كسر السلسلة، مما يثير القلق بشأن موثوقية جهاز التبريد للمشاكل الأكبر.
النتائج
في قسم “النتائج”، يقوم المؤلفون بإجراء تحليل شامل لعدة صيغ للبرمجة الخطية المختلطة (MILP) لتقييم ملاءمتها للتبريد الكمي في مشكلة جدولة المشاريع ذات القيود على الموارد (RCPSP). تبدأ التحقيقات بتقييم مفصل لاثني عشر صيغة MILP لتحديد النموذج الأكثر كفاءة من حيث الكيوبت، والذي يتم تحويله بعد ذلك إلى تنسيق تحسين ثنائي غير مقيد تربيعي (QUBO) لمزيد من التحليل.
تتم توضيح النتائج بشكل أكبر في القسم الفرعي “النتائج التجريبية”، حيث يتم تقييم أداء التبريد الكمي (QA) والتبريد الكمي المتكرر (RQA) عبر حالات مختلفة من RCPSP باستخدام QUBO المطور. بالإضافة إلى ذلك، يقدم القسم الفرعي “أوقات التبريد وتأثيرات التوقف” اختبارات تجريبية تستكشف كيف تؤثر التغيرات في أوقات التوقف والتبريد على فعالية التبريد الكمي، مما يوفر رؤى حول تحسين هذه المعلمات لتحسين الأداء.
المناقشة
تتناول قسم المناقشة في ورقة البحث مبادئ وتطبيقات التبريد الكمي (QA) وآلات D-Wave في حل مشاكل التحسين التوافقي، وخاصة مشكلة جدولة المشاريع ذات القيود على الموارد (RCPSP). يستخدم التبريد الكمي ميكانيكا الكم، وبشكل خاص التراكب والنفق، للتنقل بكفاءة عبر الحد الأدنى المحلي بحثًا عن الحد الأدنى العالمي لدالة التكلفة. تستند المنهجية إلى نظرية الأدياباتيك، التي تضمن بقاء النظام الكمي في حالته الأساسية خلال تحول بطيء لهاملتونيان من حالة أولية \( H_0 \) إلى حالة محددة للمشكلة \( H_1 \). تم تصميم معالجات D-Wave خصيصًا لمشاكل تقليل إيسينغ، باستخدام طوبولوجيا فريدة تقدم تحديات في الاتصال بين الكيوبتات وتستلزم تقنيات مثل التضمين الثانوي لرسم مشاكل التحسين على الأجهزة.
تُعتبر RCPSP مشكلة صعبة من نوع NP، تتميز بجدولة الأنشطة تحت قيود الترتيب والموارد لتقليل مدة المشروع. تناقش الورقة عدة صيغ للبرمجة الخطية المختلطة (MILP) لـ RCPSP، مع التأكيد على الحاجة إلى تكييف هذه الصيغ إلى أشكال تحسين ثنائي غير مقيد تربيعي (QUBO) مناسبة لأجهزة التبريد الكمي. كما توضح الدراسة بروتوكولًا لاختيار حالات RCPSP، باستخدام مولد RanGen لإنشاء حالات بمستويات صعوبة متفاوتة. علاوة على ذلك، تبرز أهمية مقاييس القياس مثل الوقت للوصول إلى الهدف (TTT) ودرجة Q-score لتقييم أداء خوارزميات التبريد الكمي، خاصة في سياق نظام D-Wave Advantage 6.3. تختتم المناقشة بتناول تعقيدات اختيار العقوبات في صيغ QUBO، مما يبرز الأبحاث المستمرة في تحسين هذه الاستراتيجيات لتحسين الكفاءة الحسابية.
DOI: https://doi.org/10.1038/s41598-024-67168-6
PMID: https://pubmed.ncbi.nlm.nih.gov/39039122
Publication Date: 2024-07-22
Author(s): Luis Fernando Pérez Armas et al.
Primary Topic: Resource-Constrained Project Scheduling
Overview
This study pioneers the application of quantum annealing to the resource-constrained project scheduling problem (RCPSP), a complex scheduling challenge. The authors analyze 12 established mixed integer linear programming (MILP) formulations, ultimately converting the most qubit-efficient formulation into a quadratic unconstrained binary optimization (QUBO) model. Utilizing the D-Wave Advantage 6.3 quantum annealer, they compare its performance against classical solvers, revealing significant advantages, especially for small to medium-sized problem instances.
To assess the efficacy of quantum annealing and reverse quantum annealing, the researchers introduce novel metrics: time-to-target and Atos Q-score. Additionally, the paper delves into advanced quantum optimization techniques, including customized anneal schedules, thereby enhancing the understanding and practical application of quantum computing within the realm of operations research.
Methods
In this section, the authors detail the experimental methodology employed in their study, utilizing the D-Wave Advantage 6.3 Quantum Annealer, which comprises 5640 qubits with a connectivity of 15. The minor embeddings were created using D-Wave’s “minor-miner” heuristic, and each instance was solved with a quantum annealing time of 20 µs, based on prior analysis. For the Reverse Quantum Annealing (RQA), a specific 4-point schedule was implemented, involving reverse and forward evolutions with pauses, allowing for a comprehensive evaluation of the impact of annealing times and pauses on performance. The study recorded 10,000 samples per instance and compared the performance of quantum annealing methods against classical optimization techniques, including Random Sampling (RS) and Simulated Annealing (SA), as well as solvers like GUROBI, COIN-CBC, and GLPK.
The results indicate that RQA outperformed all tested optimization methods, including GUROBI, particularly in achieving ground state energy more rapidly. However, both QA and RQA, while effective in providing high-quality solutions, did not consistently find ground states, especially in larger instances, as indicated by the relative deviation from the ground state energy. The authors observed that while GUROBI maintained superiority in high-energy quantiles, QA and RQA excelled in lower energy quantiles. Notably, the performance of RQA was superior to QA in lower energy scenarios, although SA outperformed both in most cases. The study concludes that the maximum instance size solvable by the D-Wave quantum annealer is seven non-dummy activities, beyond which the solution quality deteriorates significantly due to increased chain-break percentages, raising concerns about the reliability of the annealer for larger problems.
Results
In the “Results” section, the authors conduct a comprehensive analysis of multiple Mixed Integer Linear Programming (MILP) formulations to assess their suitability for quantum annealing in the Resource-Constrained Project Scheduling Problem (RCPSP). The investigation begins with a detailed evaluation of twelve MILP formulations to determine the most qubit-efficient model, which is subsequently transformed into a Quadratic Unconstrained Binary Optimization (QUBO) format for further analysis.
The findings are further elaborated in the “Experimental results” subsection, where the performance of Quantum Annealing (QA) and Repeated Quantum Annealing (RQA) is evaluated across various instances of the RCPSP using the developed QUBO. Additionally, the “Anneal time and pausing effects” subsection presents experimental tests that explore how variations in pausing and annealing times influence the effectiveness of quantum annealing, providing insights into optimizing these parameters for improved performance.
Discussion
The discussion section of the research paper elaborates on the principles and applications of quantum annealing (QA) and D-Wave machines in solving combinatorial optimization problems, particularly the Resource-Constrained Project Scheduling Problem (RCPSP). Quantum annealing utilizes quantum mechanics, specifically superposition and tunneling, to efficiently navigate local minima in search of a global minimum of a cost function. The methodology is grounded in the adiabatic theorem, which ensures that a quantum system remains in its ground state during a slow transformation of its Hamiltonian from an initial state \( H_0 \) to a problem-specific state \( H_1 \). D-Wave processors are specifically designed for Ising minimization problems, employing a unique topology that presents challenges in qubit connectivity and necessitates techniques like minor embedding to map optimization problems onto the hardware.
The RCPSP is identified as an NP-hard problem, characterized by scheduling activities under precedence and resource constraints to minimize project makespan. The paper discusses various Mixed Integer Linear Programming (MILP) formulations for the RCPSP, emphasizing the need to adapt these formulations into Quadratic Unconstrained Binary Optimization (QUBO) forms suitable for quantum annealers. The study also outlines a protocol for selecting RCPSP instances, utilizing the RanGen generator to create instances with varying levels of difficulty. Furthermore, it highlights the importance of benchmarking metrics such as Time-to-Target (TTT) and Q-score for evaluating the performance of quantum annealing algorithms, particularly in the context of the D-Wave Advantage 6.3 system. The discussion concludes by addressing the complexities of penalty selection in QUBO formulations, underscoring the ongoing research in optimizing these strategies for improved computational efficiency.