Search

Designing the scientific program of a technical conference is a nontrivial task, in particular when there are many parallel sessions to be scheduled. In this setting, each session must be composed by a thematically coherent set of presentations, whereas sessions attracting a similar audience should not be scheduled simultaneously. In this work we explore this issue, by proposing a combinatorial optimization model representing this situation and by presenting computational techniques that allow to obtain good-quality solutions for this problem. We illustrate the application of these techniques to the scientific program of the XXI Latin-Iberoamerican Conference in Operations Research, which took place in December 2022. We present experiments assessing the general contribution of the computational machinery proposed in this work, concluding that these techniques allow to automatically design the scientific program of a mid- to large-sized conference while taking into account the mentioned criteria. [ABSTRACT FROM AUTHOR]

The routing and spectrum allocation (RSA) problem arises in the context of flexible grid optical networks, and consists in routing a set of demands through a network while simultaneously assigning a bandwidth to each demand, subject to non-overlapping constraints. One of the most effective integer programming formulations for RSA is the DR-AOV formulation, presented in a previous work. In this work we explore a relaxation of this formulation with a subset of variables from the original formulation, in order to identify valid inequalities that could be useful within a cutting-plane environment for tackling RSA. We present basic properties of this relaxed formulation, we identify several families of facet-inducing inequalities, and we show that they can be separated in polynomial time. [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]

One of the most promising solutions to deal with huge data traffic demands in large communication networks is given by flexible optical networking, in particular the flexible grid (flexgrid) technology specified in the ITU-T standard G.694.1. In this specification, the frequency spectrum of an optical fiber link is divided into narrow frequency slots. Any sequence of consecutive slots can be used as a simple channel, and such a channel can be switched in the network nodes to create a lightpath. In this kind of networks, the problem of establishing lightpaths for a set of end-to-end demands that compete for spectrum resources is called the routing and spectrum allocation problem (RSA). Due to its relevance, RSA has been intensively studied in the last years. It has been shown to be NP-hard and different solution approaches have been proposed for this problem. In this paper we present several families of valid inequalities, valid equations, and optimality cuts for a natural integer programming formulation of RSA and, based on these results, we develop a branch-and-cut algorithm for this problem. Our computational experiments suggest that such an approach is effective at tackling this problem. [ABSTRACT FROM AUTHOR]

In the b-coloring problem , we aim to assign colors from a set C to the vertices of a graph G in such a way that adjacent vertices do not receive the same color, and for every c ∈ C we have a c -colored vertex v in G such that every color in C ∖ { c } is assigned to at least one of v 's neighbors. It has been shown that b-coloring is NP-complete, so we propose in this article an approach for the problem under integer programming techniques. To this end, we give an integer programming formulation and study the associated polytope. We provide several families of valid inequalities, and analyze facetness conditions for them. Finally, we show computational evidence suggesting that the given inequalities may be useful in a branch-and-cut environment. [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]

We propose a generalization of the k -coloring problem, namely the minimum chromatic violation problem (MCVP). Given a graph G = ( V , E ) , a set of weak edges F ⊂ E and a set of colors C , the MCVP asks for a | C | -coloring of the graph G ′ = ( V , E \ F ) minimizing the number of weak edges with both endpoints receiving the same color. We present an integer programming formulation for this problem and provide an initial polyhedral study of the polytopes arising from this formulation. We give partial characterizations of facet-inducing inequalities and we show how facets from weaker and stronger instances of MCVP (i.e., more/less weak edges) are related. We then introduce a general lifting procedure which generates (sometimes facet-inducing) valid inequalities from generic valid inequalities and we present several facet-inducing families arising from this procedure. Finally, we present another family of facet-inducing inequalities which is not obtained from the prior lifting procedure. [ABSTRACT FROM AUTHOR]

The bandwidth coloring problem (BCP) is a generalization of the well-known vertex coloring problem (VCP), asking colors to be assigned to vertices of a graph such that the absolute difference between the colors assigned to adjacent vertices is greater than or equal to a weight associated to the edge connecting them. In this work we present an integer programming formulation for BCP based on the orientation model for VCP. We present two families of valid inequalities for this formulation, show that they induce facets of the associated polytope, and report computational experience suggesting that these families are useful in practice. [ABSTRACT FROM AUTHOR]

Despite the fact that many vertex coloring problems are polynomially solvable on certain graph classes, most of these problems are not “under control” from a polyhedral point of view. The equivalence between optimization and separation suggests the existence of integer programming formulations for these problems whose associated polytopes admit elegant characterizations. In this work we address this issue. As a starting point, we focus our attention on the well-known standard formulation for the classical vertex coloring problem. We present some general results about this formulation and we show that the vertex coloring polytope associated to this formulation for a graph G and a set of colors C corresponds to a face of the stable set polytope of a particular graph S G C . We further study the perfectness of S G C showing that when ∣ C ∣ > 2 , this graph is perfect if and only if G is a block graph, from which we deduce a complete characterization of the associated coloring polytopes for block graphs. We also derive a new family of valid inequalities generalizing several known families from the literature and we conjecture that this family is sufficient to completely describe the vertex coloring polytope associated to cacti graphs. [ABSTRACT FROM AUTHOR]

