En vanlig teknik för att generera övre gränser på optimal av en quadratic 0-1 maximization problem är att överväga en linjär majorant (LM) av den quadratic objektiva funktionen f och sedan lösa motsvarande linjär avslappning. Flera dokument har övervägt LM: s erhållna genom terminslimning, men möjligheten att begränsa grupper av termer samtidigt verkar inte ha utforskats hittills. I detta dokument utvecklar vi denna idé genom att föreslå följande strategi: För det första skapas en lämplig samling av "elementära" kvadratiska funktioner med få variabler (vanligtvis 3 eller 4). Alla koefficienter för en sådan funktion (block) är antingen 1 eller -1, och överensstämmer med motsvarande koefficienter för den givna quadratic funktionen. Därefter, för varje block, en tightaste LM (dvs. en som har samma värde som blocket i så många punkter som möjligt), eller en närmaste LM (dvs, en minimera summan av slacks) beräknas. Detta kan åstadkommas genom lösningen av en liten blandad-integer program, eller en liten linjär program, respektive. Slutligen är den objektiva funktionen skriven som en viktad summa av block, med icke-negativa vikter. I detta uttryck ersätts varje block med motsvarande LM, en LM f kan erhållas. Vi ska välja vikterna i denna process så att det maximala värdet av den resulterande linjära funktionen är så litet som möjligt. Detta motsvarar ett storskaligt linjärt program, som kan lösas genom kolumngenerering. De uppmuntrande resultaten av en preliminär uppsättning numeriska tester presenteras.
Boros, Lari och Simeone REF föreslår att beräkna en övre gräns för quadratic 0-1 maximization problem genom att skriva den objektiva funktionen som en kombination av "små" quadratic funktioner vars högsta beräknas exakt.
BLOCK LINEAR MAJORANTS IN QUADRATIC 0-1 OPTIMIZATION
{'venue': None, 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}