ABSTRACT. The Routing and Spectrum Assignment problem consists of routing a given set of origin-destination traffic demands and assigning them to contiguous spectrum frequencies such that no frequency slot is assigned to more than one demand within a network link. This work deals with the variant where each demand route must additionally satisfy a maximal-length constraint. In this paper we propose a compact extended formulation for the Constrained Routing and Spectrum Assignment Problem. We show that our extended formulation is stronger than formulations known in the literature. Experimental results demonstrate the efficiency of our approach.

ABSTRACT. In this work we study the Load Minimization Problem in undirected weighted cycles. In this problem, we are given a cycle and a set of weighted origin-destination pairs. The goal is to route all the pairs minimizing the load of the routing according to the given weights. We prove that the problem is NP-complete and that it is 2-approximable. For unitary weights we present a FPT algorithm whose parameter is a natural lower bound for the value of the load.

ABSTRACT. The flexible grid (flexgrid) technology specified in the ITU-T standard G.694.1 is one of the most promising solutions to deal with huge data traffic demands in large communication networks. 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. The routing and spectrum allocation problem (RSA) consists on establishing lightpaths for a set of end-to-end demands that compete for spectrum resources and it has been shown to be NP-hard. In previous works we have proposed several integer programming formulations, leading to different solution approaches, and implemented a branch-and-cut algorithm with several families of valid inequalities as cutting planes for one of the best performing models. In the present work we propose a math-based primal-heuristic in order to improve this last procedure

ABSTRACT. It is well-known that 1-tuple domination (classical domination) is NP-hard for general graphs. For circular-arc graphs, it is efficiently solvable due to M.S. Chang (1998). On the other side, efficient algorithms of a known generalization ---k-tuple domination (k fixed)--- of 1-tuple domination are not developed for circular-arc graphs and k greater than 2. In this work we introduce a new circular-arc graph subclass. For this subclass, we present a lower bound for the k-tuple domination number for every positive integer k. Finally, we find the exact value of these numbers by proving how to achieve this bound.

ABSTRACT. Scheduling capacities and resources plays a vital role in building and maintaining efficient transportation networks. In the field of maritime shipping, vessels and crews are regarded as key resources which need to be scheduled in a best possible way. However, in academic literature, they have not received enough focus and there has not been any considerable attempt regarding the integration of vessel and crew scheduling. After reviewing related research fields in maritime shipping, the necessity of integrating the two problems, i.e. vessel scheduling and crew scheduling, is discussed. Explanations about the problem settings, key elements and stakeholders are given. A mathematical model is proposed for the integrated problem. Exemplary test instances of various sizes are generated and solved with a standard solver. As large problem instances are difficult to solve in this way, a decomposition approach is proposed. Related sub-problems are processed separately, however, with a cooperation mechanism to construct a complete solution to the original problem. Finally, the impact of disturbances is discussed. We investigate the impacts of restrictions on the vessel and crew availability which is common in the era of the Covid-19 pandemic.

ABSTRACT. In this work we deal with the problem of scheduling residential appliances of 2 classes under a demand response program abiding to energy consumption bounds for each interval, in the context of smart grids. We consider a day-ahead pricing scheme and aim to minimize the economic cost of energy and the discomfort felt by users. Despite the fact that this is an NP-hard problem, we developed an exact algorithm to solve this problem, based on backtracking and quadratic programming. In this presentation we will explain many developments and ideas that were fundamental to achieve an exact algorithm for the described problem that obtained results in acceptable execution times.

ABSTRACT. Industrial manufacturing is often organized in assembly lines where a product is assembled on a sequence of workstations, each of which executes some of the assembly tasks. A line is balanced if the maximum total execution time of any station is minimal. Commonly the task execution order is constrained by precedences, and task execution times are known. Here, we consider a problem variation, called the ``Calzedonia Workload Allocation Problem'', where the precedences form a chain, but the execution time of a task depends on the worker executing it. This problem is a special case of the Assembly Line Worker Assignment and Balancing Problem. We present recent research, and introduce a new heuristic, that focuses on problem instances with a large number of workers, which are hard for current methods.

