Search

A connected matching in a graph G consists of a set of pairwise disjoint edges whose covered vertices induce a connected subgraph of G. While finding a connected matching of maximum cardinality is a well-solved problem, it is NP-hard to determine an optimal connected matching in an edge-weighted graph, even in the planar bipartite case. We present two mixed integer programming formulations and a sophisticated branch-and-cut scheme to find weighted connected matchings in general graphs. The formulations explore different polyhedra associated to this problem, including strong valid inequalities both from the matching polytope and from the connected subgraph polytope. We conjecture that one attains a tight approximation of the convex hull of connected matchings using our strongest formulation, and report encouraging computational results over DIMACS Implementation Challenge benchmark instances. The source code of the complete implementation is also made available. [ABSTRACT FROM AUTHOR]

Developing a mathematical understanding of autocatalysis in reaction networks has both theoretical and practical implications. We review definitions of autocatalytic networks and prove some properties for minimal autocatalytic subnetworks (MASs). We show that it is possible to classify MASs in equivalence classes, and develop mathematical results about their behavior. We also provide linear-programming algorithms to exhaustively enumerate them and a scheme to visualize their polyhedral geometry and combinatorics. We then define cluster chemical reaction networks, a framework for coarse-graining real chemical reactions with positive integer conservation laws. We find that the size of the list of minimal autocatalytic subnetworks in a maximally connected cluster chemical reaction network with one conservation law grows exponentially in the number of species. We end our discussion with open questions concerning an ecosystem of autocatalytic subnetworks and multidisciplinary opportunities for future investigation. [ABSTRACT FROM AUTHOR]

We consider optimal control problems for partial differential equations where the controls take binary values but vary over the time horizon; they can thus be seen as dynamic switches. The switching patterns may be sub ject to combinatorial constraints such as, e.g., an upper bound on the total number of switchings or a lower bound on the time between two switchings. While such combinatorial constraints are often seen as an additional complication that is treated in a heuristic postprocessing, the core of our approach is to investigate the convex hull of all feasible switching patterns in order to define a tight convex relaxation of the control problem. The convex relaxation is built by cutting planes derived from finite-dimensional pro jections, which can be studied by means of polyhedral combinatorics. A numerical example for the case of a bounded number of switchings shows that our approach can significantly improve the dual bounds given by the straightforward continuous relaxation, which is obtained by relaxing binarity constraints. [ABSTRACT FROM AUTHOR]

Motivated by the problem of bounding the number of iterations of the simplex algorithm, we investigate the possible lengths of monotone paths followed inside the oriented graphs of polyhedra (oriented by the objective function). We consider both the shortest and the longest monotone paths and estimate the monotone diameter and height of polyhedra. Our analysis applies to transportation polytopes, matroid polytopes, matching polytopes, shortest-path polytopes, and the traveling salesman polytope, among others. We begin by showing that combinatorial cubes have monotone diameter and Bland simplex height upper bounded by their dimension and that in fact all monotone paths of zonotopes are no larger than the number of edge directions of the zonotope. We later use this to show that several polytopes have polynomial-size monotone diameter. In contrast, we show that for many well-known combinatorial polytopes, the height is at least exponential. Surprisingly, for some famous pivot rules, e.g., greatest improvement and steepest edge, these same polytopes have polynomial-size simplex paths.

Given a graph G = (V , E) , a subset S ⊆ V is 2- dominating if every vertex in S ¯ has at least two neighbors in S. The minimum cardinality of such a set is called the 2- domination number of G. Consider a process in discrete time that, starting with an initial set of marked vertices S , at each step marks all unmarked vertices having two marked neighbors. In such a process, the minimum number of initial vertices in S such that eventually all vertices are marked is called the P 3 - hull number of G. In this work, we explore a polyhedral relation between these two parameters and, in addition, we provide new families of valid inequalities for the associated polytopes. Finally, we give explicit descriptions of the polytopes associated to these problems when G is a path, a cycle, a complete graph, or a tree. [ABSTRACT FROM AUTHOR]

