
Allende, H., Bravo, D., & Canessa, E. (2010). Robust design in multivariate systems using genetic algorithms. Qual. Quant., 44(2), 315–332.
Abstract: This paper presents a methodology based oil genetic algorithms, which finds feasible and reasonably adequate Solutions to problems of robust design in multivariate systems. We use a genetic algorithm to determine the appropriate control factor levels for simultaneously optimizing all of the responses of the system, considering the noise factors which affect it. The algorithm is guided by a desirability function which works with only one fitness function although the system May have many responses. We validated the methodology using data obtained from a real system and also from a process simulator, considering univariate and multivariate systems. In all cases, the methodology delivered feasible solutions, which accomplished the goals of robust design: obtain responses very close to the target values of each of them, and with minimum variability. Regarding the adjustment of the mean of each response to the target value, the algorithm performed very well. However, only in some of the multivariate cases, the algorithm was able to significantly reduce the variability of the responses.



AlvarezMiranda, E., & Pereira, J. (2017). Designing and constructing networks under uncertainty in the construction stage: Definition and exact algorithmic approach. Comput. Oper. Res., 81, 178–191.
Abstract: The present work proposes a novel Network Optimization problem whose core is to combine both network design and network construction scheduling under uncertainty into a single twostage robust optimization model. The firststage decisions correspond to those of a classical network design problem, while the secondstage decisions correspond to those of a network construction scheduling problem (NCS) under uncertainty. The resulting problem, which we will refer to as the TwoStage Robust Network Design and Construction Problem (2SRNDC), aims at providing a modeling framework in which the design decision not only depends on the design costs (e.g., distances) but also on the corresponding construction plan (e.g., time to provide service to costumers). We provide motivations, mixed integer programming formulations, and an exact algorithm for the 2SRNDC. Experimental results on a large set of instances show the effectiveness of the model in providing robust solutions, and the capability of the proposed algorithm to provide good solutions in reasonable running times. (C) 2017 Elsevier Ltd. All rights reserved.



Araujo, J., Ducoffe, G., Nisse, N., & Suchan, K. (2018). On interval number in cycle convexity. Discret. Math. Theor. Comput. Sci., 20(1), 35 pp.
Abstract: Recently, Araujo et al. [Manuscript in preparation, 2017] introduced the notion of Cycle Convexity of graphs. In their seminal work, they studied the graph convexity parameter called hull number for this new graph convexity they proposed, and they presented some of its applications in Knot theory. Roughly, the tunnel number of a knot embedded in a plane is upper bounded by the hull number of a corresponding planar 4regular graph in cycle convexity. In this paper, we go further in the study of this new graph convexity and we study the interval number of a graph in cycle convexity. This parameter is, alongside the hull number, one of the most studied parameters in the literature about graph convexities. Precisely, given a graph G, its interval number in cycle convexity, denoted by in(cc)(G), is the minimum cardinality of a set S subset of V (G) such that every vertex w is an element of E V (G) \ S has two distinct neighbors u, v is an element of S such that u and v lie in same connected component of G[S], i.e. the subgraph of G induced by the vertices in S. In this work, first we provide bounds on in(cc) (G) and its relations to other graph convexity parameters, and explore its behaviour on grids. Then, we present some hardness results by showing that deciding whetherin(cc) (G) <= k is NPcomplete, even if G is a split graph or a boundeddegree planar graph, and that the problem is W[2]hard in bipartite graphs when k is the parameter. As a consequence, we obtain that in(cc) (G) cannot be approximated up to a constant factor in the classes of split graphs and bipartite graphs (unless P = NP). On the positive side, we present polynomialtime algorithms to compute in(cc) (G) for outerplanar graphs, cobipartite graphs and interval graphs. We also present fixedparameter tractable (FPT) algorithms to compute it for (q, q – 4)graphs when q is the parameter and for general graphs G when parameterized either by the treewidth or the neighborhood diversity of G. Some of our hardness results and positive results are not known to hold for related graph convexities and domination problems. We hope that the design of our new reductions and polynomialtime algorithms can be helpful in order to advance in the study of related graph problems.



