Denne artikel bør gennemlæses af en person med fagkendskab for at sikre den faglige korrekthed.

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[1]. 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[2]. 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 redigér

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 lineære relaksering er nemt sammenlignet 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[3]). Fra teorien om konvekse mængder ved vi, at det konvekse hylster af   har heltalshjørnepunkter[4]. 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

  1. Løs den lineære relaksering. Lad   være en optimal løsning.
  2. Hvis   er heltallig stop da;   er en optimal løsning til det blandede heltalsprogram.
  3. 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.[5]

Chvatal-Gomory-snit redigér

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 koefficienter 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ås det der kaldes den første Chvatal-afslutning (engelsk: first Chvatal closure) af  [6]. 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 separerer den nuværende løsning til den lineære relaxering fra  , hvorfor det også er NP-hårdt at optimere over den resulterende polytop [7]. For en fremgangsmåde til at løse separationsproblemet for Chvatal snit henvises der til den nyligt udgivne artikel af Fischetti og Lodi[8] hvor en separationsprocedure er givet og eksperimentelle resultater der underbygger disse snits anvendelighed er forelagt.

Cover snit/uligheder redigér

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:

  1.  
  2.  

Hvis vi således 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 redigér

I dette afsnit antager vi, at vi har en vektor   som vi gerne vil separere 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 redigér

  1. ^ Bertsimas, D.; Tsitsiklis, J. (1997). Introduction to Linear Optimization., kapitel 2.6 og sætninger heri.
  2. ^ Bazaraa, M.; Sherali, H.; Shetty, C. (2006). Nonlinear Programming: Theory and Algorithms (3. udgave). Theorem 2.4.4
  3. ^ Nemhauser, G.; Wolsey, L. (1988). Integer and Combinatorial Optimization. kapitel I.5 Proposition 5.2.
  4. ^ Nemhauser, G.; Wolsey, L. (1988). Integer and Combinatorial Optimization. kapitel I.4 Theorem 6.3.
  5. ^ Nemhauser, G.; Wolsey, L. (1988). Integer and Combinatorial Optimization. kapitel II.4 afsnit 3
  6. ^ Bertsimas, D.; Weismantel, R. (2005). Optimization over Integers.
  7. ^ Karp, R. M.; Papadimitriou, C. H. (1982). "On linear characterizations of combinatorial optimization problems". SIAM Journal on Computing. 11 (4): 620-632.
  8. ^ Fischetti, M.; Lodi, Andrea (2007). "Optimizing over the first Chvátal closure". Mathematical Programming. 110 (1): 2-20. doi:10.1007/s10107-006-0054-8.