Many polytopes arising in polyhedral combinatorics are linear projections of higher-dimensional polytopes with significantly fewer facets. Such lifts may yield compressed representations of polytopes, which are typically used to construct small-size linear programs. Motivated by algorithmic implications for the closest vector problem, we study lifts of Voronoi cells of lattices. We construct an explicit d-dimensional lattice such that every lift of the respective Voronoi cell has 2 Ω (d / log d) facets. On the positive side, we show that Voronoi cells of d-dimensional root lattices and their dual lattices have lifts with O (d) and O (d log d) facets, respectively. We obtain similar results for spectrahedral lifts. [ABSTRACT FROM AUTHOR]

This work focuses on the capacitated dispersion problem for which we study several mathematical formulations in different spaces using variables associated with nodes, edges, and costs. The relationships among the presented formulations are investigated by comparing the projections of the feasible sets of the LP relaxations onto the subspace of natural variables. These formulations are then strengthened with families of valid inequalities and variable‐fixing procedures. The separation problems associated with the valid inequalities that are exponential in number are shown to be polynomially solvable by reducing them to longest path problems in acyclic graphs. The dual bounds obtained from stronger but larger formulations are used to improve the strength of weaker but smaller formulations. Several sets of computational experiments are conducted to illustrate the usefulness of the findings, as well as the aptness of the formulations for different types of instances. [ABSTRACT FROM AUTHOR]

Extended formulations are an important tool in polyhedral combinatorics. Many combinatorial optimization problems require an exponential number of inequalities when modeled as a linear program in the natural space of variables. However, by adding artificial variables, one can often find a small linear formulation, i.e., one containing a polynomial number of variables and constraints, such that the projection to the original space of variables yields a perfect linear formulation. Motivated by binary optimal control problems with switching constraints, we show that a similar approach can be useful also for optimization problems in function space, in order to model the closed convex hull of feasible controls in a compact way. More specifically, we present small extended formulations for switches with bounded variation and for dwell-time constraints. For general linear switching point constraints, we devise an extended model linearizing the problem, but show that a small extended formulation that is compatible with discretization cannot exist unless P = NP. [ABSTRACT FROM AUTHOR]

We consider the problem of designing a linear program that has diverse solutions as the right-hand side varies. This problem arises in video game settings where designers aim to have players use different “weapons” or “tactics” as they progress. We model this design question as a choice over the constraint matrix A and cost vector c to maximize the number of possible supports of unique optimal solutions (what we call “loadouts”) of Linear Programs max{c⊤x∣Ax≤b,x≥0}\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\max \{c^\top x \mid Ax \le b, x \ge 0\}$$\end{document} with nonnegative data considered over all resource vectors b. We provide an upper bound on the optimal number of loadouts and provide a family of constructions that have an asymptotically optimal number of loadouts. The upper bound is based on a connection between our problem and the study of triangulations of point sets arising from polyhedral combinatorics, and specifically the combinatorics of the cyclic polytope. Our asymptotically optimal construction also draws inspiration from the properties of the cyclic polytope. [ABSTRACT FROM AUTHOR]

We study a variant of the weighted consecutive ones property problem. Here, a 0/1-matrix is given with a cost associated to each of its entries and one has to find a minimum cost set of zero entries to be turned to ones in order to make the matrix have the consecutive ones property for rows. We investigate polyhedral and combinatorial properties of the problem and we exploit them in a branch-and-cut algorithm. In particular, we devise preprocessing rules and investigate variants of "local cuts". We test the resulting algorithm on a number of instances, and we report on these computational experiments. [ABSTRACT FROM AUTHOR]

