Home  << 1 2 3 4 5 >> 
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.

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.

Aracena, J., Demongeot, J., Fanchon, E., & Montalva, M. (2013). On the number of different dynamics in Boolean networks with deterministic update schedules. Math. Biosci., 242(2), 188–194.
Abstract: Deterministic Boolean networks are a type of discrete dynamical systems widely used in the modeling of genetic networks. The dynamics of such systems is characterized by the local activation functions and the update schedule, i.e., the order in which the nodes are updated. In this paper, we address the problem of knowing the different dynamics of a Boolean network when the update schedule is changed. We begin by proving that the problem of the existence of a pair of update schedules with different dynamics is NPcomplete. However, we show that certain structural properties of the interaction digraph are sufficient for guaranteeing distinct dynamics of a network. In [1] the authors define equivalence classes which have the property that all the update schedules of a given class yield the same dynamics. In order to determine the dynamics associated to a network, we develop an algorithm to efficiently enumerate the above equivalence classes by selecting a representative update schedule for each class with a minimum number of blocks. Finally, we run this algorithm on the well known Arabidopsis thaliana network to determine the full spectrum of its different dynamics. (C) 2013 Elsevier Inc. All rights reserved.
Keywords: Boolean network; Update schedule; Update digraph; Dynamics

Aracena, J., Goles, E., Moreira, A., & Salinas, L. (2009). On the robustness of update schedules in Boolean networks. Biosystems, 97(1), 1–8.
Abstract: Deterministic Boolean networks have been used as models of gene regulation and other biological networks. One key element in these models is the update schedule, which indicates the order in which states are to be updated. We study the robustness of the dynamical behavior of a Boolean network with respect to different update schedules (synchronous, blocksequential, sequential), which can provide modelers with a better understanding of the consequences of changes in this aspect of the model. For a given Boolean network, we define equivalence classes of update schedules with the same dynamical behavior, introducing a labeled graph which helps to understand the dependence of the dynamics with respect to the update, and to identify interactions whose timing may be crucial for the presence of a particular attractor of the system. Several other results on the robustness of update schedules and of dynamical cycles with respect to update schedules are presented. Finally, we prove that our equivalence classes generalize those found in sequential dynamical systems. (C) 2009 Elsevier Ireland Ltd. All rights reserved.
Keywords: Boolean network; Update schedule; Robustness; Attractor; Dynamical cycle

Averbakh, I., & Pereira, J. (2021). Tree optimization based heuristics and metaheuristics in network construction problems. Comput. Oper. Res., 128, 105190.
Abstract: We consider a recently introduced class of network construction problems where edges of a transportation network need to be constructed by a server (construction crew). The server has a constant construction speed which is much lower than its travel speed, so relocation times are negligible with respect to construction times. It is required to find a construction schedule that minimizes a nondecreasing function of the times when various connections of interest become operational. Most problems of this class are strongly NPhard on general networks, but are often treeefficient, that is, polynomially solvable on trees. We develop a generic local search heuristic approach and two metaheuristics (Iterated Local Search and Tabu Search) for solving treeefficient network construction problems on general networks, and explore them computationally. Results of computational experiments indicate that the methods have excellent performance.
Keywords: Network design; Scheduling; Network construction; Heuristics; Metaheuristics; Local search

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., Cancela, H., & Moreno, E. (2015). Topological optimization of reliable networks under dependent failures. Oper. Res. Lett., 43(2), 132–136.
Abstract: We address the design problem of a reliable network. Previous work assumes that link failures are independent. We discuss the impact of dropping this assumption. We show that under a commoncause failure model, dependencies between failures can affect the optimal design. We also provide an integerprogramming formulation to solve this problem. Furthermore, we discuss how the dependence between the links that participate in the solution and those that do not can be handled. Other dependency models are discussed as well. (C) 2014 Elsevier B.V. All rights reserved.

Barrera, J., Moreno, E., Munoz, G., & Romero, P. (2022). Exact reliability optimization for seriesparallel graphs using convex envelopes. Networks, 80(2), 235–248.
Abstract: Given its wide spectrum of applications, the classical problem of allterminal network reliability evaluation remains a highly relevant problem in network design. The associated optimization problemto find a network with the best possible reliability under multiple constraintspresents an even more complex challenge, which has been addressed in the scientific literature but usually under strong assumptions over failures probabilities and/or the network topology. In this work, we propose a novel reliability optimization framework for network design with failures probabilities that are independent but not necessarily identical. We leverage the lineartime evaluation procedure for network reliability in the seriesparallel graphs of Satyanarayana and Wood (1985) to formulate the reliability optimization problem as a mixedinteger nonlinear optimization problem. To solve this nonconvex problem, we use classical convex envelopes of bilinear functions, introduce custom cutting planes, and propose a new family of convex envelopes for expressions that appear in the evaluation of network reliability. Furthermore, we exploit the refinements produced by spatial branchandbound to locally strengthen our convex relaxations. Our experiments show that, using our framework, one can efficiently obtain optimal solutions in challenging instances of this problem.

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.
Keywords: Income taxes; Markov processes; Networks; Algorithms

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.
Keywords: Elastic Optical Networks; Multiband; Band Allocation

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.

Canessa, E., & Riolo, R. L. (2006). An agentbased model of the impact of computermediated communication on organizational culture and performance: an example of the application of complex systems analysis tools to the study of CIS. J. Inf. Technol., 21(4), 272–283.
Abstract: Organizations that make use of computer information systems (CIS) are prototypical complex adaptive systems (CAS). This paper shows how an approach from Complexity Science, exploratory agentbased modeling (ABM), can be used to study the impact of two different modes of use of computermediated communication (CMC) on organizational culture (OC) and performance. The ABM includes stylized representations of (a) agents communicating with other agents to complete tasks; (b) an OC consisting of the distribution of agent traits, changing as agents communicate; (c) the effect of OC on communication effectiveness (CE), and (d) the effect of CE on task completion times, that is, performance. If CMC is used in a broad mode, that is, to contact and collaborate with many, new agents, the development of a strong OC is slowed, leading to decreased CE and poorer performance early on. If CMC is used in a local mode, repeatedly contacting the same agents, a strong OC develops rapidly, leading to increased CE and high performance early on. However, if CMC is used in a broad mode over longer time periods, a strong OC can develop over a wider set of agents, leading to an OC that is stronger than an OC which develops with local CMC use. Thus broad use of CMC results in overall CE and performance that is higher than is generated by local use of CMC. We also discuss how the dynamics generated by an ABM can lead to a deeper understanding of the behavior of a CAS, for example, allowing us to better design empirical longitudinal studies.

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.
Keywords: prognostics; fault detection; recurrent neural networks; prophet

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.

Cohen, Y. M., Keskinocak, P., & Pereira, J. (2021). A note on the flowtime network restoration problem. IISE Trans., 53(12), 1351–1352.
Abstract: The flowtime network restoration problem was introduced by Averbakh and Pereira (2012) who presented a Minimum Spanning Tree heuristic, two local search procedures, and an exact branchandbound algorithm. This note corrects the computational results in Averbakh and Pereira (2012).