Barrera, J., Moreno, E., & Varas, S. (2020). A decomposition algorithm for computing income taxes with passthrough entities and its application to the Chilean case. Ann. Oper. Res., 286(12), 545–557.
Abstract: Income tax systems with “passthrough” entities transfer a firm's income to shareholders, which are taxed individually. In 2014, a Chilean tax reform introduced this type of entity and changed to an accrual basis that distributes incomes (but not losses) to shareholders. A crucial step for the Chilean taxation authority is to compute the final income of each individual given the complex network of corporations and companies, usually including cycles between them. In this paper, we show the mathematical conceptualization and the solution to the problem, proving that there is only one way to distribute income to taxpayers. Using the theory of absorbing Markov chains, we define a mathematical model for computing the taxable income of each taxpayer, and we propose a decomposition algorithm for this problem. This approach allows us to compute the solution accurately and to efficiently use computational resources. Finally, we present some characteristics of Chilean taxpayers' network and the computational results of the algorithm using this network.



Calderon, F., Lozada, A., Morales, P., BorquezParedes, D., Jara, N., Olivares, R., et al. (2022). Heuristic Approaches for Dynamic Provisioning in MultiBand Elastic Optical Networks. IEEE Commun. Lett., 26(2), 379–383.
Abstract: Multiband elastic optical networks are a promising alternative to meet the bandwidth demand of the evergrowing Internet traffic. In this letter, we propose a family of band allocation algorithms for multiband elastic optical networks. Employing simulation, we evaluate the blocking performance of 3 algorithms of such a family and compare their performance with the only heuristic proposed to date. Results show that the three new algorithms outperform the previous proposal, with up to one order of magnitude improvement. We expect these results to help advance the area of dynamic resource allocation in multiband elastic optical networks.



Canessa, E., & Chaigneau, S. (2015). Calibrating AgentBased Models Using a Genetic Algorithm. Stud. Inform. Control, 24(1), 79–90.
Abstract: We present a Genetic Algorithm (GA)based tool that calibrates Agentbased Models (ABMs). The GA searches through a userdefined set of input parameters of an ABM, delivering values for those parameters so that the output time series of an ABM may match the real system's time series to certain precision. Once that set of possible values has been available, then a domain expert can select among them, the ones that better make sense from a practical point of view and match the explanation of the phenomenon under study. In developing the GA, we have had three main goals in mind. First, the GA should be easily used by nonexpert computer users and allow the seamless integration of the GA with different ABMs. Secondly, the GA should achieve a relatively short convergence time, so that it may be practical to apply it to many situations, even if the corresponding ABMs exhibit complex dynamics. Thirdly, the GA should use a few data points of the real system's time series and even so, achieve a sufficiently good match with the ABM's time series to attaining relational equivalence between the real system under study and the ABM that models it. That feature is important since social science longitudinal studies commonly use few data points. The results show that all of those goals have been accomplished.



Canessa, E., Droop, C., & Allende, H. (2012). An improved genetic algorithm for robust design in multivariate systems. Qual. Quant., 46(2), 665–678.
Abstract: In a previous article, we presented a genetic algorithm (GA), which finds solutions to problems of robust design in multivariate systems. Based on that GA, we developed a new GA that uses a new desirability function, based on the aggregation of the observed variance of the responses and the squared deviation between the mean of each response and its corresponding target value. Additionally, we also changed the crossover operator from a onepoint to a uniform one. We used three different case studies to evaluate the performance of the new GA and also to compare it with the original one. The first case study involved using data from a univariate real system, and the other two employed data obtained from multivariate process simulators. In each of the case studies, the new GA delivered good solutions, which simultaneously adjusted the mean of each response to its corresponding target value. This performance was similar to the one of the original GA. Regarding variability reduction, the new GA worked much better than the original one. In all the case studies, the new GA delivered solutions that simultaneously decreased the standard deviation of each response to almost the minimum possible value. Thus, we conclude that the new GA performs better than the original one, especially regarding variance reduction, which was the main problem exhibited by the original GA.



Canessa, E., Vera, S., & Allende, H. (2012). A new method for estimating missing values for a genetic algorithm used in robust design. Eng. Optimiz., 44(7), 787–800.
Abstract: This article presents an improved genetic algorithm (GA), which finds solutions to problems of robust design in multivariate systems with many control and noise factors. Since some values of responses of the system might not have been obtained from the robust design experiment, but may be needed in the search process, the GA uses response surface methodology (RSM) to estimate those values. In all test cases, the GA delivered solutions that adequately adjusted the mean of the responses to their corresponding target values and with low variability. The GA found more solutions than the previous versions of the GA, which makes it easier to find a solution that may meet the tradeoff among variance reduction, mean adjustment and economic considerations. Moreover, RSM is a good method for estimating the mean and variance of the outputs of highly nonlinear systems, which makes the new GA appropriate for optimizing such systems.