In this paper we investigate non-linear matroid optimization problems with polynomial objective functions where the monomials satisfy certain monotonicity properties. Indeed, we study problems where the set of non-linear monomials consists of all non-linear monomials that can be built from a given subset of the variables. Linearizing all non-linear monomials we study the respective polytope. We present a complete description of this polytope. Apart from linearization constraints one needs appropriately strengthened rank inequalities. The separation problem for these inequalities reduces to a submodular function minimization problem. These polyhedral results give rise to a new hierarchy for the solution of matroid optimization problems with polynomial objectives. This hierarchy allows to strengthen the relaxations of arbitrary linearized combinatorial optimization problems with polynomial objective functions and matroidal substructures. Finally, we give suggestions for future work. [ABSTRACT FROM AUTHOR]

Given a bipartite graph G = (V 1 , V 2 , E) , a biclique of G is a complete bipartite subgraph of G , and a biclique partitioning of G is a set A ⊆ E such that the bipartite graph G ′ = (V 1 , V 2 , A) is a vertex-disjoint union of bicliques. The biclique partitioning problem (BPP) consists of, given a complete bipartite graph G = (V 1 , V 2 , E) with edge weights w e ∈ R for all e ∈ E (thus, negative weights are allowed), finding a biclique partitioning A ⊆ E of minimum weight. The bicluster editing problem (BEP) is a variant of the BPP and consists of editing a minimum number of edges of an input bipartite graph G in order to transform its edge set into a biclique partitioning. Editing an edge consists of either adding it to the graph or deleting it from the graph. In addition to the BPP and the BEP, other problems in the literature aim at finding biclique partitionings, and this motivates the study of the biclique partitioning polytope P n m of the complete bipartite graph K n m (i.e., P n m is the convex hull of the incidence vectors of the biclique partitionings of K n m). In this paper we develop such a polyhedral study and show that ladder , bellows , and grid inequalities induce facets of P n m. Our computational results show that these inequalities are very effective in solving the BEP. In particular, they are able to improve the value of the relaxed solution by up to 20%. [ABSTRACT FROM AUTHOR]

Given a graph G = (V, E), a subset S ⊆ V is 2-dominating if every vertex in S¯ has at least two neighbors in S. The minimum cardinality of such a set is called the 2-domination number of G. Consider a process in discrete time that, starting with an initial set of marked vertices S , at each step marks all unmarked vertices having two previously marked neighbors. In such a process, the minimum number of initial vertices in S such that eventually all vertices are marked is called the P 3 -hull number of G. These parameters are relevant both as a generalization of the domination number and in the context of discrete convexities in graphs, particularly the P 3 convexity. In this work, we explore a polyhedral relation between these two parameters and, in addition, we provide new families of valid inequalities for the associated polytopes. Finally, we give explicit descriptions of the polytopes associated to these problems when G is a path, a cycle, or a complete graph. If G is a tree we give the complete description of the associated 2-domination polytope. [ABSTRACT FROM AUTHOR]

The maximum weighted stable set problem in claw-free graphs is a well-known generalization of the maximum weighted matching problem, and a classical problem in combinatorial optimization. In spite of the recent development of fast(er) combinatorial algorithms and some progresses in the characterization of the corresponding stable set polytope, the problem of "providing a decent linear description" for this polytope (Grötschel et al. in Geometric algorithms and combinatorial optimization, Springer, New York, 1988) is still open. The main contribution of this paper is to propose an algorithmic answer to that question by providing a polynomial-time and computationally attractive separation routine for the stable set polytope of claw-free graphs, that only requires a combinatorial decomposition algorithm, the solution of (moderate sized) compact linear programs, and Padberg and Rao's algorithm for separating over the matching polytope. In particular, it is a generalization of the latter and avoids the heavy computational burden of resorting to the ellipsoid method, on which the only poly-time separation routine known so far relied. Besides, our separation routine comes with a 'small' (but not polynomial) extended linear programming formulation and a procedure to derive a linear description of the stable set polytope of claw-free graphs in the original space. [ABSTRACT FROM AUTHOR]

