Snitplansmetoden

Snitplansmetoden (engelsk: cutting plane method) er en metode som benyttes til iterativt at styrke en matematisk formulering af et problem ved hjælp af lineære uligheder. Disse uligheder kaldes snit (engelsk: cuts) idet de snitter noget af det brugbare område af. Snitplansmetoden er oftest brugt i forbindelse med heltalsprogrammering hvor en funktion ønskes minimeret/maksimeret over heltallene i en given mængde. Metoden bruges inden for disciplinen matematisk optimering eller matematisk programmering.

Metoden er som nævnt en iterativ proces, hvor man i en given iteration løser en såkaldt lineær relaksering (engelsk: linear relaxation) af det givne heltalsprogram. Teorien bag lineær programmering (engelsk: linear programming) fortæller os, at givet at det lineære program har en optimal løsning og at det brugbare område ikke indeholder en linje, så kan en optimal løsning findes i et hjørnepunkt af det brugbare område. Når en optimal løsning til det lineære program er fundet, testes denne løsning for om den er heltallig. Hvis det er tilfældet, er denne løsning optimal til det oprindelige heltalsprogram. Hvis der derimod findes en variabel som skal være heltallig, men som er en brøk, fortæller teorien om konvekse mængder, at der eksisterer en ulighed, som separerer dette givne hjørnepunkt fra det konvekse hylster af heltallene i det brugbare område. At finde en sådan ulighed kaldes separationsproblemt (engelsk:separation problem) og den givne ulighed kaldes et snit. Ideen er så at tilføje denne nyfundne ulighed til det oprindelige lineære program for så at genløse problemet. Dette gentages indtil en optimal heltalsløsning er fundet.

Teori 
Lad  være det brugbare område for et lineært blandet heltalsprogram. Så kan vi skrive  som

For at gøre den følgende præsentation uafhængig starter vi med at definere den lineære relaksering af  som 

hvilket vil sige, at  blot er  hvor vi har relakseret heltalskravet for de før heltallige variable. Vi får således, at 

På denne måde får vi, at hvis vi maksimere en funktion over  i stedet for  får vi et optimistisk bud på den optimale løsningsværdi for det blandede heltalsprogram. Dette skyldes, lidt simpelt sagt, at vi kan vælge mellem flere løsninger i  end i . Der er dog den fordel, at maksimering af en lineær funktion over den linære relaksering er nemt sammelignet med at gøre det samme over  (et lineært program kan under milde antagelser løses i polynomiel tid ved hjælp Ellipse-metoden hvorimod løsning af generelle blandede heltalsprogrammer er NP-hård). Fra teorien om konvekse mængder ved vi, at det konvekse hylster af  har heltalshjørnepunkter. Lad i det følgende det konvekse hylster af  være givet som  At  har heltalshjørner betyder, at vi principielt kan løse det blandede heltalsprogram

som det lineære program

Det er dog ikke helt trivielt hvorledes man skulle finde en repræsentation af . Vi kan dog ved hjælp af snitplaner (i teorien) lave en repræsentation af den relevante del af . Snitplansmetoden løser først den lineære relaksering af heltalsprogrammet

Det vil sige, at vi har droppet heltals kravene. Hvis den optimal løsning  er heltallig, kan vi stoppe med denne løsning som en optimal løsning til det blandede heltalsprogram (da  er et optimistisk bud på den optimale løsningsværdi har vi at  for all  og da  er heltallig er  hvorved  er optimal). Ellers er målet nu at finde en ulighed  således, at  er valid for alle punkter i , men sådan at . Når en sådan ulighed er fundet tilføjes denne til matricen  og det nu opdaterede lineære program løses igen. Processen fortsættes til man har en heltalsløsning eller til man ikke kan separere flere uligheder. Skematisk kan dette opstilles på følgende måde

 Løs den lineære relaksering. Lad  være en optimal løsning.
 Hvis  er heltallig stop da;  er en optimal løsning til det blandede heltalsprogram.
 Ellers find en lineær ulighed som er valid for alle heltalsløsninger til det blandede haltalsprgram men som er brudt af . Tilføj denne til den lineære relaksering. Gå til 1..

I praksis benytter man sjældent den rene form af snitplansmetoden men kombinerer den i stedet med for eksempel branch-and-bound eller branch-and-price. Ofte separeres en bestemt type problemspecifikke uligheder som man ved virker godt for det givne problem. Det er dog vist, at under tekniske antagelser konvergerer snitplansmetoden mod en optimal løsning til det blandede heltalsprogram.

Chvatal-Gomory-snit 
En meget simpel måde at finde valide snitplaner på, er ved at danne en vægtet sum af rækkerne i matricen  for så at runde de resulterende coefficienter ned til nærmeste hele tal. For at være mere præcis, lad 

være den brugbare mængde for et heltalsproblem. Endvidere lad  være en vektor med samme antal indgange som der er rækker i matricen . Da vil 

være en brugbar ulighed for . Da der for alle søjlerne i  gælder  får vi, at 

