Search

Given a matrix with real-valued entries, the maximum 2D subarray problem consists in finding a rectangular submatrix with consecutive rows and columns maximizing the sum of its entries. In this work we start a polyhedral study of an integer programming formulation for this problem. We thus define the 2D subarray polytope, explore conditions ensuring the validity of linear inequalities, and provide several families of facet-inducing inequalities. We also report computational experiments assessing the reduction of the dual bound for the linear relaxation achieved by these families of inequalities.

The first division clubs in Argentinean professional football maintain teams in each of six youth leagues, classed by age as major divisions (Under-20, Under-18, Under-17) and minor divisions (Under-16, Under-15, Under-14). Regular season play in these leagues typically follows a single round-robin format; the minor divisions play the same schedule as the majors but with the home-away status of the matches reversed. This setup can give rise to very significant differences in travel distances between the major and minor division teams of a given club, which is a frustrating situation for club officials, coaches, and players alike but almost impossible to avoid with manual season scheduling techniques. Nor are these methods able to take into account any number of other criteria that go into the design of a satisfactory match calendar. This paper reports on models developed using mathematical programming to simultaneously schedule multiple leagues while also meeting a series of other desirable conditions. The central criterion is a better balance in the travel distances of the various teams, pursued through the application of two alternative solution approaches: one based on regional team clusters and the other on explicit analysis of actual distances between the teams’ home venues. The solutions generated by these approaches have been used by the organizers of the Argentinean youth leagues to draw up their season schedules since 2018, which has resulted in a series of benefits for all stakeholders.

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.

In this paper we define a generalization of the classical vertex coloring problem of a graph, where some pairs of adjacent vertices can be assigned to the same color. We call weak an edge connecting two such vertices. We look for a coloring of the graph minimizing the number of weak edges having its endpoints assigned to the same color. This problem is called the minimum chromatic violation problem (MCVP). We present an integer programming formulation for this problem and provide an initial polyhedral study of the polytope arising from this formulation. We give partial characterizations of facet-inducing inequalities and we show how facets from different instances of MCVP are related. We then introduce general lifting procedures which generate (sometimes facet-inducing) valid inequalities from generic valid inequalities. We exhibit several facet-inducing families arising from these procedures and we present a family of facet-inducing inequalities which is not obtained from the prior lifting procedures, associated with certain substructures in the given graph. Finally, we analyze the extreme case of all weak edges and its relationship with the well-known k -partition problem.

A caterpillar is a connected graph such that the removal of all its vertices with degree 1 results in a path. Given a graph G, a caterpillar-packing of G is a set of vertex-disjoint (not necessarily induced) subgraphs of G such that each subgraph is a caterpillar. In this work we consider the set of caterpillar-packings of a graph, which corresponds to feasible solutions of the 2-schemes strip cutting problem with a sequencing constraint (2-SSCPsc) presented by Rinaldi and Franz (Eur. J. Oper. Res. 183 (2007) 1371–1384). Facet-preserving procedures have been shown to be quite effective at explaining the facet-inducing inequalities of the associated polytope, so in this work we continue this issue by exploring such procedures for valid inequalities with acyclic supports. In particular, the obtained results are applicable when the underlying graph is a tree.

Two sets X B , X R ⊆ R d are linearly separable if their convex hulls are disjoint, implying that a hyperplane separating X B from X R exists. Such a hyperplane provides a method for classifying new points, according to the side of the hyperplane in which the new points lie. In this work we consider a particular case of the 2-class classification problem, which asks to select the maximum number of points from X B and X R in such a way that the selected points are linearly separable. We present an integer programming formulation for this problem, explore valid inequalities for the associated polytope, and develop a cutting plane approach coupled with a lazy-constraints scheme.

