Pavlos (Paul) Spirakis (University of Patras and Computer Tech. Institute (CTI), Greece)
Solvability of Bimatrix Games and related experiments
Joint work with Spyros Kontogiannis
Finding Nash equilibria of a bimatrix game is equivalent to solve an indefinite quadratic program. The problem of computing Nash Equilibria is complete in the class PPAD and, thus, seems hard to be solved in polynomial time. Thus, approximate and experimental methods are one of the ways to approach the problem in practice, and get insights on its computational complexity. Our experiments deal with linear relaxations of such programs and their relation to Nash and corellated equilibria. We also investigate how our methods relate to stationary points of the above mentioned quadratic programs. In addition we will report on recent progress on efficiently finding approximate Nash Equilibria for bimatrix games.
Xin-She Yang (National Physical Laboratory, UK)
Metaheuristic algorithms, Markov Chain Monte Carlo and Engineering Optimization
Many real-world optimization problems in engineering and industry are NP-hard, and thus no universally efficient algorithms exist. The choice of an optimization algorithm tends to be problem specific. Among many algorithms, metaheuristic algorithms are the most promising in solving highly nonlinear, global optimization problems. Most metaheuristic algorithms are nature-inspired, mimicking certain unique features of successful biological systems, and their main characteristics tend to be stochastic and experimenting by trial and error. This talk provides an overview of latest metaheuristic algorithms such as particle swarm optimization, firefly algorithms and cuckoo search. We also try to provide a unified view of metahueristic in terms of Markov chain Monte carlo and try to explain how algorithms work. We will also discuss a few case studies in real-world applications.
Josef Kallrath (University of Florida, USA)
Polylithic Modeling and Solution Approaches
Based on the Greek term monolithos (stone consisting of one single block) Kallrath (2009) introduced the term polylithic for modeling and solution approaches in which mixed integer or non-convex nonlinear optimization problems are solved by a tailor-made methods involving several models and/or algorithmic components. A monolithic model is just one model with data, a set of variables and constraints and one solve statement calling a LP, MILP, NLP, or MINLP solver.
In contrast, a polylithic model contains a set of models which are somehow connected in their data flow of input and output data, i.e., the solution of one model is input to another one. This can be exploited to initialize certain variables, or to provide bounds on them (problem-specific preprocessing). Mathematical examples of polylithic approaches are decomposition techniques, column generation and Branch and Price or hybrid methods in which constructive heuristics and local search improvement methods are coupled with exact MIP algorithms. Thus, we observe that the sub-models of polylithic models are often connected in such a way that they represent a tailor-made algorithm.
Tailor-made polylithic solution approaches with thousands or millions of solve statement to be executed put an extreme challenge on algebraic modeling languages. Hot-start techniques avoiding that the whole matrix is re-generated become essential. Local objects and procedural structures are almost necessary.
In this talk we discuss polylithic approaches within the context of algebraic modeling languages and present illustrative examples from the paper and metals industries, scheduling in the process industry, and planning of hydro-thermal plants in the energy industry.