Οι ερευνητές προσεγγίζουν νέο όριο ταχύτητας για το σπερματικό πρόβλημα | Περιοδικό Quanta

Το πρόβλημα του ταξιδιώτη πωλητή είναι ένα από τα παλαιότερα γνωστά υπολογιστικά ερωτήματα. Ζητάει την ιδανική διαδρομή μέσα από μια συγκεκριμένη λίστα πόλεων, ελαχιστοποιώντας τα χιλιόμετρα. Παρά το ότι φαίνεται απλό, το πρόβλημα είναι εμφανώς δύσκολο. Ενώ μπορείτε να χρησιμοποιήσετε ωμή βία για να ελέγξετε όλες τις πιθανές διαδρομές μέχρι να βρείτε το συντομότερο μονοπάτι, μια τέτοια στρατηγική γίνεται αβάσιμη μετά από λίγες μόνο πόλεις. Αντίθετα, μπορείτε να εφαρμόσετε ένα αυστηρό μαθηματικό μοντέλο που ονομάζεται γραμμικός προγραμματισμός, το οποίο προσεγγίζει το πρόβλημα ως σύνολο εξισώσεων και ελέγχει μεθοδικά τους πιθανούς συνδυασμούς για να βρει την καλύτερη λύση.

Αλλά μερικές φορές, χρειάζεται να κάνετε βελτιστοποίηση για προβλήματα που αφορούν ακέραια ποσά. Τι ωφελεί ένα εργοστασιακό σχέδιο βελτιστοποίησης που κατασκευάζει 500.7 καναπέδες; Για αυτό, οι ερευνητές συχνά στρέφονται σε μια παραλλαγή του γραμμικού προγραμματισμού που ονομάζεται ακέραιος γραμμικός προγραμματισμός (ILP). Είναι δημοφιλές σε εφαρμογές που περιλαμβάνουν διακριτές αποφάσεις, συμπεριλαμβανομένου του προγραμματισμού παραγωγής, του προγραμματισμού πληρώματος αεροπορικής εταιρείας και της δρομολόγησης οχημάτων. «Βασικά, το ILP είναι το ψωμί και το βούτυρο της επιχειρησιακής έρευνας τόσο στη θεωρία όσο και στην πράξη», είπε Santosh Vempala, επιστήμονας υπολογιστών στο Ινστιτούτο Τεχνολογίας της Τζόρτζια.

Από τότε που πρωτοδιατύπωσαν το ILP πάνω από 60 χρόνια πριν, οι ερευνητές έχουν ανακαλύψει διάφορους αλγόριθμους που λύνουν προβλήματα ILP, αλλά όλοι ήταν σχετικά αργοί όσον αφορά τον αριθμό των βημάτων που απαιτούνται. Η καλύτερη έκδοση που θα μπορούσαν να βρουν - ένα είδος ορίου ταχύτητας - προέρχεται από την ασήμαντη περίπτωση όπου οι μεταβλητές του προβλήματος (όπως εάν ένας πωλητής επισκέπτεται μια πόλη ή όχι) μπορούν να υποθέσουν μόνο δυαδικές τιμές (μηδέν ή 1). Σε αυτήν την περίπτωση, το ILP έχει χρόνο εκτέλεσης που κλιμακώνεται εκθετικά με τον αριθμό των μεταβλητών, που ονομάζεται επίσης διάσταση. (Εάν υπάρχει μόνο μία μεταβλητή, χρειάζονται μόνο δύο βήματα για να δοκιμάσετε κάθε πιθανό συνδυασμό και να λύσετε το πρόβλημα· δύο μεταβλητές σημαίνουν τέσσερα βήματα, τρεις σημαίνουν οκτώ βήματα και ούτω καθεξής.)

Δυστυχώς, όταν οι μεταβλητές λάβουν μια τιμή πέρα ​​από το μηδέν και το 1, ο χρόνος εκτέλεσης του αλγορίθμου μεγαλώνει πολύ. Οι ερευνητές αναρωτιόντουσαν εδώ και καιρό αν θα μπορούσαν να έρθουν πιο κοντά στο ασήμαντο ιδανικό. Η πρόοδος ήταν αργή, με το ρεκόρ που διαδραματίστηκε στη δεκαετία του 1980 και μόνο σταδιακά βελτιώσεις έγινε από τότε.