The complete bipartite graph K 1 , 3 is called a claw. A graph is said to be claw-free if it contains no induced subgraph isomorphic to a claw. Given a graph G, the NP-hard Graph Declawing Problem (GDP) consists of finding a minimum set S ⊆ V (G) such that G - S is claw-free. This work develops a polyhedral study of the GDP polytope, expliciting its full dimensionality, proposing and testing five families of facets: trivial inequalities, claw inequalities, star inequalities, lantern inequalities, and binary star inequalities. In total, four Branch-and-Cut algorithms with separation heuristics have been developed to test the computational benefits of each proposed family on random graph instances and random interval graph instances. Our results show that the model that uses a separation heuristics proposed for star inequalities achieves better results on both set of instances in almost all cases. [ABSTRACT FROM AUTHOR]

The problem of deciding if a given triangulation of a sphere can be realized as the boundary sphere of a simplicial, convex polytope is known as the 'Simplicial Steinitz problem'. It is known by an indirect and non-constructive argument that a vast majority of Bier spheres are non-polytopal. Contrary to that, we demonstrate that the Bier spheres associated to threshold simplicial complexes are all polytopal. Moreover, we show that all Bier spheres are starshaped. We also establish a connection between Bier spheres and Kantorovich–Rubinstein polytopes by showing that the boundary sphere of the KR-polytope associated to a polygonal linkage (weighted cycle) is isomorphic to the Bier sphere of the associated simplicial complex of "short sets". [ABSTRACT FROM AUTHOR]

Motivated by classical Euler’s Tonnetz, we introduce and study the combinatorics and topology of more general simplicial complexes Tonnn,k(L) of Tonnetz type. Out main result is that for a sufficiently generic choice of parameters the generalized Tonnetz Tonnn,k(L) is a triangulation of a (k − 1)-dimensional torus T k−1 . In the proof we construct and use the properties of a discrete Abel–Jacobi map, which takes values in the torus T k−1 ∼= Rk−1/Λ where Λ ∼= A∗ k−1 is the permutohedral lattice. [ABSTRACT FROM AUTHOR]

Ideal matrices and clutters are prevalent in combinatorial optimization, ranging from balanced matrices, clutters of T-joins, to clutters of rooted arborescences. Most of the known examples of ideal clutters are combinatorial in nature. In this paper, rendered by the recently developed theory of cuboids, we provide a different class of ideal clutters, one that is geometric in nature. The advantage of this new class of ideal clutters is that it allows for infinitely many ideal minimally nonpacking clutters. We characterize the densest ideal minimally nonpacking clutters of the class. Using the tools developed, we then verify the replication conjecture for the class. [ABSTRACT FROM AUTHOR]

We propose and analyze batch greedy heuristics for cardinality constrained maximization of non-submodular non-decreasing set functions. We consider the standard greedy paradigm, along with its distributed greedy and stochastic greedy variants. Our theoretical guarantees are characterized by the combination of submodularity and supermodularity ratios. We argue how these parameters define tight modular bounds based on incremental gains, and provide a novel reinterpretation of the classical greedy algorithm using the minorize- maximize (MM) principle. Based on that analogy, we propose a new class of methods exploiting any plausible modular bound. In the context of optimal experimental design for linear Bayesian inverse problems, we bound the submodularity and supermodularity ratios when the underlying objective is based on mutual information. We also develop novel modular bounds for the mutual information in this setting, and describe certain connections to polyhedral combinatorics. We discuss how algorithms using these modular bounds relate to established statistical notions such as leverage scores and to more recent efforts such as volume sampling. We demonstrate our theoretical findings on synthetic problems and on a real-world climate monitoring example. [ABSTRACT FROM AUTHOR]