Carrasco, R. A., Iyengar, G., & Stein, C. (2018). Resource cost aware scheduling. Eur. J. Oper. Res., 269(2), 621–632.
Abstract: We are interested in the scheduling problem where there are several different resources that determine the speed at which a job runs and we pay depending on the amount of each resource that we use. This work is an extension of the resource dependent job processing time problem and the energy aware scheduling problems. We develop a new constant factor approximation algorithm for resource cost aware scheduling problems: the objective is to minimize the sum of the total cost of resources and the total weighted completion time in the one machine nonpreemptive setting, allowing for arbitrary precedence constraints and release dates. Our algorithm handles general jobdependent resource cost functions. We also analyze the practical performance of our algorithms, showing that it is significantly superior to the theoretical bounds and in fact it is very close to optimal. The analysis is done using simulations and real instances, which are left publicly available for future benchmarks. We also present additional heuristic improvements and we study their performance in other settings. (C) 2018 Elsevier B.V. All rights reserved.



Dumett, M. A., & Cominetti, R. (2018). On The Stability Of An Adaptive Learning Dynamics In Traffic Games. J. Dyn. Games, 5(4), 265–282.
Abstract: This paper investigates the dynamic stability of an adaptive learning procedure in a traffic game. Using the RouthHurwitz criterion we study the stability of the rest points of the corresponding mean field dynamics. In the special case with two routes and two players we provide a full description of the number and nature of these rest points as well as the global asymptotic behavior of the dynamics. Depending on the parameters of the model, we find that there are either one, two or three equilibria and we show that in all cases the mean field trajectories converge towards a rest point for almost all initial conditions.



Fernandez, C., Valle, C., Saravia, F., & Allende, H. (2012). Behavior analysis of neural network ensemble algorithm on a virtual machine cluster. Neural Comput. Appl., 21(3), 535–542.
Abstract: Ensemble learning has gained considerable attention in different learning tasks including regression, classification, and clustering problems. One of the drawbacks of the ensemble is the high computational cost of training stages. Resampling local negative correlation (RLNC) is a technique that combines two wellknown methods to generate ensemble diversityresampling and error negative correlationand a finegrain parallel approach that allows us to achieve a satisfactory balance between accuracy and efficiency. In this paper, we introduce a structure of the virtual machine aimed to test diverse selection strategies of parameters in neural ensemble designs, such as RLNC. We assess the parallel performance of this approach on a virtual machine cluster based on the full virtualization paradigm, using speedup and efficiency as performance metrics, for different numbers of processors and training data sizes.



