Skärplanens

Skärplanen, ofta benämnda cutting planes i engelskspråkig litteratur, är ett begrepp inom optimering och beräkning som används för att förbättra lösningar av kontinuerliga och heltalsproblem. Inom heltals- och mixed-integer programming används skärplanen för att förkorta eller stärka den linjära avslappningen av ett problem. Genom att införa nya linjära ojämlikheter som avskär en del av lösningsrymden kan man exkludera oacceptabla lösningar utan att utesluta giltiga heltalslösningar.

Historiskt utgör skärplanen en central del av så kallade cutting-plane-metoder. Konceptet introducerades av Ralph Gomory i slutet av 1950- och början av 1960-talen och har sedan dess utvecklats vidare av bland andra Chvátal, Gomory och Cook med kollegor. Skärplanerna används ofta i kombination med andra metoder, framför allt i branch-and-bound/-cut-algoritmer, för att effektivt täta relaxationen innan slutlig lösning hittas.

Skärplanens konstruktioner varierar mellan olika tillvägagångssätt. Typiska exempel är Gomory-skärplan, split-skärplan och lift-and-project-skärplan. Dessa planer kan genereras från den aktuella LP-lösningen eller från problemstrukturen och syftar till att reducera sökområdet utan att beröva möjligheten att hitta giltiga heltalslösningar.

I svensk språkbruk används termen främst inom teknisk och matematisk optimering. Förväxling kan uppstå med geometri där ett skärplan hänvisar till ett plan som skär igenom ett objekt och bildar tvärsnitt, men i optimizationstermerna refererar skärplanen till den reglering av lösningsrymden som stärker problemet.