The shortest bibranching problem is a common generalization of the minimum-weight edge cover problem in bipartite graphs and the minimum-weight arborescence problem in directed graphs. For the shortest bibranching problem, an efficient primal-dual algorithm is given by Keijsper and Pendavingh (J Comb Theory Ser B 73:130–145, 1998), and the tractability of the problem is ascribed to total dual integrality in a linear programming formulation by Schrijver (Ann Discret Math 16:261–280, 1982). Another view on the tractability of this problem is afforded by a valuated matroid intersection formulation by Takazawa (Jpn J Ind Appl Math 29:561–573, 2012). In the present paper, we discuss the relationship between these two formulations for the shortest bibranching problem. We first demonstrate that the valuated matroid intersection formulation can be derived from the linear programming formulation through the Benders decomposition, where integrality is preserved in the decomposition process and the resulting convex programming is endowed with discrete convexity. We then show how a pair of primal and dual optimal solutions of one formulation is constructed from that of the other formulation, thereby providing a connection between polyhedral combinatorics and discrete convex analysis. [ABSTRACT FROM AUTHOR]

A coloring of a graph is an assignment of colors to its vertices such that any two vertices receive distinct colors whenever they are adjacent. An acyclic coloring is a coloring such that no cycle receives exactly two colors, and the acyclic chromatic number χA(G) of a graph G is the minimum number of colors in any such coloring of G. Given a graph G and an integer k, determining whether χA(G) ≤ k or not is NP-complete even for k = 3. The acyclic coloring problem arises in the context of efficient computations of sparse and symmetric Hessian matrices via substitution methods. In a previous work we presented facet-inducing families of valid inequalities based on induced even cycles for the polytope associated to an integer programming formulation of the acyclic coloring problem. In this work we continue with this study by introducing new families of facet-inducing inequalities based on combinations of even cycles and cliques. [ABSTRACT FROM AUTHOR]

The matroid parity (MP) problem is a powerful (and N P -hard) extension of the matching problem. Whereas matching polytopes are well understood, little is known about MP polytopes. We prove that, when the matroid is laminar, the MP polytope is affinely congruent to a perfect b -matching polytope. From this we deduce that, even when the matroid is not laminar, every Chvátal–Gomory cut for the MP polytope can be derived as a { 0 , 1 2 } -cut from a laminar family of rank constraints. We also prove a negative result concerned with the integrality gap of two linear relaxations of the MP problem. [ABSTRACT FROM AUTHOR]

Based on the sociometric analysis of social networks, we introduce the sociotechnical teams formation problem (STFP). Given a group of individuals with different skill-sets and a social network that captures the mutual affinity between them, the problem consists in finding a set of pairwise disjoint teams, as harmonious as possible, with a minimum specified number of individuals per team per skill. We prove that STFP is NP -hard and propose an integer linear programming formulation. We show several classes of facet-inducing inequalities for the corresponding polytope. Computational experiments performed on a set of 120 test instances attest the efficiency of a solution method based on the formulation strengthened by valid inequalities and on a simulated annealing algorithm used to provide good initial feasible solutions. [ABSTRACT FROM AUTHOR]

Total dual integrality is a powerful and unifying concept in polyhedral combinatorics and integer programming that enables the refinement of geometric min-max relations given by linear programming strong duality into combinatorial min-max theorems. The definition of a linear inequality system being totally dual integral (TDI) revolves around the existence of optimal dual solutions that are integral and thus naturally applies to a host of combinatorial optimization problems that are cast as integer programs whose linear program (LP) relaxations have the TDIness property. However, when combinatorial problems are formulated using more general convex relaxations, such as semidefinite programs (SDPs), it is not at all clear what an appropriate notion of integrality in the dual program is, thus inhibiting the generalization of the theory to more general forms of structured convex optimization. (In fact, we argue that the rank-one constraint usually added to SDP relaxations is not adequate in the dual SDP.) In this paper, we propose a notion of total dual integrality for SDPs that generalizes the notion for LPs, by relying on an "integrality constraint" for SDPs that is primal-dual symmetric. A key ingredient for the theory is a generalization to compact convex sets of a result of Hoffman for polytopes, fundamental for generalizing the polyhedral notion of total dual integrality introduced by Edmonds and Giles. We study the corresponding theory applied to SDP formulations for stable sets in graphs using the Lovâsz theta function and show that total dual integrality in this case corresponds to the underlying graph being perfect. We also relate dual integrality of an SDP formulation for the maximum cut problem to bipartite graphs. Total dual integrality for extended formulations naturally comes into play in this context. [ABSTRACT FROM AUTHOR]

