Deel 1: Geheeltallige programmering (IP)
Preemptive Programming: Er bestaat een Hierarchie tijdens de objectieven.
Cutting-plane Algoritme:
Tailing off: Optiamle doelfunctie waarde zal afvlakken naarmate aantal toegevoegde sneden ∞ nadert; laatste x
iteraties geen significante verbetering in de LP-bound.
Branch-and-cut: combinatie branch and bound met cuts.
Snedes zijn sterker als ze meer van de LP-oplossingsruimte wegsnijden.
Gomory Snedes: bewaart alle geheeltallige oplossing.
Maak gomory-snede-equatie enkel van de equatie(s) met fractionele oplossing(en).
∑ xi ≥ 1 voor alle nonbasic variabelen.
DFJ-Formulering (Subtour Eliminatie): 2 formuleringen zijn even sterk (LP-relaxaties hebben zelfde
oplossingsruimte)
Sterker dan MTZ formulering:
Wordt sneller groter in rekentijd dan MTZ: 2n
∑ x{i,j} ≥ 2 met S ∈ N, 2 ≤ ∣S∣ < ∣N∣
De 2 subtours moeten verbonden zijn met elkaar met minstens 2 ‘links’.
∑ x{i,j} ≤ ∣S∣ − 1 met S ∈ N, 2 ≤ ∣S∣ < ∣N∣
Het aantal links/paden in een cluster moet kleiner zijn ∣S∣ − 1 met S het aantal knooppunten, om zo subtours
te vermijden.
Comb Inequality: Subgraaf met x{1,2} + x{1,3} + x{1,4} + x{2,3} + x{2,5} + x{3,6} ≤ 4
Met 4 het aantal bogen dat ge maximaal kunt gebruiken om een loop/lus te doorlopen.
, Als er een pijl is tussen 4 en 2 ⇒ x42 ; dan moet u2 groter zijn dan u4 +1
Als er geen pijl is tussen 4 en 2 ⇒ x42 ; dan is u2 vrij, (moet groter zijn dan −M ) met M groot.
Deel 2: Combinatorische Optimalisatie (Dynamische
Programmering)
Kortste pad vanuit één knooppunt naar alle andere:
Rekentijd/Tijdscomplexiteit: O(n²) :
O(n x n) : checken in elke iteratie of de getallen kleiner zijn.
+O(m) : Elk van de pijlen gaat maar 1x gebruikt worden
Iteratie 1 2 3 4 5 6
0 0* Infinity Infinity Infinity Infinity Infinity
1 0* 5 3* Infinity Infinity Infinity
2 0* 5* 3* Infinity 6 Infinity
3 0* 5* 3* 9 6* Infinity
4 0* 5* 3* 9 6* Infinity
5 0* 5* 3* 9* 6* Infinity
6 0* 5* 3* 9* 6* 10*
7 0* 5* 3* 9* 6* 10*
8 0* 5* 3* 9* 6* 10*
Met i∗ = permanent gemaakt.
Ge gaat altijd verder van de node die net permanent gemaakt is.
Als ge een waarde vind voor node(i) bij iteratie j die groter is dan bij iteratie j − 1, dan laat ge de kleinste
waarde staan.
Bellman-Ford: Opsporen negatieve Lus
Notes 3
Les avantages d'acheter des résumés chez Stuvia:
Qualité garantie par les avis des clients
Les clients de Stuvia ont évalués plus de 700 000 résumés. C'est comme ça que vous savez que vous achetez les meilleurs documents.
L’achat facile et rapide
Vous pouvez payer rapidement avec iDeal, carte de crédit ou Stuvia-crédit pour les résumés. Il n'y a pas d'adhésion nécessaire.
Focus sur l’essentiel
Vos camarades écrivent eux-mêmes les notes d’étude, c’est pourquoi les documents sont toujours fiables et à jour. Cela garantit que vous arrivez rapidement au coeur du matériel.
Foire aux questions
Qu'est-ce que j'obtiens en achetant ce document ?
Vous obtenez un PDF, disponible immédiatement après votre achat. Le document acheté est accessible à tout moment, n'importe où et indéfiniment via votre profil.
Garantie de remboursement : comment ça marche ?
Notre garantie de satisfaction garantit que vous trouverez toujours un document d'étude qui vous convient. Vous remplissez un formulaire et notre équipe du service client s'occupe du reste.
Auprès de qui est-ce que j'achète ce résumé ?
Stuvia est une place de marché. Alors, vous n'achetez donc pas ce document chez nous, mais auprès du vendeur jan-willemdenys. Stuvia facilite les paiements au vendeur.
Est-ce que j'aurai un abonnement?
Non, vous n'achetez ce résumé que pour €9,95. Vous n'êtes lié à rien après votre achat.
