Abstrakt. Det har erkänts nyligen att för att representera en polyhedron som projektion av en högre dimension, men enklare, polyhedron, är ett kraftfullt verktyg i polyhedral combinatorics. Vi utvecklar en allmän metod för att konstruera högre-dimensionella polyhedra (eller, i vissa fall, konvexa uppsättningar) vars projektion ungefär motsvarar konvexa skrov av 0-1 värderade lösningar av ett system av linjär ojämlikhet. Ett viktigt drag i dessa approximationer är att man kan optimera någon linjär objektiv funktion över dem i polynom tid. I det speciella fallet med vertex förpackning polytope, får vi en sekvens av system av ojämlikhet, så att redan det första systemet inkluderar klick, udda hål, udda antihål, hjul, och ortogonalitet begränsningar. Särskilt för perfekta (och många andra) grafer, detta första system ger vertex förpackning polytop. För olika klasser av grafer, inklusive t-perfekta grafer, följer att den stabila uppsättningen polytop är projektionen av en polytop med ett polynom antal fasetter. Vi diskuterar också en förlängning av metoden, som etablerar ett samband med vissa submodulära funktioner och Möbius-funktionen av en lattice. 1980 Ämnesindelning i matematik: 05C35, 90C10, 90C27. Nyckelord och fraser: polyhedron, kon, vertex förpackning polytop, perfekt graf, Möbius funktion. 1 En av de viktigaste metoderna i combinatorial optimering är att representera varje genomförbar lösning av problemet med en 0-1 vektor (vanligen förekomsten vektor för lämplig uppsättning), och sedan beskriva konvexa skrov K av lösningarna med ett system av linjära ojämlikheter. I de finaste fallen (t.ex. i fallet med bipartit matchning problem) vi få ett system som har polynom storlek (mätt i den naturliga "storlek" n av problemet). I ett sådant fall kan vi beräkna maximum av någon linjär objektiv funktion i polynom tid genom att lösa ett linjärt program. I andra fall har dock konvexa skrov av genomförbara lösningar exponentiellt många fasetter och kan därför endast beskrivas med ett linjärt program av exponentiell storlek. För många kombinatoriska optimeringsproblem (inklusive de som kan lösas i polynom tid), är denna exponentiellt stora uppsättning linjära ojämlikheter fortfarande "fin" i en eller annan bemärkelse. Vi nämner två möjliga begrepp av "niceness": -Med tanke på en ojämlikhet i systemet, det finns ett polynom storlekscertifikat av det faktum att det är giltigt för K. Om så är fallet, problemet med att avgöra om en given vektor i K är i komplexitet klass co-NP. -Det finns en polynom tid separation algoritm för systemet; det vill säga, med tanke på en vektor, kan vi kontrollera i polynom tid om det uppfyller systemet, och om inte, kan vi hitta en ojämlikhet i systemet som kränks. Det följer av de allmänna resultaten av ellipsoidmetoden (se Grötschel, Lovász och Schrijver 1988) att varje linjär objektiv funktion kan optimeras över K i polynomtid. Många viktiga teorem i kombinatorisk optimering ger sådana "fina" beskrivningar av polyhedra. Viktiga exempel på polyhedra med "nice" beskrivningar är matchande polyhedra, matroid polyhedra, stabil uppsättning polyhedra för perfekta grafer etc. Å andra sidan är stabila uppsättning polyhedra i allmänhet, eller resande säljare polyhedra, inte kända för att ha "fina" beskrivningar (och förmodligen inte har några). Vanligtvis, för att hitta en sådan "fin" beskrivning och för att bevisa dess korrekthet, behöver man ad hoc-metoder beroende på den kombinatoriska strukturen. Man kan dock nämna två allmänna idéer som kan hjälpa till att få sådana linjära beskrivningar: -Gomory-Chvátal nedskärningar. Låt P vara en polytop med integrerade hörn. Anta att vi redan har hittat ett system av linjära ojämlikheter som gäller för P vars integrerade lösningar är exakt den integrerade vektorer i P. Lösningen uppsättningen av detta system är en polytope K som innehåller P som i allmänhet kommer att vara större än P. Vi kan generera ytterligare linjära ojämlikheter som gäller för P (men inte nödvändigtvis för K) enligt följande. Med tanke på en linjär ojämlikhet som gäller för K, där a i är heltal, är ojämlikheten i a i x i ≤ α fortfarande giltig för P men kan eliminera någon del av K. Gomory (1963) använt en särskild version av denna konstruktion i hans heltal programmeringsalgoritm. Om vi tar alla ojämlikheter som kan uppnås på detta sätt, de definierar en polytope K med P  på K. Upprepa detta med K i stället för K vi få K etc. Chvátal (1973) visade att i ett begränsat antal steg får vi själva polytopen P. Tyvärr kan antalet steg vara mycket stort; det beror inte bara på dimensionen utan också på koefficienterna i det system vi börjar med. Ett annat problem med detta förfarande är att det inte finns något effektivt sätt att genomföra det algoritmiskt. I synnerhet, även om vi vet hur man optimerar en linjär objektiv funktion över K i polynom tid (säg, K ges av en explicit, polynom-storlek linjära program), och K = P, vi känner till ingen allmän metod för att optimera en linjär objektiv funktion över P i polynomial tid. -Projection representation (nya variabler). Denna metod har fått mycket uppmärksamhet på senare tid. Tanken är att en projektion av en polytop kan ha fler facetter än polytopen själv. Denna anmärkning tyder på att även om P har exponentiellt många facetter, kanske vi kan representera det som projektion av en polytop Q i högre (men fortfarande polynom) dimension, med endast ett polynom antal facetter. Bland annat har Ball, Liu och Pulleyblank (1987), Maculan (1987), Pulleyblank (1983 1987), Barahona och Mahjoub (1987), Cameron och Edmonds (1988) gett icke-triviala exempel på en sådan representation. Det är lätt att se att en sådan representation kan användas för att optimera linjära objektiva funktioner över P i polynom tid. I negativ riktning, Yannakakis (1988) bevisade att Travelling Salesman polytope och Matching Polytope av kompletta grafer inte kan representeras på detta sätt, förutsatt att representationen är "kanonisk". (Låt P  på IR n och P på IR m vara två polytoper. Vi säger att en projektion representation π : P → P är kanonisk om gruppen av isometerier av IR n bevara P har en handling som isomerer av IR m bevara P så att projektionen pendlar med dessa handlingar. En sådan representation erhålls t.ex. När nya variabler införs på ett "kanoniskt" sätt - när det gäller den resande försäljarens polytop, kan detta betyda variabler som tilldelas kanter eller vissa andra subgrafer, och begränsningar för dessa nya variabler härrör från lokala egenskaper. Om vi måste börja med en referensorientering, eller med att ange en rot, då den erhållna representationen kommer inte att vara kanonisk.) Inga negativa resultat verkar vara kända utan denna symmetri antagande. Ett sätt att se våra resultat är att vi tillhandahåller en allmän procedur för att skapa sådana lyft. Tanken är att utvidga metoden av Grötschel, Lovász och Schrijver (1981) för att hitta maximal stabil uppsättningar i perfekta grafer till allmänna 0-1 program. Vi representerar en genomförbar delmängd inte genom dess incidens vektor v utan genom matrisen vv T. Detta kvadrater antalet variabler, men i gengäld får vi två nya kraftfulla sätt att skriva ner linjära begränsningar. Projicering tillbaka till det "vanliga" utrymmet, vi får en procedur något 3 liknar Gomory-Chvátal förfarandet: det "skär ner" en konvex uppsättning K till en ny konvex uppsättning K så att alla 0-1 lösningar bevaras. I motsats till GomoryChvátal skär, dock, någon subrutin för att optimera en linjär objektiv funktion över K kan användas för att optimera en linjär objektiv funktion över K. Dessutom, upprepa proceduren på de flesta n gånger, vi få konvex skrov P av 0-1 vektorer i K. Vår metod är nära relaterad till nyligen arbete av Sherali och Adams (1988). De introducerar nya variabler för produkter av de ursprungliga och karakterisera konvexa skrovet, i detta högdimensionella utrymme, av vektorer associerade med 0-1 lösningar av det ursprungliga problemet. På detta sätt får de en sekvens av avkopplingar av 0-1 optimeringsproblem, varav den första är i huvudsak N-operatören infördes i avsnitt 1 nedan. Ytterligare medlemmar av de två sekvenserna av avkopplingar är olika, men nära besläktade; några av våra resultat i avsnitt 3, särskilt formel (6) och Theorem 3.3, följer direkt från deras arbete. Metoden är också relaterad till (men skiljer sig från) det senaste arbetet av Pemantle, Propp och Ullman (1989) på tensor befogenheter linjära program. I avsnitt 1 beskriver vi metoden i allmänhet och bevisar dess grundläggande egenskaper. Avsnitt 2 innehåller applikationer till vertex förpackningsproblem, en av de bäst studerade kombinatoriska optimeringsproblem. Det kommer att visa sig att vår metod ger i ett steg nästan alla kända klasser av fasetter av vertex packning polytop. Det kommer att följa i synnerhet att om en graf har egenskapen att dess stabila uppsättning polytop beskrivs av klick, udda hål och udda antihål begränsningar, då dess maximala stabila uppsättning kan hittas i polynom tid. I avsnitt 3 sätter vi dessa resultat i ett bredare sammanhang, genom att höja dimensionen ännu högre. Vi introducerar exponentiellt många nya variabler; i detta högdimensionella utrymme kan man uppnå ganska enkla och eleganta polyhedralresultat. Huvuddelen av arbetet är att "push ner" ojämlikheterna till en låg dimension, och att utföra algoritmer med endast ett polynom antal variabler och begränsningar. Det kommer att visa sig att metoderna i avsnitt 1, liksom andra konstruktioner som TH(G) som beskrivs i Grötschel, Lovász och Schrijver (1986, 1988) följer på ett naturligt sätt. Uppfattat. Den första författaren är tacksam mot institutionen för kombinatorik och optimering av University of Waterloo för sin gästfrihet medan denna uppsats skrevs. Diskussionerna med Mike Saks och Bill Pulleyblank om ämnet papper var mest stimulerande.
Den matchande polytopen studerades först i lift-och projektsammanhang av Lovász och Schrijver REF, som poserade problemet med att bestämma rangen (dvs. det minsta antalet rundor tills heltal polytope nås) för kompletta grafer Kn.
Cones of matrices and set-functions and 0-1 optimization
{'venue': 'SIAM JOURNAL ON OPTIMIZATION', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}