The routing and spectrum allocation (RSA) problem is a critical challenge in optical networks, in which the objective is to assign a path and a set of contiguous frequency slots to each demand, meeting technical constraints given by the network infrastructure. As a key solution to managing large-scale data traffic in such networks, RSA has gained significant attention in the last years. One of the most effective integer programming formulations for RSA is the so-called DR-AOV model, and it is relevant to gain both theoretical and practical insights on this formulation. In this work, we tackle the first of these by starting a polyhedral study of the convex hull of the feasible solutions of the DR-AOV model. We identify general properties of this polytope, we establish relations to interval coloring polytopes, and we present several families of facet-inducing inequalities.

Given a graph G = (V,E) , a set of consecutive colors, and a demand vector d ∈ ℤ + |V| , the interval coloring problem asks for an assignment of d i consecutive colors to each vertex i ϵ V , in such a way that no two adjacent vertices are assigned the same color. Inspired by a situation arising in the allocation of ships to berths, in this work we propose to consider the split-interval coloring problem , which asks to assign at most two disjoint color intervals to each vertex in such a way that each vertex i ϵ V receives a total of d i colors. We explore a natural integer programming formulation for this NP-hard problem and its associated polytope. We state some relations to the interval coloring polytope, including lemmas allowing to translate valid inequalities between these two polytopes. We also present several valid inequalities and study conditions ensuring that these inequalities induce facets of the associated polytope.

The berth allocation problem models the spatial and temporal allocation of ships into berth space in container terminals. In this work we are interested in the discrete version of this problem, in which the container terminal is viewed as a set of atomic berths. We are particularly interested in modeling the existence of tides, in such a way that ships can be moved in/out of the container terminal only in high-tide periods. We introduce a natural extension of the standard formulation for the discrete berth allocation problem that considers this feature, and we perform a polyhedral exploration of this formulation. We present valid inequalities involving the variables that model high-tide periods, we explore conditions ensuring that these inequalities induce facets of the associated polytopes, and we present computational experiments showing that the reinforcement of the formulation with some of these inequalities has a better performance with a general integer programming solver.

production battery in the oil industry is a set of equipment and facilities used in the initial stages of crude oil processing at an oilfield. At various stages of operation, it may be necessary to restrict or increase its processing capacity, meaning that the gross volume to be received must be adjusted. In remote areas where connectivity and infrastructure may be limited, it is necessary for an operator to approach the well in person to make manual adjustments directly to the pumping system. Proper planning of the well route for adjusting regimes directly impacts the operating costs of the oilfield. In this work in progress, a mixed integer linear programming model for this problem is proposed, by considering the production, operation, and modification restrictions of the pumping regime of each well. Preliminary results are presented, which show that the model can be used in practice.

Internet of Things (IoT) is a technology that serves as the basis for smart environments. The ever-expanding set of applications that provide intelligence in different scenarios is continually growing and expanding. From precision agriculture to the development of sustainable smart cities, the need to have a communications infrastructure that allows the connectivity of sensors, actuators, and users becomes essential. In what is known as the “last mile,” wireless networks are the fastest growing group. For these to be operational, it is necessary to connect them to the Internet through gateways. These gateways handle different communication technologies and are therefore expensive nodes to install and maintain. Defining their location and their ability to “route” messages involves a combinatorial optimization problem. In this work in progress, a multiobjective integer linear programming model (minimizing number of gateways, used energy, and transmission time) is presented. To the best of our knowledge, previous literature does not include any optimization framework encompassing all these three objectives together.

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.

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.

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