Relaxation

Ett heltalsproblem där de röda prickarna representerar tillåtna lösningar, kan relaxeras med exempelvis det röda området, eller det blå området (där alla punkter i områdena är tillåtna lösningar).

Relaxation är en term inom optimeringslära som betyder att man lättar på eller helt tar bort vissa av villkoren som finns på ett optimeringsproblem. Det kan exempelvis innebära att man istället för ett problem där en variabel ${\textstyle x}$ är heltalig, låter ${\textstyle x}$ anta alla reella värden.

Relaxeringar brukar göras för att det nya problemet man får är enklare att hantera, mer lättlösligt, gärna ett konvext problem.

Eftersom man vid en relaxering tillåter fler värden än tidigare (man utökar mängden tillåtna lösningar) utan att ta bort några tillåtna lösningar ur ursprungsproblemet, så kommer det relaxerade problemet alltid att ge ett minst lika bra resultat som ursprungsproblemet. Man säger att en relaxation ger en optimistisk skattning av optimalvärdet.

Om optimallösningen i relaxationen är en tillåten lösning i ursprungsproblemet så är den även optimallösningen till det problemet.

Oftast är optimallösningen till det relaxerade problemet en otillåten lösning till ursprungsproblemet. Man kan då behöva göra kapningar/snitt/beskärningar eller förgreningar av det tillåtna området för att bli av med punkten som var optimum och leta upp en ny optimal lösning. Detta kan upprepas tills den funna optimallösningen är en tillåten lösning i ursprungsproblemet.