The topological interference management (TIM) problem studies the degrees of freedom (DoF) of partially-connected interference networks with no channel state information (CSI) at the transmitters except the network topology (i.e., partial connectivity). In this paper, we consider a variant of the TIM problem with uncertainty in network topology, where the channel state with partial connectivity is only known to belong to one of $M$ states at the transmitters. In particular, the transmitter has access to all network topological information over $M$ states, but is unaware of which state it falls in exactly for communication. The receiver at any state is aware of the exact state it falls in besides the network topologies of all states, and wish to recover as much highly-prioritized information at current state as possible. We formulate it as the opportunistic TIM problem with network uncertainty modeled by $M$ state-varying network topologies. To adapt to network topology uncertainty and different message decoding priority, joint encoding and opportunistic decoding are enabled at the transmitters and receivers respectively. Specifically, being aware of all possible network topologies, each transmitter sends a signal jointly encoded from all messages desired over $M$ states, say $M$ distinct messages, and at a certain State $m$ , Receiver $k$ wishes to opportunistically decode the first $\pi _{k}(m) \in \{1,2,\cdots,M\}$ higher-priority messages. Under this opportunistic TIM setting, we construct a multi-state conflict graph to capture the mutual conflict of messages over $M$ states, and characterize the optimal DoF region of two classes of network topologies via polyhedral combinatorics. A remarkable fact is that, under an additional mild monotonous condition, the optimality conditions of orthogonal access and one-to-one interference alignment still apply to TIM with uncertainty in network topology. [ABSTRACT FROM AUTHOR]

Optimal Recovery of a Hidden Hamiltonian Cycle with Applications in Genome Sequencing One of the most pressing challenges in genomics is to reconstruct a long and contiguous genome sequence from short genome subsequences (contigs). Recent developments in sequencing technology obtain long-range linking measurements among the contigs. In "Hidden Hamiltonian Cycle Recovery via Linear Programming," Bagaria, Ding, Tse, Wu, and Xu propose a probabilistic model for the problem of contig assembly, where the goal is to recover a Hamiltonian cycle hidden in a complete weighted graph based on noisy edge measurements. Computing the maximum likelihood estimate in this model reduces to the traveling salesman problem (TSP). Despite the NP-hardness of TSP, they show that a simple linear programming (LP) relaxation—namely, the fractional 2-factor LP—recovers the hidden Hamiltonian cycle with high probability, whenever it is information-theoretically possible. Evaluation of the algorithm on real data shows improvements over existing approaches. We introduce the problem of hidden Hamiltonian cycle recovery, where there is an unknown Hamiltonian cycle in an n-vertex complete graph that needs to be inferred from noisy edge measurements. The measurements are independent and distributed according to Pn for edges in the cycle and Qn otherwise. This formulation is motivated by a problem in genome assembly, where the goal is to order a set of contigs (genome subsequences) according to their positions on the genome using long-range linking measurements between the contigs. Computing the maximum likelihood estimate in this model reduces to a traveling salesman problem (TSP). Despite the NP-hardness of TSP, we show that a simple linear programming (LP) relaxation—namely, the fractional 2-factor (F2F) LP—recovers the hidden Hamiltonian cycle with high probability as n → ∞ provided that α n − log n → ∞ , where α n ≜ − 2 log ∫ d P n d Q n is the Rényi divergence of order 1 2 . This condition is information-theoretically optimal in the sense that, under mild distributional assumptions, α n ≥ (1 + o (1)) log n is necessary for any algorithm to succeed regardless of the computational cost. Departing from the usual proof techniques based on dual witness construction, the analysis relies on the combinatorial characterization (in particular, the half-integrality) of the extreme points of the F2F polytope. Represented as bicolored multigraphs, these extreme points are further decomposed into simpler "blossom-type" structures for the large deviation analysis and counting arguments. Evaluation of the algorithm on real data shows improvements over existing approaches. [ABSTRACT FROM AUTHOR]

