Home  << 1 >> 
Lagos, T., Armstrong, M., HomemdeMello, T., Lagos, G., & Saure, D. (2021). A framework for adaptive openpit mining planning under geological uncertainty. Optim. Eng., Early Access, 36 pp.
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.

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.

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.

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

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.

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.
Keywords: FPT algorithms; Treewidth; Potential maximal cliques

Pereira, J., Ritt, M., & Vasquez, O. C. (2018). A memetic algorithm for the costoriented robotic assembly line balancing problem. Comput. Oper. Res., 99, 249–261.
Abstract: In order to minimize costs, manufacturing companies have been relying on assembly lines for the mass production of commodity goods. Among other issues, the successful operation of an assembly line requires balancing work among the stations of the line in order to maximize its efficiency, a problem known in the literature as the assembly line balancing problem, ALBP. In this work, we consider an ALBP in which task assignment and equipment decisions are jointly considered, a problem that has been denoted as the robotic ALBP. Moreover, we focus on the case in which equipment has different costs, leading to a costoriented formulation. In order to solve the problem, which we denote as the costoriented robotic assembly line balancing problem, cRALBP, a hybrid metaheuristic is proposed. The metaheuristic embeds results obtained for two special cases of the problem within a genetic algorithm in order to obtain a memetic algorithm, applicable to the general problem. An extensive computational experiment shows the advantages of the hybrid approach and how each of the components of the algorithm contributes to the overall ability of the method to obtain good solutions. (C) 2018 Elsevier Ltd. All rights reserved.

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.

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.

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.

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.

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.

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.

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.

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.

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.