Αλλά πρόσφατα δουλειά by Βίκτορ Ρέις, επί του παρόντος στο Institute for Advanced Study, και Thomas Rothvoss, στο Πανεπιστήμιο της Ουάσιγκτον, έκανε το μεγαλύτερο άλμα χρόνου εκτέλεσης των τελευταίων δεκαετιών. Συνδυάζοντας γεωμετρικά εργαλεία για να περιορίσουν τις πιθανές λύσεις, δημιούργησαν έναν νέο, ταχύτερο αλγόριθμο για την επίλυση ILP σχεδόν ταυτόχρονα με την ασήμαντη δυαδική περίπτωση. Το αποτέλεσμα έλαβε το βραβείο καλύτερου χαρτιού το 2023 Θεμέλια Επιστήμης Υπολογιστών διάσκεψη.

"Αυτός ο νέος αλγόριθμος είναι εξαιρετικά συναρπαστικός", είπε Νόα Στίβενς-Νταβίντοβιτς, μαθηματικός και επιστήμονας υπολογιστών στο Πανεπιστήμιο Cornell. «Αντιπροσωπεύει την πρώτη [σημαντική] βελτίωση στους λύτες ILP εδώ και σχεδόν 40 χρόνια».

Το ILP λειτουργεί μετατρέποντας ένα δεδομένο πρόβλημα σε ένα σύνολο γραμμικών εξισώσεων που πρέπει να ικανοποιούν ορισμένες ανισότητες. Οι συγκεκριμένες εξισώσεις βασίζονται στις λεπτομέρειες του αρχικού προβλήματος. Όμως, ενώ αυτές οι λεπτομέρειες μπορεί να διαφέρουν, η βασική σύνθεση των προβλημάτων ILP παραμένει η ίδια, δίνοντας στους ερευνητές έναν μοναδικό τρόπο να επιτεθούν σε ένα πλήθος προβλημάτων.

Αυτό δεν σημαίνει ότι είναι εύκολη δουλειά. Μόλις το 1983 ο μαθηματικός Χέντρικ Λένστρα αποδείχθηκε ότι το γενικό πρόβλημα ήταν ακόμη και επιλύσιμο, παρέχοντας τον πρώτο αλγόριθμο που θα μπορούσε να το κάνει. Ο Lenstra σκέφτηκε το ILP γεωμετρικά. Πρώτον, μετέτρεψε τις ανισότητες στην καρδιά του ILP σε ένα κυρτό σχήμα, όπως οποιοδήποτε κανονικό πολύγωνο. Αυτό το σχήμα αντιπροσωπεύει τους περιορισμούς του μεμονωμένου προβλήματος που επιλύετε, είτε πρόκειται για παραγωγή καναπέ είτε για προγραμματισμό αεροπορικών εταιρειών, επομένως το εσωτερικό του σχήματος αντιστοιχεί σε όλες τις πιθανές τιμές που θα μπορούσαν να λύσουν τις ανισότητες, και συνεπώς το πρόβλημα. Ο Λένστρα ονόμασε αυτό το σχήμα κυρτό σώμα. Η διάσταση του προβλήματος επηρεάζει τη διάσταση αυτού του σχήματος: Με δύο μεταβλητές παίρνει τη μορφή ενός επίπεδου πολυγώνου. σε τρεις διαστάσεις είναι α Πλατωνικό στερεό, και ούτω καθεξής.

Ο Lenstra στη συνέχεια φαντάστηκε όλους τους ακέραιους αριθμούς ως ένα άπειρο σύνολο σημείων πλέγματος, γνωστό στα μαθηματικά ως πλέγμα. Μια δισδιάστατη έκδοση μοιάζει με μια θάλασσα από κουκκίδες και σε τρεις διαστάσεις μοιάζει με τα σημεία όπου συνδέονται οι χαλύβδινες δοκοί σε ένα κτίριο. Η διάσταση του πλέγματος εξαρτάται επίσης από τη διάσταση ενός δεδομένου προβλήματος.

Για να λύσετε ένα δεδομένο πρόβλημα ILP, ο Lenstra έδειξε ότι απλώς αναζητάτε πού συναντούν οι πιθανές λύσεις το σύνολο των ακεραίων: στη τομή του κυρτού σώματος και του πλέγματος. Και βρήκε έναν αλγόριθμο που μπορούσε να αναζητήσει εξαντλητικά αυτόν τον χώρο — αλλά για να είναι αποτελεσματικός, μερικές φορές έπρεπε να σπάσει το πρόβλημα σε κομμάτια μικρότερων διαστάσεων, προσθέτοντας πολλά βήματα στο χρόνο εκτέλεσης.