The 1‐wheel inequalities for the stable set polytope were introduced by Cheng and Cunningham. In general, there is an exponential number of these inequalities. We present a new polynomial size extended formulation of the stable set relaxation that includes the odd cycle and 1‐wheel inequalities. This compact formulation allows one to polynomially optimize over a polyhedron instead of handling the separation problem for 1‐wheel inequalities by solving many shortest walk problems and relying on the ellipsoid method. [ABSTRACT FROM AUTHOR]

Let G = (V, E) be an undirected graph where the edges in E have non-negative weights. A star in G is either a single node of G or a subgraph of G where all the edges share one common end-node. A star forest is a collection of vertex-disjoint stars in G. The weight of a star forest is the sum of the weights of its edges. This paper deals with the problem of finding a Maximum Weight Spanning Star Forest (MWSFP) in G. This problem is NP-hard but can be solved in polynomial time when G is a cactus [Nguyen, Discrete Math. Algorithms App.7 (2015) 1550018]. In this paper, we present a polyhedral investigation of the MWSFP. More precisely, we study the facial structure of the star forest polytope, denoted by SFP(G), which is the convex hull of the incidence vectors of the star forests of G. First, we prove several basic properties of SFP(G) and propose an integer programming formulation for MWSFP. Then, we give a class of facet-defining inequalities, called M-tree inequalities, for SFP(G). We show that for the case when G is a tree, the M-tree and the nonnegativity inequalities give a complete characterization of SFP(G). Finally, based on the description of the dominating set polytope on cycles given by Bouchakour et al. [Eur. J. Combin.29 (2008) 652–661], we give a complete linear description of SFP(G) when G is a cycle. [ABSTRACT FROM AUTHOR]

Given an undirected simple graph G with node set V and edge set E, let f v , for each node v ∈ V , denote a nonnegative integer value that is lower than or equal to the degree of v in G. An f-dominating set in G is a node subset D such that for each node v ∈ V \ D at least f v of its neighbors belong to D. In this paper, we study the polyhedral structure of the polytope defined as the convex hull of all the incidence vectors of f-dominating sets in G and give a complete description for the case of trees. We prove that the corresponding separation problem can be solved in polynomial time. In addition, we present a linear-time algorithm to solve the weighted version of the problem on trees: Given a cost c v ∈ R for each node v ∈ V , find an f-dominating set D in G whose cost, given by ∑ v ∈ D c v , is a minimum. [ABSTRACT FROM AUTHOR]

Abstract This paper addresses a scheduling problem involving a continuously-divisible cumulative resource with limited capacity. During its processing, each task requests a part of this resource, which lies between a minimum and a maximum requirement. A task is finished when a certain amount of energy is received by it within its time window. This energy is received via the resource and an amount of resource is converted into an amount of energy with an increasing and pseudo-linear efficiency function. The goal is to minimize the resource consumption. The paper focuses on an event-based mixed integer linear program, providing several valid inequalities, which are used to improve the performance of the model. Furthermore, we give a minimal description of the polytope of all feasible assignments to the on/off binary variable for a single activity along with a dedicated separation algorithm. Computational experiments are reported in order to show the effectiveness of the results. [ABSTRACT FROM AUTHOR]