Given two graphs G = (V, EG) and H = (V, EH) over the same set of vertices and given a set of colors C, the impact on H of a coloring c : V → C of G, denoted I ( c ) , is the number of edges ij ∈ EH such that c(i) = c(j). In this setting, the maximum-impact coloring problem asks for a proper coloring c of G maximizing the impact I ( c ) on H. This problem naturally arises in the context of assigning classrooms to courses, where it is desirable –but not mandatory– to assign lectures from the same course to the same classroom. We are interested in an integer programming approach for this problem. In this work we present two procedures that construct valid inequalities from existing inequalities, based on extending individual colors to sets of colors and on extending edges of G to cliques, respectively. If the original inequality defines a facet and additional technical hypotheses are satisfied, then the obtained inequality also defines a facet. We present a generic separation algorithm based on these procedures, and report computational experiments showing that this approach is effective.

Given a d-dimensional array, the maximum subarray problem consists in finding an axis-parallel slice of the array maximizing the sum of its entries. In this work we start a polyhedral study of a natural integer programming formulation for this problem when d = 2. Such an exploration is motivated by the need of solving large-scale instances of the rectilinear picture compression problem (RPC), a problem which arises in different scenarios. The obtained results can be useful to solve the column generation phase of a branch and price approach for RPC, a technique that applies naturally to this problem. We thus define the 2D subarray polytope, explore conditions ensuring the validity of linear inequalities, and provide several families of facet-inducing inequalities.

Operations research methods are applied to design the season schedules of Argentina’s professional basketball leagues using a format adopted in 2014 by the top two divisions. Following the setup used by the National Basketball Association (NBA) in North America, games are played any day of the week and away games are scheduled in road trips of one to four consecutive games. The main scheduling objective is to reduce the teams’ total travel distance compared to previous season formats through the use of predetermined trips submitted by the teams. The mathematical form of the problem is a variation on the well-known Travelling Tournament Problem. The modelling is divided into two successive stages, the first one defining the sequences in which each team plays the other teams and the second one assigning the days on which each game is played. Both stages use integer programming models that incorporate a series of constraints reflecting criteria requested by the Argentine Basketball Club Association. Implementation of the models has generated average travel distance reductions of more than 30% per away game, with consequential benefits in lower travel costs and less player fatigue.

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.

A subset S of vertices of a graph G = ( V , E ) is P 3 -convex if every simple path of three vertices starting and ending in S is contained in S . The P 3 -convex hull of S is the smallest P 3 -convex set containing S and the P 3 -hull number of G is the minimum number of vertices of a subset S such that its convex hull is V . It is a known fact that the calculation of the P 3 -hull number of a graph is NP-hard. In the present work we start the study of this problem from a polyhedral point of view, that is, we pose it as a binary IP problem and we study the associated polytope by exploring several families of facet-defining inequalities.

A caterpillar is a connected graph such that the removal of all its vertices with degree 1 results in a path. Given a graph G , a caterpillar-packing of G is a set of vertex-disjoint (not necessarily induced) subgraphs of G such that each subgraph is a caterpillar. In this work we consider the set of caterpillar-packings of a graph, which corresponds to feasible solutions of the 2-schemes strip cutting problem with a sequencing constraint (2-SSCPsc) presented by F. Rinaldi and A. Franz in 2007. We study the polytope associated with a natural integer programming formulation of this problem. We explore basic properties of this polytope, including a lifting lemma and several facet-preserving operations on the graph. These results allow us to introduce several families of facet-inducing inequalities.

We propose general separation procedures for generating cuts for the stable set polytope, inspired by a procedure by Rossi and Smriglio and applying a lifting method by Xavier and Campelo. In contrast to existing cut-generating procedures, ours generate both rank and non-rank valid inequalities, hence they are of a more general nature than existing methods. This is accomplished by iteratively solving a lifting problem, which consists of a maximum weighted stable set problem on a smaller graph. Computational experience on DIMACS benchmark instances shows that the proposed approach may be a useful tool for generating cuts for the stable set polytope.

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, this problem has been intensively studied in the last couple of years. It has been shown to be NP-hard (Christodoulopoulos et al. in IEEE J Lightw Technol 29(9):1354–1366, 2011; Wang et al. in IEEE J Opt Commun Netw 4(11):906–917, 2012) and several models and formulations have been proposed, leading to different solution approaches. In this work, we explore integer programming models for RSA, analyzing their effectiveness over known instances. We resort to several modeling techniques, to find natural formulations of this problem. Since integer programming techniques are known to provide successful practical approaches for several combinatorial optimization problems, the aim of this work is to explore a similar approach for RSA. Fil: Bertero, Federico Alberto. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina Fil: Bianchetti, Marcelo. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina Fil: Marenco, Javier Leonardo. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina

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.

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.

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.