Abstract: In this work we study a particular way of dealing with interference in combinatorial optimization models representing wireless communication networks. In a typical wireless network, co-channel interference occurs whenever two overlapping antennas use the same frequency channel, and a less critical interference is generated whenever two overlapping antennas use adjacent channels. This motivates the formulation of the minimum-adjacency vertex coloring problem which, given an interference graph representing the potential interference between the antennas and a set of prespecified colors/channels, asks for a vertex coloring of minimizing the number of edges receiving adjacent colors. We propose an integer programming model for this problem and present three families of facet-inducing valid inequalities. Based on these results, we implement a branch-and-cut algorithm for this problem, and we provide promising computational results. [Copyright &y& Elsevier]

Abstract: Given a graph G and an integer k, the maximum edge subgraph problem consists in finding a k-vertex subset of G such that the number of edges within the subset is maximum. This NP-hard problem arises in the analysis of cohesive subgroups in social networks. In this work we study the polytope associated with a straightforward integer programming formulation of the maximum edge subgraph problem. We characterize the graph generated by and give a tight bound on its diameter. We give a complete description of , where is the star on vertices, and we conjecture a complete description of , where is the graph composed by m disjoint edges. Finally, we introduce three families of facet-inducing inequalities for , which generalize known families of valid inequalities for this polytope. [Copyright &y& Elsevier]

Abstract: One of the most challenging tasks within the planning of a demographic census is to partition each census track into sets of homes such that each census taker visits exactly one set from this partition. In this work we introduce the home segmentation problem, which consists in designing such a partition subject to specific constraints. We present an integer programming-based algorithm for this problem, and we report the application of this algorithm for the 2010 census in the main province in Argentina. [Copyright &y& Elsevier]

Abstract: A coloring of a graph G is an assignment of colors to the vertices of G such that any two vertices receive distinct colors whenever they are adjacent. An acyclic coloring of G is a coloring such that no cycle of G receives exactly two colors, and the acyclic chromatic number 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 or not is NP-complete even for . The acyclic coloring problem arises in the context of efficient computations of sparse and symmetric Hessian matrices via substitution methods. In this work we study the disjunctive rank of six facet-inducing families of valid inequalities for the polytope associated to a natural integer programming formulation of the acyclic coloring problem. We also introduce the concept of disjunctive anti-rank and study the anti-rank of these families. [Copyright &y& Elsevier]

Abstract: In this work we consider the single-item single-machine lot-sizing problem with continuous start-up costs. A continuous start-up cost is generated in a period whenever there is a nonzero production in the period and the production capacity in the previous period is not saturated. This concept of start-up does not correspond to the standard (discrete) start-up considered in previous models, thus motivating a polyhedral study of this problem. We introduce a natural integer programming formulation for this problem, we study some general properties and facet-inducing inequalities of the associated polytope, and we state relationships with known lotsizing polytopes. [Copyright &y& Elsevier]

Abstract: The study of cohesive subgroups is an important aspect of social network analysis. Cohesive subgroups are studied using different relaxations of the notion of clique in a graph. For instance, given a graph and an integer k, the maximum edge subgraph problem consists in finding a k-vertex subset such that the number of edges within the subset is maximum. This work proposes a polyhedral approach for this NP-hard problem. We study the polytope associated to an integer programming formulation of the problem, present several families of facet-inducing valid inequalities, and discuss the separation problem associated to these families. [Copyright &y& Elsevier]

Abstract: A coloring of a graph G is an assignment of colors to the vertices of G such that any two vertices receive distinct colors whenever they are adjacent. An acyclic coloring of G is a coloring such that no cycle of G receives exactly two colors, and the acyclic chromatic number 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 or not is NP-complete even for . The acyclic coloring problem arises in the context of efficient computations of sparse and symmetric Hessian matrices via substitution methods. In this work we start an integer programming approach for this problem, by introducing a natural integer programming formulation and presenting six facet-inducing families of valid inequalities. [Copyright &y& Elsevier]

Abstract: The football pool problem asks for the minimun number of bets on the result on n football matches ensuring that some bet correctly predicts the outcome of at least of them. This combinatorial problem has proven to be extremely difficult, and is open for . Integer programming techniques have been applied to this problem in the past but, in order to tackle the open cases, a deep knowledge of the polytopes associated with the integer programs modeling this problem is required. In this work we address this issue, by defining and studying the football pool polytope in connection with a natural integer programming formulation of the football pool problem. We explore the basic properties of this polytope and present several classes of facet-inducing valid inequalities over natural combinatorial structures in the original problem. [Copyright &y& Elsevier]