Περιβάλλον δοκιμών ακέραιου προγραμματισμού
Επιλύστε ένα μικρό ακέραιο γραμμικό πρόγραμμα με ακριβή διακλάδωση και οριοθέτηση και δείτε κάθε κόμβο της αναζήτησης. Το καλύτερο σημείο αναφέρεται ως αποδεδειγμένα βέλτιστο μόνο όταν έχει εξερευνηθεί ολόκληρο το δέντρο.
Τα προγράμματα περιορίζονται σε 4.000 χαρακτήρες και 40 γραμμές, 8 μεταβλητές και 8 περιορισμούς με δύο ή περισσότερες μεταβλητές· το όριο κόμβων είναι από 1 έως 5.000 και η αναζήτηση σταματά επίσης μετά από 3.000.000 ακριβή αριθμητικά βήματα. Όλοι οι υπολογισμοί γίνονται στη συσκευή σας σε εργασία παρασκηνίου με όριο 15 δευτερολέπτων. Μπορείτε να κατεβάσετε αναφορά JSON και CSV κόμβων. Πρώτη γραμμή: maximize ή minimize και η αντικειμενική συνάρτηση. Έπειτα, ένας περιορισμός ανά γραμμή. Έως 4.000 χαρακτήρες. Εξετάστε τις ρυθμίσεις πριν από την εκτέλεση.
Το αποτέλεσμά σας
Περιβάλλον δοκιμών ακέραιου προγραμματισμού
- Γράψτε την αντικειμενική συνάρτηση στην πρώτη γραμμή, όπως maximize 5x + 4y.
- Προσθέστε έναν περιορισμό ανά γραμμή, όρια όπως x, y >= 0 και, προαιρετικά, γραμμές όπως integer x ή binary z.
- Ορίστε το όριο κόμβων και ξεκινήστε την αναζήτηση.
- Διαβάστε την κατάσταση, την καλύτερη τρέχουσα ακέραια λύση, το καλύτερο φράγμα και το χάσμα· έπειτα κατεβάστε την αναφορά JSON ή το CSV κόμβων.
Τι να περιμένετε
Τα προγράμματα περιορίζονται σε 4.000 χαρακτήρες και 40 γραμμές, 8 μεταβλητές και 8 περιορισμούς με δύο ή περισσότερες μεταβλητές· το όριο κόμβων είναι από 1 έως 5.000 και η αναζήτηση σταματά επίσης μετά από 3.000.000 ακριβή αριθμητικά βήματα. Όλοι οι υπολογισμοί γίνονται στη συσκευή σας σε εργασία παρασκηνίου με όριο 15 δευτερολέπτων. Μπορείτε να κατεβάσετε αναφορά JSON και CSV κόμβων.
Διακλάδωση και οριοθέτηση
Κάθε κόμβος επιλύει ακριβώς τη γραμμική χαλάρωση με τη μέθοδο simplex. Μια ακέραια μεταβλητή με κλασματική τιμή χωρίζεται σε δύο κλάδους, x <= floor και x >= ceiling. Ένας κόμβος αποκόπτεται όταν η χαλάρωσή του είναι ανέφικτη ή δεν μπορεί να βελτιώσει το καλύτερο ακέραιο σημείο που έχει βρεθεί. Μέθοδος: Wolsey, Integer Programming, 2η έκδοση, κεφάλαιο 7 (2020).
Τι σημαίνει αποδεδειγμένο
Όταν κάθε κόμβος έχει επιλυθεί ή αποκοπεί με ακριβές φράγμα, αποδεικνύεται ότι η καλύτερη τρέχουσα λύση είναι βέλτιστη ή ότι το πρόβλημα είναι ανέφικτο. Αν η αναζήτηση σταματήσει νωρίτερα λόγω ορίου κόμβων ή βημάτων, η καλύτερη τρέχουσα λύση είναι μόνο το καλύτερο σημείο που έχει βρεθεί μέχρι στιγμής και η αναφορά δίνει το καλύτερο φράγμα και τη μεταξύ τους απόσταση.
Κανόνες εισαγωγής
Από προεπιλογή, όλες οι μεταβλητές είναι ακέραιες. Όσες δηλώσετε με integer x, y παραμένουν ακέραιες· οι υπόλοιπες είναι συνεχείς. Οι περιορισμοί μίας μεταβλητής μετατρέπονται σε φράγματα. Αν μια χαλάρωση είναι μη φραγμένη, η αναζήτηση σταματά, επειδή το ακέραιο πρόγραμμα μπορεί τότε να είναι μη φραγμένο ή ανέφικτο.