[algoritmiek/lineair programmeren]integer oplossingen uit lp probleem

[timwaagh]

Ik heb hier een Binary Integer Lineair Programming probleem dat wordt opgelost door eerst het bijbehorende LP probleem op te lossen en daarna met het branch and bound algoritme de beste oplossing te vinden waarbij de variabelen de waarde 0 of 1 krijgen. Het opvallende is dat de oplossingen uit het LP probleem al bijna allemaal 0'en en 1'en zijn. Op de 10000 variabelen worden er vaak iets van 50 niet 0 of 1. Nu is dat niet zo prettig, want het branch and bound algoritme is heel langzaam. Zo langzaam dat het soms misgaat. Nou is 50 op de 10000 heel weinig. Dus is de vraag:

hoe komt het dat er zo weinig niet-integer oplossingen zijn? hoe komt het dat bepaalde oplossingen daarvan afwijken? hoe kunnen we eventueel een paar van die oplossingen van tevoren naar 0 of 1 krijgen, voordat we met branch-and-bound beginnen? Ik ben als student dit soort problemen niet gewend.

het 'relaxed' probleem: p hulpverleners moeten over n routes

\( x=(x_1,...,x_n) \)

verdeeld worden. omdat er ook lege routes zijn opgenomen (leeg = dat een hulpverlener nergens heen gaat), moet de hulpverlener precies een keer op een route voorkomen, dus zijn er p beperkingen van het type

\( a_{i1} x_1 + ... + a_{in} x_n = 1 \)

. Ook moet elk van de m incidenten precies een keer op de route liggen. Dit geeft m beperkingen van het type

\( a_{k1} x_1 + ... + a_{kn} x_n = 1\)

. Dit is een lineair programmeerprobleem en daarmee goed op te lossen (met een computer). Het punt is dat het antwoord van de computer dus veel routes geeft met de waarde 0 of 1. Helaas ook een aantal met waardes als 0,6666 of 0,5.

ik maak dit bericht thuis wel af. moet nu weg

[timwaagh]

???waarom kan ik mijn thread niet editen???

goed dan hier verder. Wat we denken is dat er in een aantal gevallen meerdere oplossingen ontstaan, waaronder een integer oplossing en dat dan soms de verkeerde gekozen wordt. Bijvoorbeeld als hulpverleners op dezelfde afstand van het incident zitten. Om dat probleem op te lossen willen we in die gevallen ruis toevoegen. Ook zijn er gevallen waarin de niet-integer gevallen echte besparingen opleveren. We willen zo'n gevel construeren. Vooral van dat laatste, vraag ik me af heo ik dat het beste aan kan pakken. Normaal los je een vergelijking

\(x=f(y)\)

op door iets van een

\(f^-1(f(y))\)

uit te rekenen. Hier lijkt dat te moeilijk. Hoe zou het wel kunnen? Wat is een goede weg om dit soort, ik noem ze invers-algoritmische problemen op te lossen?

[timwaagh]

Ik ben helemaal mijn kostenfunctie vergeten. het probleem is het minimaliseren van de kosten gegeven door

\(c_1x_1 + ... + c_n x_n\)

onder de genoemde voorwaarden.