Snitplansmetoden

Skabelon:Eftersyn 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

$𝒳:=\{x\in {ℝ}^n:Ax\le x,l_j\le x_j\le u_j,x_j\in {\mathbb{Z}}^n\text{ for nogle }j\in \{1,\dots ,n\}\}$

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

$\overline{𝒳}:=\{x\in {ℝ}^n:Ax\le b,l_j\le x_j\le u_j\}$

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

$𝒳\subseteq \overline{𝒳}$

På denne måde får vi, at hvis vi maksimere en funktion over $\overline{𝒳}$ 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 $\overline{𝒳}$ 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). 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 $\text{conv}(𝒳).$ At $\text{conv}(𝒳)$ har heltalshjørner betyder, at vi principielt kan løse det blandede heltalsprogram

$\max \{c^{T}x:x\in 𝒳\}$

som det lineære program

$\max \{c^{T}x:x\in \text{conv}(𝒳)\}$

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

$\max \{c^{T}x:x\in \overline{𝒳}\}$

Det vil sige, at vi har droppet heltals kravene. Hvis den optimal løsning $x^{*}$ er heltallig, kan vi stoppe med denne løsning som en optimal løsning til det blandede heltalsprogram (da $c^T{x}^{*}$ er et optimistisk bud på den optimale løsningsværdi har vi at $c^T{x}^{*}\ge c^{T}x$ for all $x\in 𝒳$ og da $x^{*}$ er heltallig er $x^{*}\in 𝒳$ hvorved $x^{*}$ er optimal). Ellers er målet nu at finde en ulighed $\pi x\le {\pi }_0$ således, at $\pi x\le {\pi }_0$ er valid for alle punkter i $\text{conv}(𝒳)$, men sådan at $\pi x^{*}>{\pi }_0$. Når en sådan ulighed er fundet tilføjes denne til matricen $(A,b)$ 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 $x^{*}$ være en optimal løsning.
2. Hvis $x^{*}$ er heltallig stop da; $x^{*}$ 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 $x^{*}$. 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 $A$ for så at runde de resulterende koefficienter ned til nærmeste hele tal. For at være mere præcis, lad

$𝒳:=\{x\in {\mathbb{Z}}^n:Ax\le x\}$

være den brugbare mængde for et heltalsproblem. Endvidere lad $u\in {ℝ}_{+}^m$ være en vektor med samme antal indgange som der er rækker i matricen $A$. Da vil

$u^{T}Ax\le u^{T}b$

være en brugbar ulighed for $\text{conv}(𝒳)$. Da der for alle søjlerne i $A$ gælder $\lfloor u^T{A}_j\rfloor \le u^T{A}_j$ får vi, at

$\sum _{j=1}^n\lfloor u^T{A}_j\rfloor x_j\le u^{T}b$

ligeledes er en valid ulighed for $\text{conv}(𝒳)$ (vær opmærksom på, at $\lfloor y\rfloor$ angiver det største hele tal mindre end $y$). 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 $u^{T}b$. På denne måde opnås den valide ulighed

$\sum _{j=1}^n\lfloor u^T{A}_j\rfloor x_j\le \lfloor u^{T}b\rfloor$.

Denne nye ulighed kan nu tilføjes det oprindelige system og en ny vægt-vektor $u$ kan nu vælges. Ved at variere $u$ opnås det der kaldes den første Chvatal-afslutning (engelsk: first Chvatal closure) af $\{x\in {ℝ}^n:Ax\le b\}$. Vi opnår således

$\begin{array}{cc}\{x\in {ℝ}^n:Ax\le b\}& \supseteq \{x\in {ℝ}^n:Ax\le b,\sum _{j=1}^n\lfloor u^T{A}_j\rfloor x_j\le \lfloor u^{T}b\rfloor ,\mathrm{\forall }u\in {ℝ}_{+}^m\}\\ & \supseteq \text{conv}(𝒳)\end{array}$