Τα επόμενα χρόνια, αρκετοί ερευνητές διερεύνησαν πώς να κάνουν αυτόν τον αλγόριθμο να τρέχει πιο γρήγορα. Το 1988, οι Ravi Kannan και László Lovász εισήγαγαν μια ιδέα που ονομάζεται ακτίνα κάλυψης. δανειστεί από τη μελέτη του κωδικούς διόρθωσης σφαλμάτων, για να βοηθήσει το κυρτό σώμα και το πλέγμα να τέμνονται πιο αποτελεσματικά. Χονδρικά, η ακτίνα κάλυψης διασφαλίζει ότι το κυρτό σώμα περιέχει πάντα τουλάχιστον ένα ακέραιο σημείο, ανεξάρτητα από το πού το τοποθετείτε στο πλέγμα. Ως αποτέλεσμα, το μέγεθος της ακτίνας κάλυψης καθορίζει επίσης πόσο αποτελεσματικά μπορείτε να λύσετε το πρόβλημα ILP.

Έτσι, όλα κατέληξαν στον καθορισμό του μεγέθους της ιδανικής ακτίνας κάλυψης. Δυστυχώς, αυτό αποδείχτηκε ένα δύσκολο πρόβλημα από μόνο του και το καλύτερο που μπορούσαν να κάνουν οι Kannan και Lovász ήταν να περιορίσουν μια πιθανή τιμή αναζητώντας πάνω και κάτω όρια. Έδειξαν ότι το άνω όριο - το μέγιστο μέγεθος της ακτίνας κάλυψης - κλιμακώθηκε γραμμικά με τη διάσταση. Αυτό ήταν αρκετά γρήγορο, αλλά όχι αρκετό για να επιταχύνει σημαντικά το χρόνο εκτέλεσης του ILP. Τα επόμενα 30 χρόνια, άλλοι ερευνητές θα μπορούσαν να τα πάνε ελαφρώς καλύτερα.

Αυτό που τελικά βοήθησε τον Reis και τον Rothvoss να ξεπεράσουν ήταν ένα άσχετο μαθηματικό αποτέλεσμα που επικεντρώθηκε καθαρά στα πλέγματα. Το 2016, Oded Regev και Stephens-Davidowitz έδειξε, στην πραγματικότητα, πόσα σημεία πλέγματος θα μπορούσαν να χωρέσουν σε ένα συγκεκριμένο σχήμα. Ο Reis και ο Rothvoss το εφάρμοσαν σε άλλα σχήματα, γεγονός που τους επέτρεψε να εκτιμήσουν καλύτερα τον αριθμό των σημείων πλέγματος που περιέχονται σε μια ακτίνα κάλυψης ILP, χαμηλώνοντας το άνω όριο. «Η πιο πρόσφατη ανακάλυψη ήρθε με τη συνειδητοποίηση ότι μπορείς να κάνεις άλλα είδη σχημάτων», είπε ο Regev.

Αυτό το νέο σφιγμένο άνω όριο ήταν μια τεράστια βελτίωση, επιτρέποντας στους Reis και Rothvoss να επιτύχουν μια δραματική επιτάχυνση του συνολικού αλγορίθμου ILP. Η δουλειά τους φέρνει το χρόνο εκτέλεσης στο (log n)^O(n), Όπου n είναι ο αριθμός των μεταβλητών και O (n)σημαίνει ότι κλιμακώνεται γραμμικά με n. (Αυτή η έκφραση θεωρείται "σχεδόν" ίδια με τον χρόνο εκτέλεσης του δυαδικού προβλήματος.)

«Είναι ένας θρίαμβος στη διασταύρωση των μαθηματικών, της επιστήμης των υπολογιστών και της γεωμετρίας», είπε Ντάνιελ Νταντούς του εθνικού ερευνητικού ινστιτούτου CWI στην Ολλανδία, ο οποίος βοήθησε να γίνει πρωτοπόρος ο αλγόριθμος που χρησιμοποιούσαν οι Reis και Rothvoss για τη μέτρηση του χρόνου εκτέλεσης ILP.

Προς το παρόν, ο νέος αλγόριθμος δεν έχει πραγματικά χρησιμοποιηθεί για την επίλυση προβλημάτων υλικοτεχνικής υποστήριξης, καθώς θα χρειαζόταν πάρα πολλή δουλειά για την ενημέρωση των σημερινών προγραμμάτων για να γίνει χρήση του. Αλλά για τον Rothvoss, αυτό είναι εκτός θέματος. «Πρόκειται για τη θεωρητική κατανόηση ενός προβλήματος που έχει θεμελιώδεις εφαρμογές», είπε.

Όσον αφορά το εάν η υπολογιστική απόδοση του ILP θα μπορούσε να βελτιωθεί περαιτέρω, οι ερευνητές εξακολουθούν να ελπίζουν ότι θα συνεχίσουν να πλησιάζουν τον ιδανικό χρόνο εκτέλεσης — αλλά όχι σύντομα. «Αυτό θα απαιτούσε μια θεμελιωδώς νέα ιδέα», είπε η Βεμπάλα.