Polyhedra and algorithms for problems bridging notions of connectivity and independence

Abstract

I denne avhandlinga interesserer vi oss for å finne delgrafer som svarer til utvalgte modeller for begrepene sammenheng og uavhengighet. I korthet betyr dette stabile (også kalt uavhengige) mengder med gitt kardinalitet, stabile (også kalt konfliktfrie) spenntrær og pardannelser (eller uavhengige kantmengder) som induserer en sammenhengende delgraf. Dette er kombinatoriske strukturer som kan generaliseres til ulike modeller for nettverksdesign innen telekommunikasjon og forsyningsvirksomhet, plassering av anlegg, fylogenetikk, og mange andre applikasjoner innen operasjonsanalyse og optimering.

Vi argumenterer for at de valgte strukturene reiser interessante forskningsspørsmål, og vi bidrar med forbedret matematisk forståelse av selve strukturene, samt forbedrede algoritmer for å takle de tilhørende kombinatoriske optimeringsproblemene. Med det mener vi metoder for å identifisere en optimal struktur, forutsatt at elementene som danner dem (hjørner eller kanter i en gitt graf) er tildelt verdier. Forskninga vår omfatter ulike områder innenfor algoritmer, kombinatorikk og optimering. De fleste resultatene omhandler det å finne bedre beskrivelser av de geometriske strukturene (nemlig 0/1-polytoper) som representerer alle mulige løsninger for hvert av problemene. Slike forbedrede beskrivelser oversettes til lineære ulikheter i heltallsprogrammeringsmodeller, noe som igjen gir mer effektive beregningsresultater når man løser referanseinstanser av hvert problem.

Vi påpeker gjentatte ganger betydninga av å dele kildekoden til implementasjonen av alle utviklede algoritmer og verktøy når det foreslås nye modeller og løsningsmetoder for heltallsprogrammering og kombinatorisk optimering. Kodearkivene våre inkluderer fullstendige implementasjoner, utformet med effektivitet og modulær design i tankene, og fremmer dermed gjenbruk, videre forskning og nye anvendelser innen forskning og utvikling.

We are interested in finding subgraphs that capture selected models of connectivity and independence. In short: fixed cardinality stable (or independent) sets, stable (or conflict-free) spanning trees, and matchings (or independent edge sets) inducing a connected subgraph. These are combinatorial structures that can be generalized to a number of models across network design in telecommunication and utilities, facility location, phylogenetics, among many other application domains of operations research and optimization.

We argue that the selected structures raise appealing research questions, and seek to contribute with improved mathematical understanding of the structures themselves, as well as improved algorithms to face the corresponding combinatorial optimization problems. That is, methods to identify an optimal structure, assuming the elements that form them (vertices or edges in a given graph) have a weight.

Our research spans different lines within algorithmics, combinatorics and optimization. Most of the results concern finding better descriptions of the geometric structures (namely, 0/1-polytopes) that represent all feasible solutions to each of the problems. Such improved descriptions translate to linear inequalities in integer programming formulations which, in turn, provide stronger computational results when solving benchmark instances of each problem.

We repeatedly remark the importance of sharing an open-source implementation of all algorithms and tools developed when proposing new models and solution methods in integer programming and combinatorial optimization. Our code repositories include full implementations, crafted with efficiency and modular design in mind, thus fostering reuse, further research and new applications in research and development.