Det vil altså sige, at vi opnår en bedre beskrivelse af $\text{conv}(𝒳)$ 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 $\text{conv}(𝒳)$, 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 $n$ artikler som vi ønsker at fylde i en rygsæk. Hver artikel $i$ har en vægt/størrelse her kaldet $w_i$ og en værdi, her kaldet $p_i$. Rygsække har en kapacitet, $c$ som ikke kan overskrides. Rygsækproblemet er således at maksimere ryksækkens værdi uden at overskride kapaciteten. Problemet kan opskrives matematisk som

$\max \sum _{i=1}^n{p}_i{x}_i\text{ under bibetingelse af: }\sum _{i=1}^n{w}_i{x}_i\le c\text{ og }x\in \{0,1{\}}^n$

hvor $x_i=1$ hvis artikel $i$ kommes i rygsækken og nul ellers. Lad nu $𝒞\subseteq \{1,\dots ,n\}$ være sådan at $\sum _{i\in 𝒞}{w}_i>c$. 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å $|S|$ være antallet af elementer i en mængde $S$ opnår vi følgende valide ulighed for rygsæk problems:

$\sum _{i\in 𝒞}{x}_i\le |𝒞|-1$

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. $\sum _{i\in 𝒞}{w}_i>c$
2. $\sum _{i\in 𝒞\setminus \{j\}}{w}_i\le c,\mathrm{\forall }j\in 𝒞$

Hvis vi således ved, at $𝒞$ er et minimalt cover kan vi udlede en stærkere ulighed ved at betragte $𝒞$'s udvidelse (engelsk: extension):

$E(𝒞)=𝒞\cup \{i\in ̸𝒞:w_i\ge \underset{j\in 𝒞}{\max }{w}_j\}$

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 $E(𝒞)$ med mere en $|𝒞|-1$ elementer uden at ryksækkens kapacitet bliver brudt. Derfor er den udvidede cover ulighed

$\sum _{i\in E(𝒞)}{x}_i\le |𝒞|-1$

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 $\hat{x}\in {ℝ}^n$ 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

$\sum _{i\in 𝒞}{x}_i\le |𝒞|-1\iff \sum _{i\in 𝒞}(1-x_i)\ge 1$

Det betyder, at hvis vi kan finde et cover $𝒞$, som opfylder $\sum _{i\in 𝒞}(1-{\hat{x}}_i)<1$ så har vi fundet et cover som separerer $\hat{x}$ 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

$\min \sum _{i=1}^n(1-{\hat{x}}_i)z_i,\text{ u.b. }\sum _{i=1}^n{w}_i{z}_i\ge c+1,\text{ og }z\in \{0,1{\}}^n$

En optimal løsning til dette problem, lad os kalde den $z^{*}$ vil således definere et cover givet ved

$𝒞=\{i\in \{1,\dots ,n\}:z_i=1\}$

Hvis den optimale løsningsværdi ${\gamma }^{*}=\sum _{i=1}^n(1-{\hat{x}}_i)z_i^{*}$ er strengt mindre end 1, da separerer den resulterende cover ulighed

$\sum _{i\in 𝒞}{x}_i\le |𝒞|-1$

punktet $\hat{x}$ 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

$\min \sum _{i=1}^n(1-{\hat{x}}_i)z_i,\text{ u.b. }\sum _{i=1}^n{w}_i{z}_i\ge c+1,\text{ og }z\in \{0,1{\}}^n$

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

$\sum _{i=1}^n(1-{\hat{x}}_i)-\max \sum _{i=1}^n(1-{\hat{x}}_i)y_i\text{ u.b. }\sum _{i=1}^n{w}_i{y}_i\le \overline{c}\text{ og }y\in \{0,1{\}}^n$

hvor $\overline{c}=\sum _{i=1}^n{w}_i-(c+1)$. Dette er præcis et rygsækproblem i variablene $y$ 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.