Vi föreslår en mycket enkel förkonditioneringsmetod för heltal programmering genomförbarhetsproblem: ersätta problemet där U är en unimodulär matris beräknas via basreduktion, för att göra kolumnerna i AU kort (dvs., har liten Euclidean norm), och nästan ortogonal (se t.ex., [26], [25] ). Vårt tillvägagångssätt kallas kolonnbasminskning, och omformuleringen kallas för omformulering av avståndsrymden. Det motiveras av den teknik som föreslås för jämställdhetsbegränsade IPs av Aardal, Hurkens och Lenstra. Vi föreslår också en förenklad metod för att beräkna deras omformulering. Vi studerar också en familj av IP-fall, så kallade nedbrytbara Knapsack problem (DKPs). DKPs generaliserar de fall som föreslås av Jeroslow, Chvátal och Todd, Avis, Aardal och Lenstra, och Cornuéjols et al. De är knapsack problem med en begränsning vektor av formen pM + r, med p > 0 och r integral vektorer, och M ett stort heltal. Om parametrarna är lämpligt valda i DKPs, vi bevisa • hårdhetsresultat, när gren-och-bundet förgrening på enskilda variabler tillämpas, • att de är enkla, om en gren på begränsningen px istället, och • att förgrening på de sista variablerna i antingen avståndsrymden eller AHL omformuleringar motsvarar förgrening på px i det ursprungliga problemet. Vi tillhandahåller också recept för att generera sådana fall. Vår beräkningsstudie bekräftar att beteendet hos de studerade instanserna i praktiken är som förutsägs av teorin.
Vår omformulering av MIP-modellen för NPP är en generalisering av förkonditioneringsmetoden för IP:er som kallas kolonnbasreduktion, som föreslogs tidigare av den första författaren och Pataki REF, till fallet med MIP:er.
Column basis reduction, and decomposable knapsack problems
{'venue': 'Discrete Optimization Volume 6, Issue 3, August 2009, Pages 242-270', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}