Bruno Vieira, Ana Viana, Manuel Matos, and João Pedro Pedroso. A multiple criteria utility-based approach for unit commitment with wind power and pumped storage hydro. Electric Power Systems Research, 131:244 - 254, 2016. [ bib | DOI | http | .pdf ]
Abstract The integration of wind power in electricity generation brings new challenges to the unit commitment problem, as a result of the random nature of the wind speed. The scheduling of thermal generation units at the day-ahead stage is usually based on wind power forecasts. Due to technical limitations of thermal units, deviations from those forecasts during intra-day operations may lead to unwanted consequences, such as load shedding and increased operating costs. Wind power forecasting uncertainty has been handled in practice by means of conservative stochastic scenario-based optimization models, or through additional operating reserve settings. However, generation companies may have different attitudes towards the risks associated to wind power variability. In this paper, operating costs and load shedding are modeled by non-linear utility functions aggregated into a single additive utility function of a multi-objective model. Computational experiments have been done to validate the approach: firstly we test our model for the wind–thermal unit commitment problem and, in a second stage, pumped storage hydro units are added, leading to a model with wind–hydro-thermal coordination. Results have shown that the proposed methodology is able to correctly reflect different risk profiles of decision makers for both models.
Keywords: Multiple criteria analysis
Filipe Brandão and João Pedro Pedroso. Bin packing and related problems: General arc-flow formulation with graph compression. Computers & Operations Research, 69:56 - 67, 2016. [ bib | DOI | http | .pdf ]
Abstract We present an exact method, based on an arc-flow formulation with side constraints, for solving bin packing and cutting stock problems—including multi-constraint variants—by simply representing all the patterns in a very compact graph. Our method includes a graph compression algorithm that usually reduces the size of the underlying graph substantially without weakening the model. Our formulation is equivalent to Gilmore and Gomory׳s, thus providing a very strong linear relaxation. However, instead of using column-generation in an iterative process, the method constructs a graph, where paths from the source to the target node represent every valid packing pattern. The same method, without any problem-specific parameterization, was used to solve a large variety of instances from several different cutting and packing problems. In this paper, we deal with vector packing, bin packing, cutting stock, cardinality constrained bin packing, cutting stock with cutting knife limitation, bin packing with conflicts, and other problems. We report computational results obtained with many benchmark test datasets, some of them showing a large advantage of this formulation with respect to the traditional ones.
Keywords: Bin packing
Xenia Klimentova, João Pedro Pedroso, and Ana Viana. Maximising expectation of the number of transplants in kidney exchange programmes. Computers & Operations Research, 73:1 - 11, 2016. [ bib | DOI | http | .pdf ]
This paper addresses the problem of maximising the expected number of transplants in kidney exchange programmes. New schemes for matching rearrangement in case of failure are presented, along with a new tree search algorithm used for the computation of optimal expected values. Extensive computational experiments demonstrate the effectiveness of the algorithm and reveal a clear superiority of a newly proposed scheme, subset-recourse, as compared to previously known approaches.
Keywords: Kidney exchange programmes
João Pedro Pedroso, Sílvia Cunha, and João Nuno Tavares. Recursive circle packing problems. International Transactions in Operational Research, 23(1-2):355-368, 2016. [ bib | DOI | http | .pdf ]
Keywords: packing problems, knapsack problems, heuristics, practice of OR, combinatorial optimization, integer programming, loading problems, local search
Margarida Carvalho, Andrea Lodi, João Pedro Pedroso, and Ana Viana. Nash equilibria in the two-player kidney exchange game. Mathematical Programming, pages 1-29, 2016. [ bib | DOI | http ]
Kidney exchange programs have been set in several countries within national, regional or hospital frameworks, to increase the possibility of kidney patients being transplanted. For the case of hospital programs, it has been claimed that hospitals would benefit if they collaborated with each other, sharing their internal pools and allowing transplants involving patients of different hospitals. This claim led to the study of multi-hospital exchange markets. We propose a novel direction in this setting by modeling the exchange market as an integer programming game. The analysis of the strategic behavior of the entities participating in the kidney exchange game allowed us to prove that the most rational game outcome maximizes the social welfare and that it can be computed in polynomial time.
Teresa Neto, Miguel Constantino, Isabel Martins, and João Pedro Pedroso. Forest harvest scheduling with clearcut and core area constraints. Annals of Operations Research, 9 2016. [ bib | DOI | http ]
Many studies regarding environmental concerns in forest harvest scheduling problems deal with constraints on the maximum clearcut size. However, these constraints tend to disperse harvests across the forest and thus to generate a more fragmented landscape. When a forest is fragmented, the amount of edge increases at the expense of the core area. Highly fragmented forests can neither provide the food, cover, nor the reproduction needs of core-dependent species. This study presents a branch-and-bound procedure designed to find good feasible solutions, in a reasonable time, for forest harvest scheduling problems with constraints on maximum clearcut size and minimum core habitat area. The core area is measured by applying the concept of subregions. In each branch of the branch-and-bound tree, a partial solution leads to two children nodes, corresponding to the cases of harvesting or not a given stand in a given period. Pruning is based on constraint violations or unreachable objective values. The approach was tested with forests ranging from some dozens to more than a thousand stands. In general, branch-and-bound was able to quickly find optimal or good solutions, even for medium/large instances.
Vítor Rodrigues, Benny Akesson, Mário Florido, Simão Melo de Sousa, João Pedro Pedroso, and Pedro Vasconcelos. Certifying execution time in multicores. Science of Computer Programming, 111(P3):505-534, November 2015. [ bib | DOI | http | .pdf ]
Abstract This article presents a semantics-based program verification framework for critical embedded real-time systems using the worst-case execution time (WCET) as the safety parameter. The verification algorithm is designed to run on devices with limited computational resources where efficient resource usage is a requirement. For this purpose, the framework of abstract-carrying code (ACC) is extended with an additional verification mechanism for linear programming (LP) by applying the certifying properties of duality theory to check the optimality of {WCET} estimates. Further, the {WCET} verification approach preserves feasibility and scalability when applied to multicore architectural models. The certifying {WCET} algorithm is targeted to architectural models based on the {ARM} instruction set and is presented as a particular instantiation of a compositional data-flow framework supported on the theoretic foundations of denotational semantics and abstract interpretation. The data-flow framework has algebraic properties that provide algorithmic transformations to increase verification efficiency, mainly in terms of verification time. The {WCET} analysis/verification on multicore architectures applies the formalism of latency-rate ( {LR} ) servers, and proves its correcteness in the context of abstract interpretation, in order to ease {WCET} estimation of programs sharing resources.
Keywords: Abstract interpretation
João P. Pedroso and Rui Rei. Tree search and simulation. In Miguel Mujica Mota, Idalia Flores De La Mota, and Daniel Guimarans Serrano, editors, Applied Simulation and Optimization, pages 109-131. Springer International Publishing, 2015. [ bib | DOI | http | .pdf ]
This chapter presents a methodology for embodying simulation as part of a tree search procedure, as a technique for solving practical problems in combinatorial optimization. Target problems either are difficult to express as mixed integer optimization models, or have models which provide rather loose bounds; in both cases, traditional, exact methods typically fail. The idea used is to have tree search instantiating part of the variables, in a systematic way, and for that particular instantiation-a node in the search tree-resort to a simulation for assigning values to the remaining variables; then, use the outcome of the simulation for evaluating that node in the tree. This method has been used with considerable success in game playing, but has received very limited attention as a tool for optimization. Nevertheless, it has great potential, either as a way for improving known heuristics or as an alternative to metaheuristics. We depart from repeated, randomized simulation based on problem-specific heuristics for applications in scheduling, logistics, and packing, and show how the systematic search in a tree improves the results that can be obtained.
João P. Pedroso, Mikio Kubo, and Ana Viana. Unit commitment with valve-point loading effect. Technical Report DCC-2014-05, DCC, Faculdade de Ciências, Universidade do Porto, 2014. [ bib | .pdf ]
Valve-point loading affects the input-output characteristics of generating units, bringing the fuel costs nonlinear and nonsmooth. This has been considered in the solution of load dispatch problems, but not in the planning phase of unit commitment. This paper presents a mathematical optimization model for the thermal unit commitment problem considering valve-point loading. The formulation is based on a careful linearization of the fuel cost function, which is modeled with great detail on power regions being used in the current solution, and roughly on other regions. A set of benchmark instances for this problem is used for analyzing the method, with recourse to a general-purpose mixed-integer optimization solver.
Margarida Carvalho, João P. Pedroso, and João Saraiva. Electricity day-ahead markets: Computation of nash equilibria. Journal of Industrial and Management Optimization, 11(3):985-998, 2014. [ bib | DOI | http | .pdf ]
In a restructured electricity sector, day-ahead markets can be modeled as a game where some players - the producers - submit their proposals. To analyze the companies' behavior we have used the concept of Nash equilibrium as a solution in these multi-agent interaction problems. In this paper, we present new and crucial adaptations of two well-known mechanisms, the adjustment process and the relaxation algorithm, in order to achieve the goal of computing Nash equilibria. The advantages of these approaches are highlighted and compared with those available in the literature.
Filipe Brandão and João Pedro Pedroso. Fast pattern-based algorithms for cutting stock. Computers & Operations Research, 48:69-80, 2014. [ bib | DOI | http | .pdf ]
The conventional assignment-based first/best fit decreasing algorithms (FFD/BFD) are not polynomial in the one-dimensional cutting stock input size in its most common format. Therefore, even for small instances with large demands, it is difficult to compute FFD/BFD solutions. We present pattern-based methods that overcome the main problems of conventional heuristics in cutting stock problems by representing the solution in a much more compact format. Using our pattern-based heuristics, FFD/BFD solutions for extremely large cutting stock instances, with billions of items, can be found in a very short amount of time.
Keywords: Cutting stock
Nicolau Santos, Rui Rebelo, and João P. Pedroso. A tabu search for the flowshop scheduling problem with sequence dependent setup times. International Journal of Data Analysis Techniques and Strategies, 6(3):275-285, 2014. [ bib | .pdf ]
In this work we present a tabu search metaheuristic method for solving the permutation flow shop scheduling problem with sequence dependent setup times and the objective of minimizing total weighted tardiness. The problem is well known for its practical applications and for the difficulty in obtaining good solutions. The tabu search method proposed is based on the insertion neighborhood, and is characterized by the selection and evaluation of a small subset of this neighborhood at each iteration; this has consequences both on diversification and intensification of the search. We also propose a speed-up technique based on book keeping information of the current solution, used for the evaluation of its neighbors.
Dewan Fayzur Rahman, Ana Viana, and João Pedro Pedroso. Metaheuristic search based methods for unit commitment. International Journal of Electrical Power and Energy Systems, 59(0):14 - 22, 2014. [ bib | DOI | http | .pdf ]
This paper presents two new solution approaches capable of finding optimal solutions for the thermal unit commitment problem in power generation planning. The approaches explore the concept of "matheuristics", a term usually used to refer to an optimization algorithm that hybridizes (meta)heuristics with mixed integer programming solvers, in order to speed up convergence to optimality for large scale instances. Two algorithms are proposed: "local branching", and an hybridization of particle swarm optimization with a mixed integer programming solver. From extensive computational tests on a broad set of benchmarks, the algorithms were found to be able to solve large instances. Optimal solutions were obtained for several well-known situations with dramatic reductions in CPU time for the larger cases, when compared to previously proposed exact methods.
Keywords: Unit commitment
João Pedro Pedroso. Maximizing expectation on vertex-disjoint cycle packing. In Beniamino Murgante, Sanjay Misra, Ana Maria A.C. Rocha, Carmelo Torre, Jorge Gustavo Rocha, Maria Irene Falcão, David Taniar, Bernady O. Apduhan, and Osvaldo Gervasi, editors, Computational Science and Its Applications - ICCSA 2014, volume 8580 of Lecture Notes in Computer Science, pages 32-46. Springer International Publishing, 2014. [ bib | DOI | http | .pdf ]
This paper proposes a method for computing the expectation for the length of a maximum set of vertex-disjoint cycles in a digraph where vertices and/or arcs are subject to failure with a known probability. This method has an immediate practical application: it can be used for the solution of a kidney exchange program in the common situation where the underlying graph is unreliable. Results for realistic benchmark instances are reported and analyzed.
Keywords: Kidney exchange programs; Cycle packing; Expectation optimization; Combinatorial optimization
João Pedro Pedroso. Optimization and artificial intelligence for smart devices. In T-Engine Forum, Tokyo, Japan, 2014. IEEE Consumer Electronics Society. [ bib | .pdf ]
Dewan Fayzur Rahman, Ana Viana, and João Pedro Pedroso. A MILP-based approach for hydrothermal scheduling. In Stefan Helber, Michael Breitner, Daniel Rösch, Cornelia Schön, Johann-Matthias Graf von der Schulenburg, Philipp Sibbertsen, Marc Steinbach, Stefan Weber, and Anja Wolter, editors, Operations Research Proceedings 2012, Operations Research Proceedings, pages 157-162. Springer International Publishing, 2014. [ bib | DOI | http | .pdf ]
This paper presents new solution approaches capable of finding optimal solutions for the Hydrothermal Scheduling Problem (HSP) in power generation planning. The problem has been proven to be NP-hard and no exact methods have been able to tackle it, for problem sizes of practical relevance. We explore three approaches. The first method is an iterative algorithm that has been successfully used previously to solve the thermal commitment problem. The two other methods are "Local Branching" and a hybridization of "Particle Swarm Optimization" with a general purpose solver. Computational experiments show that the iterative piecewise linear approximation method outperforms more elaborated approaches, indicating that recourse to matheuristics for solving this problem is not necessary.
Filipe Brandão and João P. Pedroso. Bin packing and related problems: General arc-flow formulation with graph compression. Technical Report DCC-2013-08, DCC, Faculdade de Ciências, Universidade do Porto, 2013. [ bib | .pdf ]
We present an exact method, based on an arc-flow formulation with side constraints, for solving bin packing and cutting stock problems - including multi-constraint variants - by simply representing all the patterns in a very compact graph. Our method includes a graph compression algorithm that usually reduces the size of the underlying graph substantially without weakening the model. As opposed to our method, which provides strong models, conventional models are usually highly symmetric and provide very weak lower bounds. Our formulation is equivalent to Gilmore and Gomory's, thus providing a very strong linear relaxation. However, instead of using column-generation in an iterative process, the method constructs a graph, where paths from the source to the target node represent every valid packing pattern. The same method, without any problem-specific parameterization, was used to solve a large variety of instances from several different cutting and packing problems. In this paper, we deal with vector packing, graph coloring, bin packing, cutting stock, cardinality constrained bin packing, cutting stock with cutting knife limitation, cutting stock with binary patterns, bin packing with conflicts, and cutting stock with binary patterns and forbidden pairs. We report computational results obtained with many benchmark test data sets, all of them showing a large advantage of this formulation with respect to the traditional ones.
Filipe Brandão and João P. Pedroso. Cutting stock with binary patterns: Arc-flow formulation with graph compression. Technical Report DCC-2013-09, DCC, Faculdade de Ciências, Universidade do Porto, 2013. [ bib | .pdf ]
The cutting stock problem with binary patterns (0-1 CSP) is a variant of CSP that usually appears as a relaxation of 2D and 3D packing problems. We present an exact method, based on an arc-flow formulation with side constraints, for solving 0-1 CSP by simply representing all the patterns in a very compact graph. Gilmore-Gomory's column generation approach is usually used to compute strong lower bounds for 0-1 CSP. We report a computational comparison between the arc-flow approach and the Gilmore-Gomory's approach.
Filipe Brandão and João P. Pedroso. Fast pattern-based algorithms for cutting stock. Technical Report DCC-2013-10, DCC, Faculdade de Ciências, Universidade do Porto, 2013. [ bib | .pdf ]
The conventional assignment-based first/best fit decreasing algorithms (FFD/BFD) are not polynomial in the cutting stock input size in its most common format. Therefore, even for small instances with large demands, it is difficult to compute FFD/BFD solutions. We present pattern-based methods that overcome the main problems of conventional heuristics in cutting stock problems by representing the solution in a much more compact format. Using our pattern-based heuristics, FFD/BFD solutions for extremely large cutting stock instances, with billions of items, can be found in a very short amount of time.
Filipe Brandão and João P. Pedroso. Multiple-choice vector bin packing: Arc-flow formulation with graph compression. Technical Report DCC-2013-13, DCC, Faculdade de Ciências, Universidade do Porto, 2013. [ bib | .pdf ]
The vector bin packing problem (VBP) is a generalization of bin packing with multiple constraints. In this problem we are required to pack items, represented by p-dimensional vectors, into as few bins as possible. The multiple-choice vector bin packing (MVBP) is a variant of the VBP in which bins have several types and items have several incarnations. We present an exact method, based on an arc-flow formulation with graph compression, for solving MVBP by simply representing all the patterns in a very compact graph. As a proof of concept we report computational results on a variable-sized bin packing data set.
Rui Jorge Rei and João Pedro Pedroso. Tree search for the stacking problem. Annals of Operations Research, 203(1):371-388, 2013. [ bib | .pdf ]
The stacking problem is a hard combinatorial optimization problem with high practical interest in, for example, steel storage or container port operations. In this problem, a set of items is stored in a warehouse for a period of time, and a crane is used to place them in a limited number of stacks. Since the entrance and exit of items occurs in an arbitrary order, items may have to be relocated in order to reach and deliver other items below them. The objective of the problem is to find a feasible sequence of movements that delivers all items, while minimizing the total number of movements. We propose two heuristic methods to solve the problem, and study the scalability of an exact approach. The two heuristic approaches are a multiple simulation algorithm using semi-greedy construction heuristics, and a stochastic best-first tree search algorithm. The two methods are compared in a set of challenging instances, revealing a superior performance of the tree search approach in most cases.
Filipe Brandão and João Pedro Pedroso. A complete search method for the relaxed traveling tournament problem. EURO Journal on Computational Optimization, pages 1-10, 2013. [ bib | DOI | http | .pdf ]
The Traveling Tournament Problem (TTP) is a sports scheduling problem that includes two major issues in creating timetables: home/away pattern feasibility and travel distance. In this problem the schedule must be compact: every team plays in every time slot. However, there are some sports leagues that have both home/away pattern restrictions and distance limits, but do not require a compact schedule. In such schedules, one or more teams can have a bye in any time slot. This leads us to a variant of the problem: the Relaxed Traveling Tournament Problem (RTTP). We present a complete search method to solve this problem based on branch-and-bound, metaheuristics and dynamic programming.
Keywords: Traveling tournament problem; Branch-and-bound; Metaheuristics; Dynamic programming; 90-08 Computational methods; 90-XX Operations research; mathematical programming
Ana Viana and J. P. Pedroso. A new MILP-based approach for unit commitment in power production planning. International Journal of Electrical Power and Energy Systems, 44:997-1005, 2013. http://dx.doi.org/10.1016/j.ijepes.2012.08.046. [ bib | .pdf ]
This paper presents a complete, quadratic programming formulation of the standard thermal unit commitment problem in power generation planning, together with a novel iterative optimisation algorithm for its solution. The algorithm, based on a mixed-integer formulation of the problem, considers piecewise linear approximations of the quadratic fuel cost function that are dynamically updated in an iterative way, converging to the optimum; this avoids the requirement of resorting to quadratic programming, making the solution process much quicker. From extensive computational tests on a broad set of benchmark instances of this problem, the algorithm was found to be flexible and capable of easily incorporating different problem constraints. Indeed, it is able to tackle ramp constraints, which although very important in practice were rarely considered in previous publications. Most importantly, optimal solutions were obtained for several well-known benchmark instances, including instances of practical relevance, that are not yet known to have been solved to optimality. Computational experiments and their results showed that the method proposed is both simple and extremely effective.
João P. Pedroso. Maximizing expectation on vertex-disjoint cycle packing. Technical Report DCC-2013-05, DCC, Faculdade de Ciências, Universidade do Porto, 2013. [ bib | .pdf ]
This paper proposes a method for computing the expectation for the length of the maximum set of vertex-disjoint cycles in a digraph where vertices and/or arcs are subject to failure with a known probability. This method has an immediate practical application: it can be used for the solution of a kidney exchange program in the common situation where the underlying graph is unreliable. Results for realistic benchmark instances are reported and analyzed.
Teresa Neto, Miguel Constantino, João P. Pedroso, and Isabel Martins. A branch-and-bound procedure for forest harvest scheduling problems addressing aspects of habitat availability. International Transactions in Operational Research, 20(5):689-709, 2013. [ bib | DOI | http | .pdf ]
In the literature, the most referenced approaches for forest harvesting scheduling problems addressing environmental protection issues have focused mainly on including constraints on clearcut area. Nevertheless, these restrictions may not be sufficient to prevent the loss of habitat availability that endangers the survival of many wild species. This work presents a tree search procedure for finding good feasible solutions, in reasonable times, to forest harvest scheduling problems with constraints on clearcut area and habitat availability. We use two measures for habitat availability: the area of all habitats and the connectivity between them. For solving the problem, we use a tree search procedure: a process inspired in branch-and-bound, specifically designed for this problem. In each branch, a partial solution leads to two children nodes, corresponding to harvesting or not a given stand in a given period. Pruning is based on constraint violations or on unreachable objective values. Preliminary computational results are reported.
Keywords: forestry, branch and bound, integer programming, tree algorithms, scheduling
Rui Jorge Rei and João Pedro Pedroso. Heuristic search for the stacking problem. International Transactions in Operational Research, 19(3):379-395, 2012. http://dx.doi.org/10.1111/j.1475-3995.2011.00831.x. [ bib ]
This paper presents the Stacking Problem, a hard combinatorial optimization problem concerning handling and storage of items in a warehouse, where they are handled by a crane and organized into stacks. We define the problem, study its complexity class, and present a mathematical programming model to solve it. In order to tackle medium- or large-scale instances, we propose a simulation-based algorithm using semi-greedy construction heuristics. This simple approach allows for multiple constructions, finding solutions within reasonable time even for large instances. Three semi-greedy heuristics are proposed and compared in an extensive computational experiment, where we study the relation between the number of constructions and the best solution obtained using each heuristic.
Keywords: Stacking Problem, optimization, simulation, heuristics
Rui Jorge Rei, João Pedro Pedroso, Hideitsu Hino, and Noboru Murata. A tree search approach to sparse coding. In Youssef Hamadi and Marc Schoenauer, editors, LION, volume 7219 of Lecture Notes in Computer Science, pages 472-477. Springer, 2012. [ bib | .pdf ]
Sparse coding is an important optimization problem with numerous applications. In this paper, we describe the problem and the commonly used pursuit methods, and propose a best-first tree search algorithm employing multiple queues for unexplored tree nodes. We assess the effectiveness of our method in an extensive computational experiment, showing its superiority over other methods even for modest computational time.
Vítor Rodrigues, João Pedro Pedroso, Mário Florido, and Simão Melo de Sousa. Certifying execution time. In Ricardo Peña, Marko C. J. D. van Eekelen, and Olha Shkaravska, editors, FOPARA, volume 7177 of Lecture Notes in Computer Science, pages 108-125. Springer, 2011. [ bib ]
João P. Pedroso and Yves Smeers. Equilibria on a game with discrete variables. In Fernando Ferreira, Hélia Guerra, Elvira Mayordomo, and João Rasga, editors, Programs, Proofs, Processes, pages 326-335, Azores, Portugal, 2010. Computability in Europe 2010. [ bib | .pdf ]
Equilibrium in Economics has been seldom addressed in a situation where some variables are discrete. This work introduces a problem related to lot-sizing with several players, and analyses some strategies which are likely to be found in real world games. An illustration with a simple example is presented, with concerns about the difficulty of the problem and computation possibilities.
João Pedro Pedroso. Metaheuristics for the asymmetric hamiltonian path problem. In Ivan Dimov, Stefka Dimova, and Natalia T. Kolkovska, editors, NMA, volume 6046 of Lecture Notes in Computer Science, pages 272-279. Springer, 2010. [ bib | .pdf ]
One of the most important applications of the Asymmetric Hamiltonian Path Problem is in scheduling. In this paper we describe a variant of this problem, and develop both a mathematical programming formulation and simple metaheuristics for solving it. The formulation is based on a transformation of the input data, in such a way that a standard mathematical programming model for the Asymmetric Travelling Salesman Problem can be used on this slightly different problem. Two standard metaheuristics for the asymmetric travelling salesman are proposed and analysed on this variant: repeated random construction followed by local search with the 3-Exchange neighbourhood, and iterated local search based on the same neighbourhood and on a 4-Exchange perturbation. The computational results obtained show the interest and the complementary merits of using a mixed-integer programming solver and an approximative method for the solution of this problem.
João P. Pedroso and Mikio Kubo. Heuristics and exact methods for number partitioning. European Journal of Operational Research, 202:73-81, 2010. [ bib | DOI | http | .pdf ]
Number partitioning is a classical NP-hard combinatorial optimization problem, whose solution is challenging for both exact and approximative methods. This work presents a new algorithm for number partitioning, based on ideas drawn from branch-and-bound, breadth first search, and beam search. A new set of benchmark instances for this problem is also proposed. The behavior of the new method on this and other test beds is analyzed and compared to other well known heuristics and exact algorithms.
Pedro Pereira Rodrigues, João Gama, and João P. Pedroso. Hierarchical clustering of time series data streams. IEEE Transactions on Knowledge and Data Engineering, 20(5):615-627, May 2008. [ bib | http ]
This paper presents and analyzes an incremental system for clustering streaming time series. The Online Divisive-Agglomerative Clustering (ODAC) system continuously maintains a tree-like hierarchy of clusters that evolves with data. ODAC uses a top-down strategy. The splitting criterion is a correlation-based dissimilarity measure among time series, splitting each node by the farthest pair of streams, which defines the diameter of the cluster. In stationary environments expanding the structure leads to a decrease in the diameters of the clusters. The system uses a merge operator, which agglomerates two sibling clusters, in order to react to changes in the correlation structure between time series. The split and merge operators are triggered in response to changes in the diameters of existing clusters. The system is designed to process thousands of data streams that flow at high-rate. The main features of the system include update time and memory consumption that do not depend on the number of examples in the stream. Moreover, the time and memory required to process an example decreases whenever the cluster structure expands. Experimental results on artificial and real data assess the processing qualities of the system, suggesting competitive performance on clustering streaming time series, exploring also its ability to deal with concept drift.
Rui Jorge Rei, Mikio Kubo, and João Pedro Pedroso. Simulation-based optimization for steel stacking. In Le Thi Hoai An, Pascal Bouvry, and Pham Dinh Tao, editors, MCO, volume 14 of Communications in Computer and Information Science, pages 254-263. Springer, 2008. [ bib | .pdf ]
In many sectors of industry, manufacturers possess warehouses where finished goods are stored, awaiting to fulfill a client order. We present a situation where these items are characterized by release and due dates, i.e. warehouse arrival for storage and client delivery, respectively. The warehouse has a number of positions available, where items can be placed on top of each other, forming stacks. For item manipulation, there is a single a stacking crane, able to carry one item at a time. When in a given stack an item at the top is due at a date later than some item below it, it must be relocated to another stack, so that the item below can be delivered. In this problem the objective is to minimize the number of movements made by the crane.
João P. Pedroso. An evolutionary solver for mixed integer programming. Technical Report DCC-2007-09, DCC, FC, Universidade do Porto, 2007. [ bib | .pdf ]
In this paper we introduce an evolutionary algorithm for the solution of mixed integer programs. The strategy is based on the separation of the set of variables into the integer subset and the continuous subset. The main idea is that if the integer variables are fixed by the evolutionary system, the continuous ones can be determined in function of them by a linear program, which simultaneously provides an evaluation of those variables. We extend this idea to the case were some of the integer variables are fixed by the evolutionary system and the remaining ones, as well as the continuous ones, are determined in function of them. Branch-and-bound and a specialised version of the relax-and-fixed heuristic are used to solve the mixed-integer subproblems. When a particular assignment of the integer variables set by the evolutionary system leads to a feasible solution, its evaluation is determined directly by the objective function. If the variables correspond to an infeasible solution, the evaluation is measured by the number of variables that could not be fixed, due to infeasibility in the subproblem; solutions with more variables fixed are preferred. We report results obtained for some standard benchmark instances, and compare them with those obtained by time limited branch-and-bound. For a set of difficult instances, the evolutionary algorithm could almost always improve the solution obtained by branch-and-bound on the same amount of CPU time.
João Pedro Pedroso. Simple metaheuristics using the simplex algorithm for non-linear programming. In Thomas Stützle, Mauro Birattari, and Holger H. Hoos, editors, SLS, volume 4638 of Lecture Notes in Computer Science, pages 217-221. Springer, 2007. [ bib | .pdf ]
In this paper we present an extension of the Nelder and Mead simplex algorithm for non-linear programming, which makes it suitable for both unconstrained and constrained optimisation. We then explore several extensions of the method for escaping local optima, and which make it a simple, yet powerful tool for optimisation of nonlinear functions with many local optima. A strategy which proved to be extremely robust was random start local search, with a correct, though unusual, setup. Actually, for some of the benchmarks, this simple metaheuristic remained as the most effective one. The idea is to use a very large simplex at the begin; the initial movements of this simplex are very large, and therefore act as a kind of filter, which naturally drives the search into good areas. We propose two more mechanisms for escaping local optima, which, still being very simple to implement, provide better results for some difficult problems.
Pedro Rodrigues, João Gama, and João Pedro Pedroso. ODAC: Hierarchical clustering of time series data streams. In David Skillicorn Joydeep Ghosh, Diane Lambert and Jaideep Srivastava, editors, Proceedings of the Sixth SIAM International Conference on Data Mining, pages 499-503, Bethesda, Maryland, USA, April 2006. SIAM. ISBN 0-89871-611-X. [ bib | DOI | .pdf ]
This paper presents a time series whole clustering system that incrementally constructs a tree-like hierarchy of clusters, using a top-down strategy. The Online Divisive-Agglomerative Clustering (ODAC) system uses a correlation-based dissimilarity measure between time series over a data stream and possesses an agglomerative phase to enhance a dynamic behavior capable of concept drift detection. Main features include splitting and agglomerative criteria based on the diameters of existing clusters and supported by a significance level. At each new example, only the leaves are updated, reducing computation of unneeded dissimilarities and speeding up the process every time the structure grows. Experimental results on artificial and real data suggest competitive performance on clustering time series and show that the system is equivalent to a batch divi- sive clustering on stationary time series, being also capable of dealing with concept drift. With this work, we assure the possibility and importance of hierarchical incremental time series whole clustering in the data stream paradigm, presenting a valuable and usable option.
João P. Pedroso. Tabu search for mixed integer programming. In Cesar Rego, editor, Metaheuristic Optimization via Memory and Evolution: Tabu Search and Scatter Search, Operations Research/Computer Science Interfaces Series. Springer, 2005. [ bib | .pdf ]
This paper introduces tabu search for the solution of general linear integer problems. Search is done on integer variables; if there are continuous variables, their corresponding value is determined through the solution of a linear program, which is also used to evaluate the integer solution. The complete tabu search procedure includes an intensification and diversification procedure, whose effects are analysed on a set of benchmark problems.
João Pedro Pedroso and Mikio Kubo. Hybrid tabu search for lot sizing problems. In Maria J. Blesa, Christian Blum, Andrea Roli, and Michael Sampels, editors, Hybrid Metaheuristics, volume 3636 of Lecture Notes in Computer Science, pages 66-77. Springer, 2005. [ bib | .pdf ]
This paper presents a hybrid tabu search strategy for lot sizing problems. This strategy allows the exploitation of the quality of the well-known relax-and-fix heuristic, inside a tabu search framework which enforces diversity. The computational results show an advantage of this strategy when compared to a version of the relax-and-fix heuristic and to time constrained branch-and-bound.
João P. Pedroso. Metaheuristics for industrial scheduling. In Shigeru Masuyama, editor, Proceedings of the International Symposium in Scheduling, Shizuoka, Japan, September 2004. [ bib | .pdf ]
We will analyse the problem of scheduling on batch industries. A production order for an end product implies the sequential execution of a set of operations; for each operation, there is a set of machines, possibly with different characteristics, able to process it. After processing an operation, the machines have to be cleaned; the cleaning time is sequence-dependent. The most usual objective is minimising the makespan for all the orders in hand. In this work we present the fundamental notions concerning the use of metaheuristics for tackling this problem, focusing on construction strategies and neighbourhood structures for local search.
João P. Pedroso, Nelma Moreira, and Rogério Reis. A web-based system for multi-agent interactive timetabling. In ICKEDS'04: International Conference on Knowledge Engineering and Decision Support, Porto, Portugal, July 2004. [ bib | .pdf ]
We propose a web-based timetabling system for a typical situation in universities, where agents (usually departments or faculties) compete for a set of resources (lecture rooms) on a given number of time slots. Each agent (typically a person, on the behalf of a department) proposes the placement (room and time) for events. A dispatching system decides which event should be scheduled next, based on a pre-established set of rules, and asks its placement to the corresponding department. The system also suggests the placement of an event to each agent, thus allowing a completely automated timetable construction. We describe a prototype implemented at the Faculty of Sciences, University of Porto.
Rogério Reis, Nelma Moreira, and João Pedro Pedroso. Educated brute-force to get h(4). Technical Report DCC-2004-04, LIACC, Universidade do Porto, 2004. [ bib | .pdf ]
In one of his numerous conferences, Frank Harary, talked about one of his many games, that, as usual, had a very difficult problem associated to it. In this case, a family of games for two players in which the selected number of columns in the game has a vital importance. He has proved that for 2 and 3 columns the longest match has 9 and 24 moves respectively, that is to say that h_2=9 and h_3=24. At the same time it was announced that he knew a solution of length 67 for the problem with 4 columns, but he didn't know if it was the maximum. We present here a program that proves that h_4=67. Although it uses but a brute-force approach, its soundness seems good fun to prove.
João P. Pedroso. Hybrid enumeration strategies for mixed integer programming. Technical Report DCC-2004-08, LIACC, Universidade do Porto, 2004. [ bib | .pdf ]
In this paper we present several algorithms which combine a partial enumeration with metaheuristics for the solution of general mixed-integer programming problems. The enumeration is based on the primal values assignable to the integer variables of the problem. We develop some algorithms for this integration, and test them using a set of well-known benchmark problems.
João P. Pedroso. A multi-agent system for automated timetabling with shared resources. In Jianzhong Cha, Ricardo Jardim-Gonçalves, and Adolfo Steiger-Garção, editors, Proceedings of the 10th ISPE International Conference on Concurrent Engineering, volume 2 - Advanced design, management and production systems, Madeira Island - Portugal, 2003. A.A. Balkema Publishers. [ bib | .pdf ]
We propose an automated timetabling system for a typical situation in universities, where agents (usually departments or faculties) compete for a set of resources (lecture rooms) on a given number of time slots. Each agent uses its own algorithm (which might be unknown to the others). A central system decides whether some agent is granted a resource or not, based on a list of requests and on a certificate, obtained from each agent, asserting that it does not have requests with priority higher that a certain amount. Priority is measured primarily by the number of attendees and some requirements for particular features on the resources, but other criteria are proposed for ties. We describe a prototype implementation, in use at the Faculty of Sciences, University of Porto.
Ana S. Pereira, Filipe Carvalho, Miguel Constantino, and João P. Pedroso. Iterated local search and tabu search for a discrete lot sizing and scheduling problem. In Jorge P. Sousa and Mauricio G. C. Resende, editors, METAHEURISTICS: Computer Decision-Making, Combinatorial Optimization Book Series, pages 575-600. Kluwer Academic Publishers, 2003. [ bib | DOI | .pdf ]
In this paper we describe iterated local search and tabu search for solving a multi-item, multi-machine discrete lot sizing and scheduling problem with sequence dependent changeover costs. We present two construction heuristics with a random component; one of them is purely random and another is based on the linear programming relaxation of the mixed integer programming model. They are used to generate initial solutions for iterated local search and tabu search. We also propose two ways of exploring the neighbourhoods, one based on a random subset of the whole neighbourhood, and another based on exploring the whole neighbourhood. Construction and improvement methods were combined on iterated local search and tabu search, leading to a total of eight different methods. We present results of extensive computer experiments for analysing the performance of all methods and their comparison with branch-and-bound, and conclude with some remarks on the different approaches to the problem.
Teresa Neto and João P. Pedroso. Grasp for linear integer programming. In Jorge P. Sousa and Mauricio G. C. Resende, editors, METAHEURISTICS: Computer Decision-Making, Combinatorial Optimization Book Series, pages 545-574. Kluwer Academic Publishers, 2003. [ bib | DOI | .pdf ]
In this paper we introduce a GRASP for the solution of general linear integer problems. The strategy is based on the separation of the set of variables into the integer subset and the continuous subset. The integer variables are fixed by GRASP and replaced in the original linear problem. If the original problem had continuous variables, it becomes a pure continuous problem, which can be solved by a linear program solver to determine the objective value corresponding to the fixed variables. If the original problem was a pure integer problem, simple algebraic manipulations can be used to determine the objective value that corresponds to the fixed variables. When we assign values to integer variables that lead to an impossible linear problem, the evaluation of the corresponding solution is given by the sum of infeasibilities, together with an infeasibility flag. We report results obtained for some standard benchmark problems, and compare them to those obtained by branch-and-bound and to those obtained by an evolutionary solver.
João P. Pedroso. An evolutionary solver for pure integer linear programming. International Transactions in Operational Research, 9(3):337-352, May 2002. [ bib ]
In this paper we introduce an evolutionary algorithm for the solution of pure integer linear programs. All the variables of the problem are fixed by the evolutionary system. If they correspond to a feasible solution, their evaluation is determined directly by the objective function. If the variables correspond to an infeasible solution, the evaluation is measured by the sum of infeasibilities, which can be determined by simple linear algebra manipulations. The algorithm proposed does not require the solution of continuous linear programs. We report results obtained for some standard benchmark problems, and compare them with those obtained by branch-and-bound. The performance of the evolutionary algorithm is promising. Good feasible solutions were generally obtained, and in some of the difficult benchmark tests it outperformed branch-and-bound.
João P. Pedroso. Metaheuristics for combinatorial optimisation. Working Paper 9/01, Centro de Investigação Operacional da Universidade de Lisboa, Centro de Investigação Operacional, Faculdade de Ciências da Universidade de Lisboa, 1749-016 Lisboa, Portugal, 2001. [ bib | .pdf ]
The use of metaheuristics for solving combinatorial optimisation has now a long history, and there are virtually no well-known, hard optimisation problems for which a metaheuristic has not been applied. Often, metaheuristics obtain the best known solutions for hard, large-size real problems, for which exact methods are too time consuming to be applied in in practice. There are many successful applications reported in the literature; still, to the best of our knowledge there are no mathematical programming languages with an interface to solvers based on metaheuristics. Mathematical programming being the traditional, powerful way of modelling combinatorial problems, we believe that it would be an important achievement to have a solver based on metaheuristics callable from mathematical programming systems. In this paper we will focus on the different aspects to take into account when designing a metaheuristic which can be applied to any combinatorial optimisation problem modelled in mathematical programming.
Ana S. Pereira, Filipe Carvalho, João P. Pedroso, and Miguel Constantino. Iterated local search and tabu search for a discrete lot sizing and scheduling problem. In Jorge P. Sousa and Mauricio G. C. Resende, editors, Proceedings of the Fourth Metaheuristics International Conference, pages 697-701, Porto, Portugal, 2001. [ bib | .pdf ]
In this paper we describe iterated local search and tabu search for solving a multi-item, multi-machine discrete lot sizing and scheduling problem with sequence dependent changeover costs. We present two construction heuristics with a random component; one of them is purely random and another is based on the linear programming relaxation of the mixed integer programming model. They are used to generate initial solutions for iterated local search and tabu search. We also propose two ways of exploring the neighbourhoods, one based on a random subset of the whole neighbourhood, and another based on exploring the whole neighbourhood. Construction and improvement methods were combined on iterated local search and tabu search, leading to a total of eight different methods. We present results of extensive computer experiments for analysing the performance of all methods and their comparison with branch-and-bound, and conclude with some remarks on the different approaches to the problem.
Teresa Neto and João P. Pedroso. Grasp for linear integer programming. In Jorge P. Sousa and Mauricio G. C. Resende, editors, Proceedings of the Fourth Metaheuristics International Conference, pages 377-385, Porto, Portugal, 2001. [ bib | .ps ]
In this paper we introduce a GRASP for the solution of general linear integer problems. The strategy is based on the separation of the set of variables into the integer subset and the continuous subset. The integer variables are fixed by GRASP and replaced in the original linear problem. If the original problem had continuous variables, we have now a pure continuous problem, which can be solved by a linear program solver to determine the objective value corresponding to the fixed variables. If the original problem was a pure integer problem, simple algebraic manipulations can be used to determine the objective value that corresponds to the fixed variables. When we assign values to integer variables that lead to an impossible linear problem, the evaluation of the corrresponding solution is given by the sum of infeasibilities, together with an infeasibility flag. We report results obtained for some standard benchmark problems, and compare them to those obtained by branch-and-bound.
João P. Pedroso. Metaheuristics using the simplex algorithm for nonlinear programming. In Proceedings of the 2001 International Symposium on Nonlinear Theory and its Applications, pages 315-318, Miyagi, Japan, 2001. [ bib | .pdf ]
In this paper we present a metaheuristic for non-linear programming, based on the Nelder and Mead simplex algorithm. The algorithm proposed is suitable for both unconstrained and constrained optimisation. We explore several possibilities for escaping local optima.
João P. Pedroso and Noboru Murata. Support vector machines with different norms: motivation, formulations, and results. Pattern Recognition Letters, 22:1263-1272, 2001. [ bib ]
We introduce two formulations for training support vector machines, based on considering the L1 and L norms instead of the currently used L2 norm, and maximising the margin between the separating hyperplane and each data sets using L1 and L distances. We exploit the geometrical properties of these different norms, and propose what kind of results should be expected for them. Formulations in mathematical programming for linear problems corresponding to L1 and L norms are also provided, for both the separable and non separable cases. We report results obtained for some standard benchmark problems, which confirmed that the performance of all the formulations is similar. As expected, the CPU time required for machines solvable with linear programming is much shorter.
João P. Pedroso and Noboru Murata. Optimisation on support vector machines. In Shun-Ichi Amari, C. Lee Giles, Marco Gori, and Vincenzo Piuri, editors, IEEE-INNS-ENNS International Joint Conference on Neural Networks, volume VI, pages 399-404, 2000. [ bib | .pdf ]
In this paper we deal with the optimisation problem involved in determining the maximal margin separation hyperplane in support vector machines. We consider three different formulations, based on L2 norm distance (the standard case), L1 norm, and L norm. We consider separation in the original space of the data (i.e., there are no kernel transformations). For any of these cases, we focus on the following problem: having the optimal solution for a given training data set, one is given a new training example. The purpose is to use the information about the solution of the problem without the additional example in order to speed up the new optimisation problem. We also consider the case of reoptimisation after removing an example from the data set. We report results obtained for some standard benchmark problems.
João P. Pedroso and Noboru Murata. Support vector machines for linear programming: motivation and formulation. BSIS Technical Report 99-2, Riken Brain Science Institute, Wako-shi, Saitama, Japan, 1999. [ bib | .ps.gz ]
We introduce two formulations for training support vector machines, based on considering the L1 and L norms instead of the currently used L2 norm, and maximising the margin between the separating hyperplane and each data sets using L1 and L distances. We exploit the geometrical properties of these different norms, and propose what kind of results should be expected for them. Formulations in mathematical programming for linear problems corresponding to L1 and L norms are also provided, for both the separable and non separable cases. We report results obtained for some standard benchmark problems, which confirmed that the performance of all the formulations is similar. As expected, the CPU time required for machines solvable with linear programming is much shorter.
João P. Pedroso. An evolutionary solver for pure integer linear programming. Working Paper 5/99, Centro de Investigação Operacional da Universidade de Lisboa, Centro de Investigação Operacional, Faculdade de Ciências da Universidade de Lisboa, 1749-016 Lisboa, Portugal, 1999. [ bib | .ps.gz ]
In this paper we introduce an evolutionary algorithm for the solution of pure integer linear programs. All the variables of the problem are fixed by the evolutionary system. If they correspond to a feasible solution, their evaluation is determined directly by the objective function. If the variables correspond to an infeasible solution, the evaluation is measured by the sum of infeasibilities, which can be determined by simple linear algebra manipulations. The algorithm proposed does not require the solution of continuous linear programs. We report results obtained for some standard benchmark problems, and compare them with those obtained by branch-and-bound. The performance of the evolutionary algorithm is promising. Good feasible solutions were generally obtained, and in some of the difficult benchmark tests it outperformed branch-and-bound.
João P. Pedroso. An evolutionary solver for linear integer programming. BSIS Technical Report 98-7, Riken Brain Science Institute, Wako-shi, Saitama, Japan, 1998. [ bib | .pdf ]
In this paper we introduce an evolutionary algorithm for the solution of linear integer programs. The strategy is based on the separation of the set of variables into the integer subset and the continuous subset; the integer variables are fixed by the evolutionary system, and the continuous ones are determined in function of them, by a linear program solver. If they correspond to a feasible solution, their evaluation is determined directly by the objective function. If the variables correspond to an infeasible solution, the evaluation is measured by the minimal sum of constraint violations. Solutions closer to feasibility are preferred, without regard to the objective function. We report results obtained for some standard benchmark instances, and compare them with those obtained by branch-and-bound. The performance of the evolutionary algorithm is promising. Good feasible solutions were generally obtained, and in some of the difficult benchmark tests the algorithm outperformed branch-and-bound.
João P. Pedroso. Niche search: an application in vehicle routing. In IEEE International Conference on Evolutionary Computation, number 1 in 98TH8360, pages 177-182, Anchorage, Alaska, 1998. IEEE. [ bib | .pdf ]
In this paper we describe a hybrid strategy for solving combinatorial optimisation problems, obtained by coupling a local search method to an evolutionary algorithm, and we provide an application to a particular variant of the vehicle routing problem. The local search method has been devised specifically for this class of problems. It is based on a composite neighbourhood, which is searched iteratively up to the point where no further improvements can be made. The evolutionary structure is the niche search, an algorithm based on the evolution of several independent niches. Niches whose individuals' fitness is good remain, and the others tend to be replaced. The separation of the population into niches allows for a good compromise between intensive search (inside each niche) and diversification (through the separation between the niches). We also describe how we integrate specific problem knowledge into an evolutionary structure, in order to achieve a high performance optimisation algorithm. All the steps that we consider necessary are described in detail: finding an appropriate representation, determining what is a relevant neighbourhood, setting up a local search method and finally integrating the local search into an evolutionary algorithm.
João P. Pedroso. Niche search: an application to the Manhattan newspaper problem. Discussion Paper 9765, Center for Operations Research and Econometrics, Université Catholique de Louvain, Louvain-la-Neuve, Belgium, 1997. [ bib | .pdf ]
In this paper we describe a hybrid strategy for solving combinatorial optimisation problems, obtained by coupling a local search method to an evolutionary algorithm, and we provide an application to the Manhattan newspaper problem. The local search method has been devised specifically for this class of problems. It is based on a composite neighbourhood, which is searched iteratively up to the point where no further improvements can be made. The evolutionary structure is the niche search, an algorithm based on the evolution of several independent niches. Niches whose individuals' fitness is good remain, and the others tend to be replaced. The separation of the population into niches allows for a good compromise between intensive search (inside each niche) and diversification (through the separation between the niches).
João P. Pedroso. Implementation of a library for modelling in economics: design guidelines. In Proceedings of the 1997 International Symposium on Nonlinear Theory and its Applications, pages 297-300, Honolulu, 1997. Research Society of Nonlinear Theory and its Applications. [ bib | .pdf ]
In this paper we propose some design guidelines for the implementation of a library for computer aided modelling and analysis in economics. We base our approach in object-oriented programming. We also introduce a prototype implementation, where a set of algorithms and data structures appropriated for economic modelling is supplied.
João P. Pedroso. Control of search parameters in evolutionary algorithms. In Proceedings of the 1997 International Symposium on Nonlinear Theory and its Applications, pages 1265-1268, Honolulu, 1997. Research Society of Nonlinear Theory and its Applications. [ bib | .pdf ]
In this paper we present a strategy for automatically adapting the control parameters of an evolutionary algorithm. Its main features consist on its simplicity, and on providing total independence of the type of problem being solved.
João P. Pedroso. Niche Search: An Object-Oriented implementation in the C++ programming language. Technical report, CORE, UCL, 1996. [ bib ]
A (rather dated) description of the classes that intervene in Niche Search.
João Pedro Pedroso. Niche search: An evolutionary algorithm for global optimisation. In Hans-Michael Voigt, Werner Ebeling, Ingo Rechenberger, and Hans-Paul Schwefel, editors, PPSN, volume 1141 of Lecture Notes in Computer Science, pages 430-440. Springer, 1996. [ bib | .pdf ]
In this paper we describe niche search, a genetic-based optimisation approach which is characterised by an evolutionary search on two layers: the individual layer (which is comparable to search described in other genetic algorithms), and the niche layer. Neither of these searches is directed: both individuals and niches evolve based on the selection of the fittest. The numerical results obtained by niche search are quite promising, as our implementation has successfully handled all the tests carried out. The computational performance is considerably better than that of other algorithms of the same family analysed in the literature.
João P. Pedroso. Numerical solution of Nash and Stackelberg equilibria: an evolutionary approach. In Proceedings of the First Asia Conference on Simulated Evolution and Learning, pages 151-160, Taejon, Korea, 1996. First Asia Conference on Simulated Evolution and Learning (SEAL'96). [ bib | .pdf ]
In this paper we describe evolutionary heuristics for numerically solving systems of several, interdependent optimisation problems. They can be used for the solution of some games with simultaneous moves of the players (Nash equilibria), asynchronous moves (Stackelberg equilibria), or a mix of these situations. The application is possible in cases where the presence of non-convexities, integral variables, or other factors restrain the use of traditional methods, based on derivatives. The solution of instances of well known economic equilibrium problems with these algorithms is supplied. The results obtained for these simple cases show potential applications of the strategies, and provide limited convergence evidence.
This file was generated by bibtex2html 1.96.