A (convex) polytope P is said to be 2-level if for each hyperplane H that supports a facet of P, the vertices of P can be covered with H and exactly one other translate of H. The study of these polytopes is motivated by questions in combinatorial optimization and communication complexity, among others. In this paper, we present the first algorithm for enumerating all combinatorial types of 2-level polytopes of a given dimension d, and provide complete experimental results for d⩽7. Our approach is inductive: for each fixed (d-1)-dimensional 2-level polytope P0, we enumerate all d-dimensional 2-level polytopes P that have P0 as a facet. This relies on the enumeration of the closed sets of a closure operator over a finite ground set. By varying the prescribed facet P0, we obtain all 2-level polytopes in dimension d. [ABSTRACT FROM AUTHOR]

Abstract A set of points X = X B ∪ X R ⊆ R d is linearly separable if the convex hulls of X B and X R are disjoint, hence there exists a hyperplane separating X B from X R. Such a hyperplane provides a method for classifying new points, according to which side of the hyperplane the new points lie. When such a linear separation is not possible, it may still be possible to partition X B and X R into prespecified numbers of groups , in such a way that every group from X B is linearly separable from every group from X R. We may also discard some points as outliers , and seek to minimize the number of outliers necessary to find such a partition. Based on these ideas, Bertsimas and Shioda proposed the classification and regression by integer optimization (CRIO) method in 2007. In this work we explore the integer programming aspects of the classification part of CRIO, in particular theoretical properties of the associated formulation. We are able to find facet-inducing inequalities coming from the stable set polytope, hence showing that this classification problem has exploitable combinatorial properties. [ABSTRACT FROM AUTHOR]

The max-cut problem is a fundamental and much-studied NP -hard combinatorial optimisation problem, with a wide range of applications. Several authors have shown that the max-cut problem can be solved in polynomial time if the underlying graph is free of certain minors. We give a polyhedral counterpart of these results. In particular, we show that, if a family of valid inequalities for the cut polytope satisfies certain conditions, then there is an associated minor-closed family of graphs on which the max-cut problem can be solved efficiently. [ABSTRACT FROM AUTHOR]

The problem of minimizing a multilinear function of binary variables is a well-studied NP-hard problem. The set of solutions of the standard linearization of this problem is called the multilinear set. We study a cardinality constrained version of it with upper and lower bounds on the number of nonzero variables. We call the set of solutions of the standard linearization of this problem a multilinear set with cardinality constraints. We characterize a set of conditions on these multilinear terms (called properness) and observe that under these conditions the convex hull description of the set is tractable via an extended formulation. We then give an explicit polyhedral description of the convex hull when the multilinear terms have a nested structure. Our description has an exponential number of inequalities which can be separated in polynomial time. Finally, we generalize these inequalities to obtain valid inequalities for the general case. [ABSTRACT FROM AUTHOR]

In this paper we propose a geometric approach to solve the Graph Isomorphism (GI in short) problem. Given two graphs G1,G2, the GI problem is to decide if the given graphs are isomorphic i.e., there exists an edge preserving bijection between the vertices of the two graphs. We propose an Integer Linear Program (ILP) that has a non-empty solution if and only if the given graphs are isomorphic. The convex hull of all possible solutions of the ILP has been studied in literature as the Quadratic Assignment Problem (QAP) polytope. We study the feasible region of the linear programming relaxation of the ILP and show that the given graphs are isomorphic if and only if this region intersects with the QAP-polytope. As a consequence, if the graphs are not isomorphic, the feasible region must lie entirely outside the QAP-polytope. We study the facial structure of the QAP-polytope with the intention of using the facet defining inequalities to eliminate the feasible region outside the polytope. We determine two new families of facet defining inequalities of the QAP-polytope and show that all the known facet defining inequalities are special instances of a general inequality. Further we define a partial ordering on each exponential sized family of facet defining inequalities and show that if there exists a common minimal violated inequality for all points in the feasible region outside the QAP-polytope, then we can solve the GI problem in polynomial time. We also study the general case when there are k such inequalities and give an algorithm for the GI problem that runs in time exponential in k. [ABSTRACT FROM AUTHOR]