Springen naar inhoud

[algoritmiek/lineair programmeren]integer oplossingen uit lp probleem


  • Log in om te kunnen reageren

#1

timwaagh

    timwaagh


  • >250 berichten
  • 293 berichten
  • Ervaren gebruiker

Geplaatst op 20 juli 2009 - 16:44

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 LaTeX 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 LaTeX . Ook moet elk van de m incidenten precies een keer op de route liggen. Dit geeft m beperkingen van het type LaTeX . 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

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

timwaagh

    timwaagh


  • >250 berichten
  • 293 berichten
  • Ervaren gebruiker

Geplaatst op 20 juli 2009 - 21:03

???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 LaTeX op door iets van een LaTeX 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?

#3

timwaagh

    timwaagh


  • >250 berichten
  • 293 berichten
  • Ervaren gebruiker

Geplaatst op 21 juli 2009 - 11:14

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





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures