626 research outputs found
Computational Management Science, special issue
No full textNumero speciale della rivista Computational Management Science. Guest Editors A. Migdalas, P.M. Pardalos, Gerardo Torald
Spatial interaction models: facility location using game theory
No full textThis book aims to provide a comprehensive overview of facility location models that can be investigated in a game theoretical environment. Facility location theory develops the idea of locating one or more facilites optimizing suitable criteria such as minimizing transportation cost, capturing the largest market share, etc.. and a huge number of papers have been devoted to this reaserch.
In this volume we focus on situations where the location decision is faced by several decision makers, leading to a game theoretical framework in a noncooperative way, as well as in a cooperative one. Some chapters are surveys of models and methods regarding this part of the facility location using game theory, other chapters illustrate applications in dierent contexts such as economics, engineering, physics, etc. This makes the book useful for a broader audience of researchers working on theory, applications and computational aspects.
We would like to express our thanks to all the contributors of chapters and also the evaluable assistance of the Springer sta for the publication of this book
Efficient solutions for the Far From Most String Problem
No full textComputational molecular biology has emerged as one of the most exciting interdisciplinary
fields. It has currently benefited from concepts and theoretical results obtained
by different scientific research communities, including genetics, biochemistry, and
computer science. In the past few years it has been shown that a large number of molecular
biology problems can be formulated as combinatorial optimization problems, including
sequence alignment problems, genome rearrangement problems, string selection and comparison
problems, and protein structure prediction and recognition. This paper provides a
detailed description of string selection and string comparison problems. For finding goodquality
solutions of a particular class of string comparison molecular biology problems,
known as the far from most string problem, we propose new heuristics, including a Greedy
Randomized Adaptive Search Procedure (GRASP) and a Genetic Algorithm (GA). Computational
results indicate that these randomized heuristics find better quality solutions compared
with results produced by the best state-of-the-art heuristic approach
Feedback set problems
No full textIn recent years feedback set problems have been the subject of growing interest. They have found applications in many fields, including deadlock prevention, program verification, and Bayesian inference. Therefore, it is natural that in the past few years there have been intensive efforts on exact and approximation algorithms for these kinds of problems. It generalizes a number of problems, including the minimum feedback vertex (arc) set problem in both directed and undirected graphs, the subset minimum feedback vertex (arc) set problem and the graph bipartization problem, in which one must remove a minimum-weight set of vertices so that the remaining graph is bipartite. The scope of this article is to give a complete state-of-art survey of exact and approximation algorithms and to analyze a new practical heuristic method called GRASP for solving both feedback vertex and feedback arc set problems
On Very Large Maximum Clique Problems (Extended Abstract)
No full text) J. Abello Network Services Research, AT&T Labs Research, 180 Park Avenue Florham Park, NJ 07932-0971, USA e-mail: [email protected] P. M. Pardalos Center for Applied Optimization, University of Florida, 303 Weil Hall Gainesville, FL 32611, USA e-mail: [email protected] and M. G. C. Resende Information Sciences Research, AT&T Labs Research, 180 Park Avenue Florham Park, NJ 07932-0971, USA e-mail: [email protected] Abstract We present an approach to clique computations in very large multi-digraphs. We discuss graph decomposition schemes used to break up the problem into several pieces of manageable dimensions. A two-stage (out-of-memory and in-memory) greedy randomized adaptive search procedure (GRASP) for finding approximate solutions to the maximum clique problem in very large sparse graphs is presented. We experiment with this heuristic on real data sets collected in the telecomunications industry. These graphs contain on the order of millions of vertices and edges. Ke..
On the chromatic number of graphs
No full textComputing the chromatic number of a graph is an NP-hard problem. For random graphs and some other classes of graphs, estimators of the expected chromatic number have been well studied. In this paper, a new 0–1 integer programming formulation for the graph coloring problem is presented. The proposed new formulation is used to develop a method that generates graphs of known chromatic number by using the KKT optimality conditions of a related continuous nonlinear program
On the chromatic number of graphs
No full textComputing the chromatic number of a graph is an NP-hard problem. For random graphs and some other classes of graphs, estimators of the expected chromatic number have been well studied. In this paper, a new 0–1 integer programming formulation for the graph coloring problem is presented. The proposed new formulation is used to develop a method that generates graphs of known chromatic number by using the KKT optimality conditions of a related continuous nonlinear program
Neural network embeddings on corporate annual filings for portfolio selection
No full textIn recent years, there has been an increased interest from both academics and practitioners in automatically analyzing the textual part of companies’ financial reports to extract meaning rich in information for future outcomes. In particular, tracking textual changes among companies’ reports can have a large and significant impact on stock prices. This impact happens with a lag implying that investors only gradually realize the implications of the news hinted by document changes. However, the length of these documents as well as their complexity in terms of structure and language have been increasing dramatically making this process more and more difficult to perform. In this paper, we analyzed how to face this complexity by learning arbitrary dimensional vector representations for US corporate filings (10-Ks) from 1998 to 2018, exploiting and comparing different neural network embedding techniques which take into account words’ semantics through vectors proximity. We also compared their ability to capture changes associated with future risk-adjusted abnormal returns with other more commonly used approaches in literature. Finally, we propose a novel investment strategy named Semantic Similarity Portfolio (SSP) that exploits these neural network embeddings. We show that firms that do not change their 10-Ks in a semantically important way from the previous year tend to have large and statistically significant future risk-adjusted abnormal returns. We, also document an amplifying effect when we incorporate a momentum-related criterion, where the companies selected must also have had positive previous year returns. Specifically, a portfolio that buys “non-changers” based on this strategy earns up to 10% in yearly risk-adjusted abnormal returns (alpha)
CliSAT: A new exact algorithm for hard maximum clique problems
No full textGiven a graph, the maximum clique problem (MCP) asks for determining a complete subgraph with the
largest possible number of vertices. We propose a new exact algorithm, called CliSAT , to solve the
MCP to proven optimality. This problem is of fundamental importance in graph theory and combinatorial
optimization due to its practical relevance for a wide range of applications. The newly developed exact approach is a combinatorial branch-and-bound algorithm that exploits the state-of-the-art branching
scheme enhanced by two new bounding techniques with the goal of reducing the branching tree. The
first one is based on graph colouring procedures and partial maximum satisfiability problems arising in
the branching scheme. The second one is a filtering phase based on constraint programming and domain
propagation techniques. CliSAT is designed for structured MCP instances which are computationally
difficult to solve since they are dense and contain many interconnected large cliques. Extensive experiments on hard benchmark instances, as well as new hard instances arising from different applications,
show that CliSAT outperforms the state-of-the-art MCP algorithms, in some cases by several orders of
magnitude
GRASP with path relinking for the three-index assignement problem
No full textThis paper proposes and tests variants of GRASP (greedy randomized adaptive search procedure) with path relinking for the three-index assignment problem (AP3). GRASP is a multistart metaheuristic for combinatorial optimization. It usually consists of a construction procedure based on a greedy randomized algorithm and of a local search. Path relinking is an intensification strategy that explores trajectories that connect high-quality solutions. Several variants of the heuristic are proposed and tested. Computational results show clearly that this GRASP for AP3 benefits from path relinking and that the variants considered in this paper compare well with previously proposed heuristics for this problem. GRASP with path relinking was able to improve the solution quality of heuristics proposed by Balas and Saltzman (1991), Burkard et al. (1996), and Crama and Spieksma (1992) on all instances proposed in those papers. We show that the random variable “time to target solution,� for all proposed GRASP with path-relinking variants, fits a two-parameter exponential distribution. To illustrate the consequence of this, one of the variants of GRASP with path relinking is shown to benefit from parallelization
- …
