
Acuna, V., Ferreira, C. E., Freire, A. S., & Moreno, E. (2014). Solving the maximum edge biclique packing problem on unbalanced bipartite graphs. Discret Appl. Math., 164, 2–12.
Abstract: A biclique is a complete bipartite graph. Given an (L, R)bipartite graph G = (V, E) and a positive integer k, the maximum edge biclique packing (num') problem consists in finding a set of at most k bicliques, subgraphs of G, such that the bicliques are vertex disjoint with respect to a subset of vertices S, where S E {V, L, R}, and the number of edges inside the bicliques is maximized. The maximum edge biclique (mEs) problem is a special case of the MEBP problem in which k = 1. Several applications of the MEB problem have been studied and, in this paper, we describe applications of the MEBP problem in metabolic networks and product bundling. In these applications the input graphs are very unbalanced (i.e., IRI is considerably greater than ILI), thus we consider carefully this property in our models. We introduce a new formulation for the MEB problem and a branchandprice scheme, using the classical branch rule by Ryan and Foster, for the MEBP problem. Finally, we present computational experiments with instances that come from the described applications and also with randomly generated instances. (C) 2011 Elsevier B.V. All rights reserved.



Aledo, J. A., Goles, E., MontalvaMedel, M., Montealegre, P., & Valverde, J. C. (2023). Symmetrizable Boolean networks. Inf. Sci., 626, 787–804.
Abstract: In this work, we provide a procedure that allows us to transform certain kinds of deterministic Boolean networks on minterm or maxterm functions into symmetric ones, so inferring that such symmetrizable networks can present only periodic points of periods 1 or 2. In particular, we deal with generalized parallel (or synchronous) dynamical systems (GPDS) over undirected graphs, i. e., discrete parallel dynamical systems over undirected graphs where some of the selfloops may not appear. We also study the class of antisymmetric GPDS (which are nonsymmetrizable), proving that their periodic orbits have period 4. In addition, we introduce a class of nonsymmetrizable systems which admit periodic orbits with arbitrary large periods.



Allende, H., Salas, R., & Moraga, C. (2003). A robust and effective learning algorithm for feedforward neural networks based on the influence function. Lect. Notes Comput. Sc., 2652, 28–36.
Abstract: The learning process of the Feedforward Artificial Neural Networks relies on the data, though a robustness analysis of the parameter estimates of the model must be done due to the presence of outlying observations in the data. In this paper we seek the robust properties in the parameter estimates in the sense that the influence of aberrant observations or outliers in the estimate is bounded so the neural network is able to model the bulk of data. We also seek a trade off between robustness and efficiency under a Gaussian model. An adaptive learning procedure that seeks both aspects is developed. Finally we show some simulations results applied to the RESEX time series.



Averbakh, I., & Pereira, J. (2018). Lateness Minimization in Pairwise Connectivity Restoration Problems. INFORMS J. Comput., 30(3), 522–538.
Abstract: A network is given whose edges need to be constructed (or restored after a disaster). The lengths of edges represent the required construction/restoration times given available resources, and one unit of length of the network can be constructed per unit of time. All points of the network are accessible for construction at any time. For each pair of vertices, a due date is given. It is required to find a construction schedule that minimizes the maximum lateness of all pairs of vertices, where the lateness of a pair is the difference between the time when the pair becomes connected by an already constructed path and the pair's due date. We introduce the problem and analyze its structural properties, present a mixedinteger linear programming formulation, develop a number of lower bounds that are integrated in a branchandbound algorithm, and discuss results of computational experiments both for instances based on randomly generated networks and for instances based on 2010 Chilean earthquake data.



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.



BorquezParedes, D., Beghelli, A., Leiva, A., Jara, N., Lozada, A., Morales, P., et al. (2022). Agentbased distributed protocol for resource discovery and allocation of virtual networks over elastic optical networks. J. Opt. Commun. Netw., 14(8), 667–679.
Abstract: Network virtualization is a key enabling technology for “Infrastructure as a Service” provisioning, increasing the flexibility and cost savings offered to customers. By extending the concept of server virtualization to the network infrastructure, the allocation of different, independent virtual networks over a single physical network is carried out on demand. A fundamental challenge in network virtualization systems is to choose which physical nodes and links to use for hosting virtual networks in the physical infrastructure, known as the “virtual network allocation” problem. All virtual network allocation proposals on elastic optical networks assume a centralized operation, deploying a single node with access to the network state global information and assigning resources accordingly. However, such configuration might exhibit the inherent problems of centralized systems: survivability and scalability. In this paper, we present a distributed protocol for resource discovery, mapping, and allocation of network virtualization systems. The distributed protocol is generic enough as to be used with different substrate networks. However, in this paper, it has been adapted to work over an elastic optical network infrastructure, where further considerations regarding the spectrum continuity and contiguity constraints must also be taken into account. The distributed protocol is based on the concept of alliances: upon the arrival of a virtual network request, agents located in the physical network nodes compete to form the first alliance able to host the virtual network. Because the first alliances to be formed are also the ones composed by nearby nodes, a good network resource usage is achieved. The feasibility of the distributed protocol was studied by evaluating its ability to successfully establish virtual networks within acceptable time and with low bandwidth consumption from the coordination messages.



BorquezParedes, D., Beghelli, A., Leiva, A., & Murrugarra, R. (2018). Does fragmentation avoidance improve the performance of dynamic spectrum allocation in elastic optical networks? Photonic Netw. Commun., 35(3), 287–299.
Abstract: Most spectrum allocation algorithms in elastic optical networks apply a greedy approach: A new connection is allocated as long as there are enough spectrum slots to accommodate it. Recently, a different approach was proposed. Named DeadlockAvoidance (DA), it only establishes a new connection if the portion of spectrum left after allocating it is zero (fulllink utilization) or is big enough to accommodate future requests. Otherwise, the connection request is blocked as a way to avoid fragmentation. The performance of DA has been evaluated in a singlelink scenario, where its performance is not affected by the slot continuity constraint. In this paper, we evaluate for the first time the blocking performance and fragmentation level of DA in a fully dynamic network scenario with different bitrates and number of slots for a single link, a 4node bus and a mesh topology. The performance was evaluated by simulation, and a lower bound was also derived using a continuous Markov chain model. Results are obtained for DA and three greedy algorithms: First Fit, Exact Fit and FirstLast Fit. Results show that DA significantly decreases fragmentation, and thus, it exhibits a much lower blocking due to fragmentation than the greedy algorithms. However, this decrease is compensated by a new type of blocking due to the selective acceptance of connections. As a result, the extra computational complexity of DA does not compensate a gain in performance.



Calderón, F., Lozada, A., Morales, P., BórquezParedes, 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.



Calderon, F. I., Lozada, A., BorquezParedes, D., Olivares, R., Davalos, E. J., Saavedra, G., et al. (2020). BERAdaptive RMLSA Algorithm for WideArea Flexible Optical Networks. IEEE Access, 8, 128018–128031.
Abstract: Widearea optical networks face significant transmission challenges due to the relentless growth of bandwidth demands experienced nowadays. Network operators must consider the relationship between modulation format and maximum reach for each connection request due to the accumulation of physical layer impairments in optical fiber links, to guarantee a minimum quality of service (QoS) and quality of transmission (QoT) to all connection requests. In this work, we present a BERadaptive solution to solve the routing, modulation format, and spectrum assignment (RMLSA) problem for widearea elastic optical networks. Our main goal is to maximize successful connection requests in widearea networks while choosing modulation formats with the highest efficiency possible. Consequently, our technique uses an adaptive biterrorrate (BER) threshold to achieve communication with the best QoT in the most efficient manner, using the strictest BER value and the modulation format with the smallest bandwidth possible. Additionally, the proposed algorithm relies on 3R regeneration devices to enable longdistances communications if transparent communication cannot be achieved. We assessed our method through simulations for various network conditions, such as the number of regenerators per node, traffic load per user, and BER threshold values. In a scenario without regenerators, the BERAdaptive algorithm performs similarly to the most relaxed fixed BER threshold studied in blocking probability. However, it ensures a higher QoT to most of the connection requests. The proposed algorithm thrives with the use of regenerators, showing the best performance among the studied solutions, enabling longdistance communications with a high QoT and low blocking probability.



Canals, C., Maroulis, S., Canessa, E., Chaigneau, S., & Mizala, A. (2022). Mechanisms Underlying ChoiceSet Formation: The Case of School Choice in Chile. Soc. Sci. Comput. Rev., Early Access.
Abstract: Many decisions involve selecting among many more options than an individual can effectively examine and consider. Therefore, people usually consider smaller and different “choice sets” as viable options. To better understand the processes affecting choiceset formation, we developed a computational model of how households become aware of potential choices in a context for which understanding household decisionmaking has important public policy implications: marketbased reforms in education. In the model, households learn about the schools to which they can send their children through three mechanisms: find out about geographically proximate schools, access to publicly available information, and information gathered from interactions with other households. We calibrated the model using data from four cities in Chile, where students are not required to attend their neighborhood school. We then used the model to conduct hypothetical computational experiments that assessed how each mechanism impacted the sets of schools known to households before they make their choice (their “awareness set”). We found that the inclusion of a social interaction mechanism was crucial for producing simulated awareness sets that matched the awareness sets provided in a survey conducted by the Chilean Ministry of Education. We also found that the social interaction mechanism played the largest role in determining the quality and price range of the choices available in households’ awareness sets. Our findings highlight the importance of social interactions in a stage of decisionmaking before the direct impact of other individuals is typically made explicit. Moreover, it validates an approach that can be used in future models where understanding how decisionmakers become aware of their options may be as important as the way they choose among them.



Cho, A. D., Carrasco, R. A., & Ruz, G. A. (2022). A RUL Estimation System from Clustered RuntoFailure Degradation Signals. Sensors, 22(14), 5323.
Abstract: The prognostics and health management disciplines provide an efficient solution to improve a system's durability, taking advantage of its lifespan in functionality before a failure appears. Prognostics are performed to estimate the system or subsystem's remaining useful life (RUL). This estimation can be used as a supply in decisionmaking within maintenance plans and procedures. This work focuses on prognostics by developing a recurrent neural network and a forecasting method called Prophet to measure the performance quality in RUL estimation. We apply this approach to degradation signals, which do not need to be monotonical. Finally, we test our system using data from new generation telescopes in realworld applications.



Cho, A. D., Carrasco, R. A., & Ruz, G. A. (2022). Improving Prescriptive Maintenance by Incorporating PostPrognostic Information Through Chance Constraints. IEEE Access, 10, 55924–55932.
Abstract: Maintenance is one of the critical areas in operations in which a careful balance between preventive costs and the effect of failures is required. Thanks to the increasing data availability, decisionmakers can now use models to better estimate, evaluate, and achieve this balance. This work presents a maintenance scheduling model which considers prognostic information provided by a predictive system. In particular, we developed a prescriptive maintenance system based on runtofailure signal segmentation and a Long Short Term Memory (LSTM) neural network. The LSTM network returns the prediction of the remaining useful life when a fault is present in a component. We incorporate such predictions and their inherent errors in a decision support system based on a stochastic optimization model, incorporating them via chance constraints. These constraints control the number of failed components and consider the physical distance between them to reduce sparsity and minimize the total maintenance cost. We show that this approach can compute solutions for relatively large instances in reasonable computational time through experimental results. Furthermore, the decisionmaker can identify the correct operating point depending on the balance between costs and failure probability.



ColiniBaldeschi, R., Cominetti, R., & Scarsini, M. (2019). Price of Anarchy for Highly Congested Routing Games in Parallel Networks. Theor. Comput. Syst., 63(1), 90–113.
Abstract: We consider nonatomic routing games with one source and one destination connected by multiple parallel edges. We examine the asymptotic behavior of the price of anarchy as the inflow increases. In accordance with some empirical observations, we prove that under suitable conditions on the costs the price of anarchy is asymptotic to one. We show with some counterexamples that this is not always the case, and that these counterexamples already occur in simple networks with only 2 parallel links.



Cortes, C. E., JaraMoroni, P., Moreno, E., & Pineda, C. (2013). Stochastic transit equilibrium. Transp. Res. Pt. BMethodol., 51, 29–44.
Abstract: We present a transit equilibrium model in which boarding decisions are stochastic. The model incorporates congestion, reflected in higher waiting times at bus stops and increasing invehicle travel time. The stochastic behavior of passengers is introduced through a probability for passengers to choose boarding a specific bus of a certain service. The modeling approach generates a stochastic commonlines problem, in which every line has a chance to be chosen by each passenger. The formulation is a generalization of deterministic transit assignment models where passengers are assumed to travel according to shortest hyperpaths. We prove existence of equilibrium in the simplified case of parallel lines (stochastic commonlines problem) and provide a formulation for a more general network problem (stochastic transit equilibrium). The resulting waiting time and network load expressions are validated through simulation. An algorithm to solve the general stochastic transit equilibrium is proposed and applied to a sample network; the algorithm works well and generates consistent results when considering the stochastic nature of the decisions, which motivates the implementation of the methodology on a realsize network case as the next step of this research. (C) 2013 Elsevier Ltd. All rights reserved.



D'Angelo, G., Di Stefano, G., Navarra, A., Nisse, N., & Suchan, K. (2015). Computing on Rings by Oblivious Robots: A Unified Approach for Different Tasks. Algorithmica, 72(4), 1055–1096.
Abstract: A set of autonomous robots have to collaborate in order to accomplish a common task in a ringtopology where neither nodes nor edges are labeled (that is, the ring is anonymous). We present a unified approach to solve three important problems: the exclusive perpetual exploration, the exclusive perpetual clearing, and the gathering problems. In the first problem, each robot aims at visiting each node infinitely often while avoiding that two robots occupy a same node (exclusivity property); in exclusive perpetual clearing (also known as graph searching), the team of robots aims at clearing the whole ring infinitely often (an edge is cleared if it is traversed by a robot or if both its endpoints are occupied); and in the gathering problem, all robots must eventually occupy the same node. We investigate these tasks in the LookComputeMove model where the robots cannot communicate but can perceive the positions of other robots. Each robot is equipped with visibility sensors and motion actuators, and it operates in asynchronous cycles. In each cycle, a robot takes a snapshot of the current global configuration (Look), then, based on the perceived configuration, takes a decision to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case it eventually moves to this neighbor (Move). Moreover, robots are endowed with very weak capabilities. Namely, they are anonymous, asynchronous, oblivious, uniform (execute the same algorithm) and have no common sense of orientation. In this setting, we devise algorithms that, starting from an exclusive and rigid (i.e. aperiodic and asymmetric) configuration, solve the three above problems in anonymous ringtopologies.



EscapilInchauspé, P., & Ruz, G. A. (2023). Hyperparameter tuning of physicsinformed neural networks: Application to Helmholtz problems. Neurocomputing, 561, 126826.
Abstract: We consider physicsinformed neural networks (PINNs) (Raissiet al., 2019) for forward physical problems. In order to find optimal PINNs configuration, we introduce a hyperparameter optimization (HPO) procedure via Gaussian processesbased Bayesian optimization. We apply the HPO to Helmholtz equation for bounded domains and conduct a thorough study, focusing on: (i) performance, (ii) the collocation points density r and (iii) the frequency kappa, confirming the applicability and necessity of the method. Numerical experiments are performed in two and three dimensions, including comparison to finite element methods.



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.



Goles, E., & Montealegre, P. (2014). Computational complexity of threshold automata networks under different updating schemes. Theor. Comput. Sci., 559, 3–19.
Abstract: Given a threshold automata network, as well as an updating scheme over its vertices, we study the computational complexity associated with the prediction of the future state of a vertex. More precisely, we analyze two classes of local functions: the majority and the ANDOR rule (vertices take the AND or the OR logic functions over the state of its neighborhoods). Depending on the updating scheme, we determine the complexity class (NC, P, NP, PSPACE) where the prediction problem belongs. (C) 2014 Elsevier B.V. All rights reserved.



Goles, E., & Montealegre, P. (2015). The complexity of the majority rule on planar graphs. Adv. Appl. Math., 64, 111–123.
Abstract: We study the complexity of the majority rule on planar automata networks. We reduce a special case of the Monotone Circuit Value Problem to the prediction problem of determining if a vertex of a planar graph will change its state when the network is updated with the majority rule. (C) 2014 Elsevier Inc. All rights reserved.



Goles, E., & Ruz, G. A. (2015). Dynamics of neural networks over undirected graphs. Neural Netw., 63, 156–169.
Abstract: In this paper we study the dynamical behavior of neural networks such that their interconnections are the incidence matrix of an undirected finite graph G = (V, E) (i.e., the weights belong to {0, 1}). The network may be updated synchronously (every node is updated at the same time), sequentially (nodes are updated one by one in a prescribed order) or in a blocksequential way (a mixture of the previous schemes). We characterize completely the attractors (fixed points or cycles). More precisely, we establish the convergence to fixed points related to a parameter alpha(G), taking into account the number of loops, edges, vertices as well as the minimum number of edges to remove from E in order to obtain a maximum bipartite graph. Roughly, alpha(G') < 0 for any G' subgraph of G implies the convergence to fixed points. Otherwise, cycles appear. Actually, for very simple networks (majority functions updated in a blocksequential scheme such that each block is of minimum cardinality two) we exhibit cycles with nonpolynomial periods. (C) 2014 Elsevier Ltd. All rights reserved.