In a previous work we presented six facet-inducing families of valid inequalities for the polytope associated to an integer programming formulation of the acyclic coloring problem. In this work we study their disjunctive rank, as defined by [E. Balas, S. Ceria and G. Cornuejols, Math. Program. 58 (1993) 295–324]. We also propose to study a dual concept, which we call the disjunctive anti-rank of a valid inequality.

Neste trabalho, apresenta-se o modelo baseado em distâncias para o problema clássico de coloração de vértices em grafos (VCP). A formulação de programação linear inteira utiliza variáveis de decisão que representam a distância entre cores atribuídas para cada par de vértices distintos, no lugar de fornecer explicitamente tais cores. Mostra-se que há uma relação próxima entre esta formulação e o modelo baseado em orientação para o VCP, proposto também pelos autores deste trabalho. Em particular, prova-se que desigualdades indutoras de facetas para o modelo baseado em orientação podem ser traduzidas em desigualdades indutoras de facetas para o modelo baseado em distâncias e vice-versa.

In a previous work we have presented a procedure for generating rank and non-rank valid inequalities for the stable set polytope based on clique projection and lifting operations. In this work we propose to apply another lifting operation and give some sufficient conditions for this new procedure to generate facet defining inequalities. Computational experience shows that the proposed approach allows to obtain tighter upper bounds for the maximum stable set problem.

In this work we consider the uniform capacitated 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. In this work we explore a natural integer programming formulation for this problem. We consider the polytope obtained as convex hull of the feasible points in this problem. We state some general properties, study whether the model constraints define facets, and present an exponentially-sized family of valid inequalities for it. We analyze the structure of the extreme points of this convex hull, their adjacency and bounds for the polytope diameter. Finally, we study the particular case when the demands are high enough in order to require production in all the periods. We provide a complete description of the convex hull of feasible solutions in this case and show that all the inequalities in this description are separable in polynomial time, thus proving its polynomial time solvability. Fil: Escalante, Mariana Silvina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Cientifico Tecnológico Rosario; Argentina. Universidad Nacional de Rosario. Facultad de Cs.exactas Ingenieria y Agrimensura. Escuela de Cs.exactas y Naturales. Departamento de Matematica; Argentina Fil: Marenco, Javier. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina Fil: Varaldo, Maria del Carmen. Universidad Nacional de Rosario. Facultad de Cs.exactas Ingenieria y Agrimensura. Escuela de Cs.exactas y Naturales. Departamento de Matematica; Argentina

In this work we consider the distance model for the classical vertex coloring problem, introduced by Delle Donne in 2009. This formulation involves decision variables representing the distance between the colors assigned to every pair of distinct vertices, thus not explicitly representing the colors assigned to each vertex. We show close relations between this formulation and the so-called orientation model for graph coloring. In particular, we prove that we can translate many facet-inducing inequalities for the orientation model polytope into facet-inducing inequalities for the distance model polytope, and viceversa.

We propose to study a problem that arises naturally from both Topological Numbering of Directed Acyclic Graphs, and Additive Coloring (also known as Lucky Labeling). Let D be a digraph and f a labeling of its vertices with positive integers; denote by S ( v ) the sum of labels over all neighbors of each vertex v. The labeling f is called topological additive numbering if S ( u ) < S ( v ) for each arc ( u , v ) of the digraph. The problem asks to find the minimum number k for which D has a topological additive numbering with labels belonging to { 1 , ? , k } , denoted by ? t ( D ) .We characterize when a digraph has topological additive numberings, give a lower bound for ? t ( D ) and provide an integer programming formulation for our problem. We also present some families for which ? t ( D ) can be computed in polynomial time. Finally, we prove that this problem is NP -Hard even when its input is restricted to planar bipartite digraphs. We define and study a problem which we call Topological Additive Numbering of Directed Acyclic Graphs.We prove that the existence of a topological additive numbering in a digraph is polynomial.We give a lower bound of the parameter in terms of a clique of the digraph.We give the exact value of the parameter for certain families of digraphs.We prove that the problem is NP-Hard even when the digraph is planar and bipartite.