ABSTRACT. This work addresses a complex parallel machine scheduling problem with jobs divided into operations and operations grouped in families. Non-anticipatory family setup times are held at the beginning of each batch, defined by combining one setup-time and a sequence of operations from a unique family. Other aspects are also considered in the problem, such as release dates for operations and machines, operation sizes, and machine’s eligibility and capacity. We consider item availability to define the completion times of the operations within the batches, to minimize the total weighted completion time of jobs. We developed an Iterated Greedy (IG) algorithm combining destroy and repair operators with a Random Variable Neighborhood Descent (RVND) local search procedure, using four neighborhood structures to solve the problem. Our algorithm outperforms the current literature methods for the problem, in terms of average deviation for the best solutions and computational times, in a known benchmark set of 72 instances. New upper bounds are also provided for some instances within this set. Besides, computational experiments are conducted to evaluate the proposed method’s performance in a more challenging set of instances introduced in this work. The greedy repair operator showed superior performance, with more than 70% of the best solutions found. Despite the simplicity, the method presented the best results in different evaluated criteria, highlighting its potential and applicability in solving a complex machine scheduling problem.

ABSTRACT. An adjacent vertex distinguishing edge coloring (avdec) of a graph G is a proper edge coloring such that for every pair of adjacent vertices, the sets of the assigned colors to the edges incident to each are different.

Assuming colors are positive integers, the sum adjacent vertex distinguishing edge coloring problem which looks for an avdec with minimum sum.

We present an integer programming approach and propose two ILP formulations and devolop a Branch-and-Cut algorithm. Our computational experience shows that our algorithm is capable of solving instances that are out of reach of CPLEX.

ABSTRACT. We study a discrete version of the classical classification problem, to be called geodesic classification problem. It is defined on a graph, where some vertices are initially assigned a class, and the remaining ones must be classified. This vertex partition is grounded on the concept of geodesic convexity on graphs, as a replacement for the Euclidean convexity in the multidimensional space. We propose two integer programming models along with branch-and-cut algorithms to solve them. We also carry out a polyhedral study and run computational experiments to evaluate the proposed approaches.

ABSTRACT. Many optimization problems in AI are solved by transforming the input into a graph and then finding a clique maximizing an objective function. Not only are cliques often too rigid a structure, but the standard method for solving this problem, enumerating all maximal cliques and returning one maximizing the objective function, is either too slow or (in dense graphs) infeasible. We show that partial enumeration of k-plexes, via light modifications to clique local search algorithms, is sufficient to find high-quality solutions in both sparse and dense graphs in two example applications.

ABSTRACT. We consider the minimum chromatic violation problem (MCVP) studied from a polyhedral point of view. A previous paper presents the classical study of the convex hull of feasible solutions in it, introducing several exponentially sized families of valid inequalities and conditions under which they induce facets. Here we address the separation procedures for these families to find proper cuts and add them to the formulation in a cutting-plane fashion for solving the MCVP. As the inequalities analyzed in this work are associated with cliques in the given graph, we explore different clique-finding approaches and compare them within a computational experimentation over a set of DIMACS and random instances.

ABSTRACT. One of the main challenges in forest management planning involves decisions regarding the extraction of timber from the forest, namely the construction and maintenance of forest roads, the gathering of timber at loading sites in management units, and the transport to the final destination.

We consider a problem arising in a 7623 ha forest in Northwest Portugal with eucalyptus and maritime pine as predominant species. It is a collaborative joint management area that has been classified into 1137 homogeneous management units. Plans selected by the stakeholders convey information about the units to be harvested in each time period as well as the volume to be harvested in each unit.

ABSTRACT. We present an application of quantitative methods for scheduling the carnival competition of children and teenagers held annually in Uruguay. A mixed-integer linear programming model was developed for the problem, with the aim of finding a fixture that leads to balanced attendance of the public, while fulfilling certain constraints related to the competition regulations and other requirements indicated by the organizers. The fixture obtained from solving the model with an optimization solver was employed in the 2019/2020 edition of the competition, with satisfactory results.

ABSTRACT. This paper studies carbon taxes effectiveness to induce a transition to cleaner production when a firm faces different technologies in terms of emissions and investment cost. Carbon taxes effectiveness is explored through a strategic capacity planning under carbon taxes model, which is formulated as a mixed integer linear problem (MILP). Our model integrates decisions not explored previously in the literature of strategic capacity planning, such as machine replacement and workforce planning. We find that carbon taxes by themselves do not necessarily induce a transition to cleaner production, since their effectiveness depends on the size of the firm and the available technology relationships.