Sammanfattning I heltal linjär programmering (ILP), formulera en \bra" modell är av avgörande betydelse för att lösa den modell 1]. I detta dokument börjar vi med en matematisk analys av strukturen på uppdrag, timing och resursbegränsningar i hög nivå syntes, och sedan utvärdera strukturen i schemaläggning polytop beskrivs av dessa begränsningar. Vi visar sedan hur strukturen på begränsningarna kan utnyttjas för att utveckla en välstrukturerad ILP-formulering, som kan tjäna som en solid teoretisk grund för framtida förbättringar. Som en början i den riktningen presenterar vi också två metoder för att ytterligare strama åt formuleringen. Detta dokument är tvåfaldigt: 1) det ger den första formella analysen av begränsningarnas struktur, och det visar hur man kan utnyttja denna struktur i en väl utformad ILP-formulering, och 2) det visar hur man ytterligare förbättrar en välstrukturerad formulering genom att lägga till nya giltiga ojämlikheter.
Chaudhuri m.fl. REF tillhandahåller en ingående formell analys av begränsningarnas struktur och visar hur denna struktur kan tillämpas i en väl utformad ILP-formulering, såsom schemaläggningsproblemet.
Analyzing and Exploiting the Structure of the Constraints in the ILP Approach to the Scheduling Problem
{'venue': 'IEEE Transactions on VLSI Systems', 'journal': None, 'mag_field_of_study': ['Computer Science']}