This article studies a multi-item auction characterized by asymmetricbidders and quantity discounts. We report a practical application of thistype of auction in the procurement of Internet services to the 709 publicschools of Buenos Aires. The asymmetry in this application is due to firms?existing technology infrastructures, which affect their ability to providethe service in certain areas of the city. A single round first-price sealed-bidauction, it required each participating firm to bid a supply curve specifyinga price on predetermined graduated quantity intervals and to identify theindividual schools it would supply. The maximal intersections of the setsof schools each participant has bid on define regions we call competitionunits. A single unit price must be quoted for all schools supplied withinthe same quantity interval, so that firms cannot bid a high price wherecompetition is weak and a lower one where it is strong. Quantity discountsare allowed so that the bids can reflect returns-to-scale of the suppliers andthe auctioneer may benefit of awarding bundles of units instead of separateunits. The winner determination problem in this auction poses a challengeto the auctioneer. We present an exponential formulation and a polynomialformulation for this problem, both based on integer linear programming.The polynomial formulation proves to find the optimal set of bids in amatter of seconds. Results of the real-world implementation are reported. Fil: Bonomo, Flavia. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigaciones Matemáticas "Luis A. Santaló". Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigaciones Matemáticas "Luis A. Santaló"; Argentina Fil: Catalán, Jaime. Universidad de Chile; Chile Fil: Duran, Ricardo Guillermo. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigaciones Matemáticas "Luis A. Santaló". Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigaciones Matemáticas "Luis A. Santaló"; Argentina Fil: Epstein, Rafael. Universidad de Chile; Chile Fil: Guajardo, Mario. Universidad de Chile; Chile Fil: Jawtuschenko, Alexis Boris. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigaciones Matemáticas "Luis A. Santaló". Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigaciones Matemáticas "Luis A. Santaló"; Argentina Fil: Marenco, Javier Leonardo. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina

In-pipe robots are a powerful tool for hydrate plug removal inside ultra-deep water pipes. These robots may operate with energy supplied by umbilical cables immersed in oil. Present work focus on the development of a general strategy for computing the required forces for pulling such cables confined in ducts of generic length and geometry. Based on mathematical models obtained from specialized literature, a computational algorithm was designed to evaluate the static friction force related to the cumulative effects along the arbitrary set of curves present in a generic pipe. This computational routine can calculate the static friction forces associated to a cable inside a given pipe, whose coordinates are fed by the user. To evaluate the simulation performance, the achieved results were compared with that ones obtained through experimental tests performed using a cable with polymeric coating positioned inside ducts. Different geometries, load and lubricating conditions were tested, and the analytical model could estimate with reasonable accuracy the required force to move an umbilical cable inside pipes.

This article reports on the use of mathematical programming techniques to optimise the routes of a recyclable waste collection system servicing Morón, a large municipality outside Buenos Aires, Argentina. The truck routing problem posed by the system is a particular case of the generalised directed open rural postman problem. An integer programming model is developed with a solving procedure built around a subtour-merging algorithm and the addition of subtour elimination constraints. The route solutions generated by the proposed methodology perform significantly better than the previously used, manually designed routes, the main improvement being that coverage of blocks within the municipality with the model solutions is 100% by construction, whereas with the manual routes as much as 16% of the blocks went unserviced. The model-generated routes were adopted by the municipality in 2014 and the national government is planning to introduce the methodology elsewhere in the country. Fil: Braier, Gustavo. Braier & Asociados Consultores; Argentina Fil: Duran, Guillermo Alfredo. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina Fil: Marenco, Javier Leonardo. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina Fil: Wesner, Francisco. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina

We study integer programming formulations for the 2-schemes strip cutting problem with a sequencing constraint (2-SSCPsc) considered by Rinaldi and Franz. The 2-SSCPsc arises in the context of corrugated cardboard production, which involves cutting strips of large lengths into rectangles of at most (usually) two different lengths. Because of buffer restrictions, in the 2-SSCPsc these strips must be sequenced in such a way that, at any moment, at most two types of items are in production and not completed yet. This problem is NP-hard. We present four integer programming formulations for this problem, and our computational experiments with real-life instances show that one of them has a very tight integrality gap. We propose a heuristic procedure based on this formulation and present computational experience showing that this procedure finds very good primal solutions in small running times.

A set of points $X = X_B \cup X_R \subseteq \mathbb{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., Comment: 22 pages, 4 figures

Given a graph G = (V, E), a family of nonempty vertex-subsets S ⊆ 2 V , and a weight w : S → R+, the maximum stable set problem with weights on vertex-subsets consists in finding a stable set I of G maximizing the sum of the weights of the sets in S that intersect I. This problem arises within a natural column generation approach for the vertex coloring problem. In this work we perform an initial polyhedral study of this problem, by introducing a natural integer programming formulation and studying the associated polytope. We address general facts on this polytope including some lifting results, we provide connections with the stable set polytope, and we present three families of facet-inducing inequalities. Fil: Campêlo, Manoel. Universidade Federal do Ceará; Brasil Fil: Campos, Victor A.. Universidade Federal do Ceará; Brasil Fil: Corrêa, Ricardo C.. Universidade Federal do Ceará; Brasil Fil: Delle Donne, Diego Andrés. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina Fil: Marenco, Javier Leonardo. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina Fil: Mydlarz, Marcelo. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina

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 χ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 this work we start an integer programming approach for this problem, by introducing a natural integer programming formulation and presenting six families of facet-inducing valid inequalities.

The present authors consider the widely popular Argentine Turismo Carretera car racing series, which consists of 11 regular phase races followed by five playoff races. After the regular phase, the first 12 racers in the standings qualify for the playoffs, which determine the champion. The present authors address the problem of determining, at any point within the regular phase, the minimum number of points that each racer must earn in the remainder of the regular phase in order to secure a playoff spot. Two mixed-integer programming models for this problem are presented, their properties and practical performance are analysed, and the obtained results are discussed.

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 P ( G , k ) associated with a straightforward integer programming formulation of the maximum edge subgraph problem. We characterize the graph generated by P ( G , k ) and give a tight bound on its diameter. We give a complete description of P ( K 1 n , k ) , where K 1 n is the star on n + 1 vertices, and we conjecture a complete description of P ( m K 2 , k ) , where m K 2 is the graph composed by m disjoint edges. Finally, we introduce three families of facet-inducing inequalities for P ( G , k ) , which generalize known families of valid inequalities for this polytope.

We address the problem of existence of an envy-free distribution of pieces among two or more players in the cake-cutting setting with the minimum number of cuts. Our cakes are discrete in the sense that the playersʼ valuations are concentrated on atoms. These atoms are placed on an interval and no two players give positive value to atoms placed at the same position. We prove the existence of an envy-free allocation for any discrete cake and any number of players by resorting to Spernerʼs Lemma, a suitable triangulation, and moving-knife arguments. Our results also apply to pies, which are defined over circumferences instead of intervals.

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.

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.

In this paper, we study the minimum sum set coloring (MSSC) problem which consists in assigning a set of x(v) positive integers to each vertex v of a graph so that the intersection of sets assigned to adjacent vertices is empty and the sum of the assigned set of numbers to each vertex of the graph is minimum. The MSSC problem occurs in two versions: non-preemptive and preemptive. We show that the MSSC problem is strongly NP-hard both in the preemptive case on trees and in the non-preemptive case in line graphs of trees. Finally, we give exact parameterized algorithms for these two versions on trees and line graphs of trees. Fil: Bonomo, Flavia. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina Fil: Duran, Guillermo Alfredo. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad de Chile; Chile. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina Fil: Marenco, Javier. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina Fil: Valencia Pabon, Mario. Universite de Paris 13-nord; Francia

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 χ 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 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.

Chromatic scheduling polytopes arise as solution sets of the bandwidth allocation problem in certain radio access networks, which supply wireless access to voice/data communication for customers with fixed antennas and individual demands. This problem is NP-complete and, moreover, does not admit polynomial-time approximation algorithms with a fixed quality guarantee. As algorithms based on cutting planes have shown to be successful for many other combinatorial optimization problems, our goal is to apply such methods to the bandwidth allocation problem. To gain the required knowledge on the associated polytopes, the present paper contributes by considering three new classes of valid inequalities based on cycles in the interference graph. We discuss in which cases they define facets and explore the associated separation problems, showing that two of them are solvable in polynomial time.

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 n − 1 of them. This combinatorial problem has proven to be extremely difficult, and is open for n ⩾ 6 . 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.

We analyze the variant of the minority game with an additional interaction mechanism introduced by Caridi and Ceva in [I. Caridi, H. Ceva, Physica A 339 (2004) 574], which considers a periodic square lattice of agents where some of them may share information with their neighbors. We show that low levels of interaction in this model induce the interacting agents to play with their most similar strategies (those minimizing the Hamming distance between them), hence the resulting dynamics can be replicated by introducing groups of similar one-strategy agents. We also study the reaction of non-interacting agents to the global perturbations introduced by the interacting agents, showing the emergence of cluster-detection patterns.

Point-to-Multipoint systems are a kind of radio systems supplying wireless access to voice/data communication networks. Such systems have to be run using a certain frequency spectrum, which typically causes capacity problems. Hence it is, on the one hand, necessary to reuse frequencies but, on the other hand, no interference must be caused thereby. This leads to a combinatorial optimization problem, the bandwidth allocation problem, a special case of so-called chromatic scheduling problems. Both problems are NP-hard and it is known that, for these problems, there exist no polynomial time algorithms with a fixed approximation ratio. Algorithms based on cutting planes have shown to be successful for many other combinatorial optimization problems. In order to apply such methods, knowledge on the associated polytopes is required. The present paper contributes to this issue, exploring basic properties of chromatic scheduling polytopes and several classes of facet-defining inequalities.

Chromatic scheduling polytopes arise as solution sets of the bandwidth allocation problem in certain radio access networks, supplying wireless access to voice/data communication networks for customers with individual communication demands. To maintain the links, only frequencies from a certain spectrum can be used, which typically causes capacity problems. Hence it is necessary to reuse frequencies but no interference must be caused by this reuse. This leads to the bandwidth allocation problem, a special case of so-called chromatic scheduling problems. Both problems are NP-hard, and there do not even exist polynomial time algorithms with a fixed quality guarantee.As algorithms based on cutting planes have shown to be successful for many other combinatorial optimization problems, the goal is to apply such methods to the bandwidth allocation problem. For that, knowledge on the associated polytopes is required. The present paper contributes to this issue, exploring the combinatorial structure of chromatic scheduling polytopes for increasing frequency spans. We observe that the polytopes pass through various stages—emptyness, non-emptyness but low-dimensionality, full-dimensionality but combinatorial instability, and combinatorial stability—as the frequency span increases. We discuss the thresholds for this increasing “quantity” giving rise to a new combinatorial “quality” of the polytopes, and we prove bounds on these thresholds. In particular, we prove combinatorial equivalence of chromatic scheduling polytopes for large frequency spans and we establish relations to the linear ordering polytope.

Point-to-Multipoint systems are one kind of radio systems supplying wireless access to voice/data communication networks. Capacity constraints typically force the reuse of frequencies but, on the other hand, no interference must be caused thereby. This leads to the bandwidth allocation problem, a special case of so-called chromatic scheduling problems. Both problems are NP-Hard, and there exist no polynomial time algorithms with a guaranteed quality. In order to apply cutting plane methods to this problem, the associated chromatic scheduling polytopes must be studied. These polytopes have interesting theoretical properties. In this work, we present a characterization of the extreme points of chromatic scheduling polytopes, which enables to prove combinatorial equivalence properties.