ligeledes er en valid ulighed for  (vær opmærksom på, at  angiver det største hele tal mindre end ). Vi kan nu observere, at da alle koefficienterne på venstre side i den ovenstående ulighed er heltallige og at variablene også er heltallige, så vil venstresiden i uligheden altid være heltallig. Det betyder, at vi også kan runde højresiden til største heltal mindre end . På denne måde opnås den valide ulighed
.
Denne nye ulighed kan nu tilføjes det oprindelige system og en ny vægt-vektor  kan nu vælges. Ved at variere  opnåes det der kaldes den første Chvatal-afslutning (engelsk: first Chvatal closure) af . Vi opnår således

Det vil altså sige, at vi opnår en bedre beskrivelse af  ved hjælp af den første Chvatal afslutning end vi gør ved den lineære relaksering. Vi kan dog ikke forvente, at den første Chvátal afslutning er identisk med det konvekse hylster af .

Desværre er det et NP-hårdt spørgsmål, om der eksisterer et validt Chvátal-Gomory-snit som separarer den nuværende løsning til den lineære relaxering fra , hvorfor det også er NP-hårdt at optimere over den resulterende polytop . For en fremgangsmåde til at løse separationsproblemet for Chvatal snit henvises der til den nyligt udgivne artikel af Fischetti og Lodi hvor en separationsprocedure er givet og eksperimentelle resultater der underbygger disse snits anvendelighed er forelagt.

Cover snit/uligheder 
I dette afsnit vil cover uligheder for det brugbare område til det meget studerede rygsækproblem (engelsk: knapsack problem) blive udledt. Vi starter med at definere rygsækproblemet: Vi er givet  artikler som vi ønsker at fylde i en rygsæk. Hver artikel  har en vægt/størrelse her kaldet  og en værdi, her kaldet . Rygsække har en kapacitet,  som ikke kan overskrides. Rygsækproblemet er således at maksimere ryksækkens værdi uden at overskride kapaciteten. Problemet kan opskrives matematisk som

hvor  hvis artikel  kommes i rygsækken og nul ellers. Lad nu  være sådan at . Da kalder vi  et cover af rygsækken. Det skulle være åbenlyst at vi ikke kan putte alle artiklerne fra  i rygsækken uden at kapacitetsbegrænsningen bliver brudt. Lader vi så  være antallet af elementer i en mængde  opnår vi følgende valide ulighed for rygsæk problems:

som blot udtrykker, at ikke alle artikler i  kan puttes i rygsækken samtidig. Hvis  er således, at vi ikke kan fjerne en artikel uden at  taber sin egenskab af at være et cover, så siger vi at  er et minimalt cover. Matematisk er  et minimalt cover hvis følgende to betingelser er opfyldte:
 
 
Hvis vi såldes ved, at  er et minimalt cover kan vi udlede en stærkere ulighed ved at betragte 's udvidelse (engelsk: extension):

Da vi ved, at vi ikke kan putte alle artiklerne fra  i ryksækken ved vi også, at vi ikke kan lave en kombination af artikler fra  med mere en  elementer uden at ryksækkens kapacitet bliver brudt. Derfor er den udvidede cover ulighed 

ligeledes valid for det brugbare område for rygsækproblemet. Man bør notere sig, at man kan benytte cover uligheder som snitplaner for mange heltalsproblemer. Så snart det beskrivelsen af det brugbare område indeholder en ulighed tilsvarende kapacitetsbegrænsningen i rygsækproblemet, kan cover uligheder benyttes.

Separation af cover uligheder 
I dette afsnit antager vi, at vi har en vektor  som vi gerne vil separare fra det konvekse hylster af heltalsløsninger til rygsækproblemet vha. en cover ulighed. For at finde en cover ulighed som er mest brudt, kan vi notere os, at 

Det betyder, at hvis vi kan finde et cover , som opfylder  så har vi fundet et cover som separerer  fra det konvekse hylster af heltalsløsninger til rygsækproblemet. Den mest brudte cover-ulighed finder vi således ved at løse optimerings problemet

En optimal løsning til dette problem, lad os kalde den  vil således definere et cover givet ved

Hvis den optimale løsningsværdi  er strengt mindre end 1, da separerer den resulterende cover ulighed 

punktet  fra det konvekse hylster af heltalsløsniger til rygsækproblemt.

Man bør notere sig følgende: For at finde den mest brudte cover ulighed skulle heltalsprogrammet 

løses. Hvis vi komplimentere variablene , substituerer i ovenstående heltalsprogram og flytter lidt rundt på tingene opnår vi følgende optimeringsproblem

hvor . Dette er præcis et rygsækproblem i variablene  hvorfor det altså kræver at vi løser et rygsækproblem for at finde en ulighed til rygsækproblemet vi gerne ville løse. Derfor er det heller ikke beregningsmæssigt forsvarligt, at benytte sig af snitplansmetoden baseret på cover uligheder hvis man ønsker at løse rygsækproblemet. Hvis man nu derimod har et meget svært problem med tusindvis af lineære uligheder, kan man benytte cover uligheder som en del af snitplansmetoden til at styrke sin formulering.

Referencer 

Optimeringsalgoritmer og metoder