Feuilloley, L., Fraigniaud, P., Montealegre, P., Rapaport, I., Remila, E., & Todinca, I. (2021). Compact Distributed Certification of Planar Graphs. Algorithmica, 83(7), 2215–2244.
Abstract: Naor M., Parter M., Yogev E.: (The power of distributed verifiers in interactive proofs. In: 31st ACMSIAM symposium on discrete algorithms (SODA), pp 1096115, 2020. https://doi.org/10.1137/1.9781611975994.67) have recently demonstrated the existence of a distributed interactive proof for planarity (i.e., for certifying that a network is planar), using a sophisticated generic technique for constructing distributed IP protocols based on sequential IP protocols. The interactive proof for planarity is based on a distributed certification of the correct execution of any given sequential lineartime algorithm for planarity testing. It involves three interactions between the prover and the randomized distributed verifier (i.e., it is a dMAM protocol), and uses small certificates, on O(log n) bits in nnode networks. We show that a single interaction with the prover suffices, and randomization is unecessary, by providing an explicit description of a prooflabeling scheme for planarity, still using certificates on just O(log n) bits. We also show that there are no prooflabeling schemesin fact, even no locally checkable proofsfor planarity using certificates on o(log n) bits.



Feuilloley, L., Fraigniaud, P., Montealegre, P., Rapaport, I., Remila, E., & Todinca, I. (2023). Local certification of graphs with bounded genus. Discret Appl. Math., 325, 9–36.
Abstract: Naor, Parter, and Yogev [SODA 2020] recently designed a compiler for automatically translating standard centralized interactive protocols to distributed interactive protocols, as introduced by Kol, Oshman, and Saxena [PODC 2018]. In particular, by using this compiler, every lineartime algorithm for deciding the membership to some fixed graph class can be translated into a dMAM(O(log n)) protocol for this class, that is, a distributed interactive protocol with O(log n)bit proof size in nnode graphs, and three interactions between the (centralized) computationallyunbounded but nontrustable prover Merlin, and the (decentralized) randomized computationallylimited verifier Arthur. As a corollary, there is a dMAM(O(log n)) protocol for recognizing the class of planar graphs, as well as for recognizing the class of graphs with bounded genus.We show that there exists a distributed interactive protocol for recognizing the class of graphs with bounded genus performing just a single interaction, from the prover to the verifier, yet preserving proof size of O(log n) bits. This result also holds for the class of graphs with bounded nonorientable genus, that is, graphs that can be embedded on a nonorientable surface of bounded genus. The interactive protocols described in this paper are actually prooflabeling schemes, i.e., a subclass of interactive protocols, previously introduced by Korman, Kutten, and Peleg [PODC 2005]. In particular, these schn be computed a priori, at low cost, by the nodes themselves. Our results thus extend the recent prooflabeling scheme for planar graphs by Feuilloley et al. [PODC 2020], to graphs of bounded genus, and to graphs of bounded nonorientable genus.



Goles, E., & Montealegre, P. (2020). The complexity of the asynchronous prediction of the majority automata. Inf. Comput., 274(SI).
Abstract: We consider the asynchronous prediction problem for some automaton as the one consisting in determining, given an initial configuration, if there exists a nonzero probability that some selected site changes its state, when the network is updated picking one site at a time uniformly at random. We show that for the majority automaton, the asynchronous prediction problem is in NC in the twodimensional lattice with von Neumann neighborhood. Later, we show that in three or more dimensions the problem is NPComplete.



Goles, E., Leal, L., Montealegre, P., Rapaport, I., & RiosWilson, M. (2023). Distributed maximal independent set computation driven by finitestate dynamics. Int. J. Parallel Emergent Distrib. Syst., Early Access.
Abstract: A Maximal Independent Set (MIS) is an inclusion maximal set of pairwise nonadjacent vertices. The computation of an MIS is one of the core problems in distributed computing. In this article, we introduce and analyze a finitestate distributed randomized algorithm for computing a Maximal Independent Set (MIS) on arbitrary undirected graphs. Our algorithm is selfstabilizing (reaches a correct output on any initial configuration) and can be implemented on systems with very scarce conditions. We analyze the convergence time of the proposed algorithm, showing that in many cases the algorithm converges in logarithmic time with high probability.



Goles, E., Maldonado, D., Montealegre, P., & Ollinger, N. (2020). On the complexity of the stability problem of binary freezing totalistic cellular automata. Inf. Comput., 274, 21 pp.
Abstract: In this paper we study the family of twostate Totalistic Freezing Cellular Automata (TFCA) defined over the triangular and square grids with von Neumann neighborhoods. We say that a Cellular Automaton is Freezing and Totalistic if the active cells remain unchanged, and the new value of an inactive cell depends only on the sum of its active neighbors. We classify all the Cellular Automata in the class of TFCA, grouping them in five different classes: the Trivial rules, Turing Universal rules, Algebraic rules, Topological rules and Fractal Growing rules. At the same time, we study in this family the STABILITY problem, consisting in deciding whether an inactive cell becomes active, given an initial configuration. We exploit the properties of the automata in each group to show that: For Algebraic and Topological Rules the STABILITY problem is in NC. For Turing Universal rules the STABILITY problem is PComplete. (C) 2020 Elsevier Inc. All rights reserved.



Lagos, T., Armstrong, M., HomemdeMello, T., Lagos, G., & Saure, D. (2021). A framework for adaptive openpit mining planning under geological uncertainty. Optim. Eng., 72, 102086.
Abstract: Mine planning optimization aims at maximizing the profit obtained from extracting valuable ore. Beyond its theoretical complexitythe openpit mining problem with capacity constraints reduces to a knapsack problem with precedence constraints, which is NPhardpractical instances of the problem usually involve a large to very large number of decision variables, typically of the order of millions for large mines. Additionally, any comprehensive approach to mine planning ought to consider the underlying geostatistical uncertainty as only limited information obtained from drill hole samples of the mineral is initially available. In this regard, as blocks are extracted sequentially, information about the ore grades of blocks yet to be extracted changes based on the blocks that have already been mined. Thus, the problem lies in the class of multiperiod large scale stochastic optimization problems with decisiondependent information uncertainty. Such problems are exceedingly hard to solve, so approximations are required. This paper presents an adaptive optimization scheme for multiperiod production scheduling in openpit mining under geological uncertainty that allows us to solve practical instances of the problem. Our approach is based on a rollinghorizon adaptive optimization framework that learns from new information that becomes available as blocks are mined. By considering the evolution of geostatistical uncertainty, the proposed optimization framework produces an operational policy that reduces the risk of the production schedule. Our numerical tests with mines of moderate sizes show that our rolling horizon adaptive policy gives consistently better results than a nonadaptive stochastic optimization formulation, for a range of realistic problem instances.



Letelier, O. R., Clautiaux, F., & Sadykov, R. (2022). Bin Packing Problem with Time Lags. INFORMS J. Comput., Early Access.
Abstract: We introduce and motivate several variants of the bin packing problem where bins are assigned to time slots, and minimum and maximum lags are required between some pairs of items. We suggest two integer programming formulations for the general problem: a compact one and a stronger formulation with an exponential number of variables and constraints. We propose a branchcutandprice approach that exploits the latter formulation. For this purpose, we devise separation algorithms based on a mathematical characterization of feasible assignments for two important special cases of the problem: when the number of possible bins available at each period is infinite and when this number is limited to one and time lags are nonnegative. Computational experiments are reported for instances inspired from a realcase application of chemical treatment planning in vineyards, as well as for literature instances for special cases of the problem. The experimental results show the efficiency of our branchcutandprice approach, as it outperforms the compact formulation on newly proposed instances and is able to obtain improved lower and upper bounds for literature instances. Summary of Contribution: The paper considers a new variant of the bin packing problem, which is one of the most important problems in operations research. A motivation for introducing this variant is given, as well as a reallife application. We present a novel and original exact branchcutandprice algorithm for the problem. We implement this algorithm, and we present the results of extensive computational experiments. The results show a very good performance of our algorithm. We give several research directions that can be followed by subsequent researchers to extend our contribution to more complex and generic problems.



Liedloff, M., Montealegre, P., & Todinca, I. (2019). Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques. Algorithmica, 81(3), 986–1005.
Abstract: Let P(G,X) be a property associating a boolean value to each pair (G,X) where G is a graph and X is a vertex subset. Assume that P is expressible in counting monadic second order logic (CMSO) and let t be an integer constant. We consider the following optimization problem: given an input graph G=(V,E), find subsets XFV such that the treewidth of G[F] is at most t, property P(G[F],X) is true and X is of maximum size under these conditions. The problem generalizes many classical algorithmic questions, e.g., Longest Induced Path, Maximum Induced Forest, IndependentHPacking, etc. Fomin et al. (SIAM J Comput 44(1):5487, 2015) proved that the problem is polynomial on the class of graph Gpoly, i.e. the graphs having at most poly(n) minimal separators for some polynomial poly. Here we consider the class Gpoly+kv, formed by graphs of Gpoly to which we add a set of at most k vertices with arbitrary adjacencies, called modulator. We prove that the generic optimization problem is fixed parameter tractable on Gpoly+kv, with parameter k, if the modulator is also part of the input.



Ortiz, C., & Villanueva, M. (2012). Maximal independent sets in caterpillar graphs. Discret Appl. Math., 160(3), 259–266.
Abstract: A caterpillar graph is a tree in which the removal of all pendant vertices results in a chordless path. In this work, we determine the number of maximal independent sets (mis) in caterpillar graphs. For a general graph, this problem is #Pcomplete. We provide a polynomial time algorithm to generate the whole family of mis in a caterpillar graph. We also characterize the independent graph (intersection graph of mis) and the clique graph (intersection graph of cliques) of complete caterpillar graphs. (C) 2011 Elsevier B.V. All rights reserved.

