Catalogue Search | MBRL
Are you sure you want to remove the book from the shelf?
{{itemTitle}}
9,403
result(s) for
"combinatorial optimization"
Sort by:
Weakly Modular Graphs and Nonpositive Curvature
This article investigates structural, geometrical, and topological characterizations and properties of weakly modular graphs and of
cell complexes derived from them. The unifying themes of our investigation are various “nonpositive curvature\" and “local-to-global”
properties and characterizations of weakly modular graphs and their subclasses. Weakly modular graphs have been introduced as a
far-reaching common generalization of median graphs (and more generally, of modular and orientable modular graphs), Helly graphs,
bridged graphs, and dual polar graphs occurring under different disguises (
We give a local-to-global characterization of weakly modular graphs and their subclasses in terms of simple
connectedness of associated triangle-square complexes and specific local combinatorial conditions. In particular, we revisit
characterizations of dual polar graphs by Cameron and by Brouwer-Cohen. We also show that (disk-)Helly graphs are precisely the
clique-Helly graphs with simply connected clique complexes. With
eBook
Solving the deterministic and stochastic uncapacitated facility location problem: from a heuristic to a simheuristic
The uncapacitated facility location problem (UFLP) is a popular combinatorial optimization problem with practical applications in different areas, from logistics to telecommunication networks. While most of the existing work in the literature focuses on minimizing total cost for the deterministic version of the problem, some degree of uncertainty (e.g., in the customers' demands or in the service costs) should be expected in real-life applications. Accordingly, this paper proposes a simheuristic algorithm for solving the stochastic UFLP (SUFLP), where optimization goals other than the minimum expected cost can be considered. The development of this simheuristic is structured in three stages: (i) first, an extremely fast savings-based heuristic is introduced; (ii) next, the heuristic is integrated into a metaheuristic framework, and the resulting algorithm is tested against the optimal values for the UFLP; and (iii) finally, the algorithm is extended by integrating it with simulation techniques, and the resulting simheuristic is employed to solve the SUFLP. Some numerical experiments contribute to illustrate the potential uses of each of these solving methods, depending on the version of the problem (deterministic or stochastic) as well as on whether or not a real-time solution is required.
Journal Article
Integer and Combinatorial Optimization
Rave reviews for INTEGER AND COMBINATORIAL OPTIMIZATION \"This book provides an excellent introduction and survey of traditional fields of combinatorial optimization... It is indeed one of the best and most complete texts on combinatorial optimization... available. [And] with more than 700 entries, [it] has quite an exhaustive reference list.\"-Optima \"A unifying approach to optimization problems is to formulate them like linear programming problems, while restricting some or all of the variables to the integers. This book is an encyclopedic resource for such formulations, as well as for understanding the structure of and solving the resulting integer programming problems.\"-Computing Reviews \"[This book] can serve as a basis for various graduate courses on discrete optimization as well as a reference book for researchers and practitioners.\"-Mathematical Reviews \"This comprehensive and wide-ranging book will undoubtedly become a standard reference book for all those in the field of combinatorial optimization.\"-Bulletin of the London Mathematical Society \"This text should be required reading for anybody who intends to do research in this area or even just to keep abreast of developments.\"-Times Higher Education Supplement, London Also of interest... INTEGER PROGRAMMING Laurence A. Wolsey Comprehensive and self-contained, this intermediate-level guide to integer programming provides readers with clear, up-to-date explanations on why some problems are difficult to solve, how techniques can be reformulated to give better results, and how mixed integer programming systems can be used more effectively. 1998 (0-471-28366-5) 260 pp.
eBook
Solving Generalized Polyomino Puzzles Using the Ising Model
In the polyomino puzzle, the aim is to fill a finite space using several polyomino pieces with no overlaps or blanks. Because it is an NP-complete combinatorial optimization problem, various probabilistic and approximated approaches have been applied to find solutions. Several previous studies embedded the polyomino puzzle in a QUBO problem, where the original objective function and constraints are transformed into the Hamiltonian function of the simulated Ising model. A solution to the puzzle is obtained by searching for a ground state of Hamiltonian by simulating the dynamics of the multiple-spin system. However, previous methods could solve only tiny polyomino puzzles considering a few combinations because their Hamiltonian designs were not efficient. We propose an improved Hamiltonian design that introduces new constraints and guiding terms to weakly encourage favorable spins and pairs in the early stages of computation. The proposed model solves the pentomino puzzle represented by approximately 2000 spins with >90% probability. Additionally, we extended the method to a generalized problem where each polyomino piece could be used zero or more times and solved it with approximately 100% probability. The proposed method also appeared to be effective for the 3D polycube puzzle, which is similar to applications in fragment-based drug discovery.
Journal Article
Computational Principle and Performance Evaluation of Coherent Ising Machine Based on Degenerate Optical Parametric Oscillator Network
We present the operational principle of a coherent Ising machine (CIM) based on a degenerate optical parametric oscillator (DOPO) network. A quantum theory of CIM is formulated, and the computational ability of CIM is evaluated by numerical simulation based on c-number stochastic differential equations. We also discuss the advanced CIM with quantum measurement-feedback control and various problems which can be solved by CIM.
Journal Article
Extended formulations in combinatorial optimization
This survey is concerned with the size of perfect formulations for combinatorial optimization problems. By “perfect formulation”, we mean a system of linear inequalities that describes the convex hull of feasible solutions, viewed as vectors. Natural perfect formulations often have a number of inequalities that is exponential in the size of the data needed to describe the problem. Here we are particularly interested in situations where the addition of a polynomial number of extra variables allows a formulation with a polynomial number of inequalities. Such formulations are called “compact extended formulations”. We survey various tools for deriving and studying extended formulations, such as Fourier’s procedure for projection, Minkowski-Weyl’s theorem, Balas’ theorem for the union of polyhedra, Yannakakis’ theorem on the size of an extended formulation, dynamic programming, and variable discretization. For each tool that we introduce, we present one or several examples of how this tool is applied. In particular, we present compact extended formulations for several graph problems involving cuts, trees, cycles and matchings, and for the mixing set, and we present the proof of Fiorini, Massar, Pokutta, Tiwary and de Wolf of an exponential lower bound for the cut polytope. We also present Bienstock’s approximate compact extended formulation for the knapsack problem, Goemans’ result on the size of an extended formulation for the permutahedron, and the Faenza-Kaibel extended formulation for orbitopes.
Journal Article
Boltzmann Sampling by Degenerate Optical Parametric Oscillator Network for Structure-Based Virtual Screening
A structure-based lead optimization procedure is an essential step to finding appropriate ligand molecules binding to a target protein structure in order to identify drug candidates. This procedure takes a known structure of a protein-ligand complex as input, and structurally similar compounds with the query ligand are designed in consideration with all possible combinations of atomic species. This task is, however, computationally hard since such combinatorial optimization problems belong to the non-deterministic nonpolynomial-time hard (NP-hard) class. In this paper, we propose the structure-based lead generation and optimization procedures by a degenerate optical parametric oscillator (DOPO) network. Results of numerical simulation demonstrate that the DOPO network efficiently identifies a set of appropriate ligand molecules according to the Boltzmann sampling law.
Journal Article
A skewed general variable neighborhood search algorithm with fixed threshold for the heterogeneous fleet vehicle routing problem
This article considers the heterogeneous fleet vehicle routing problem, as a variant of a well-known transportation problem: the vehicle routing problem. In order to solve this particular routing problem, a variable neighborhood search with a threshold accepting mechanism is developed and implemented. The performance of the algorithm was compared to other algorithms and tested on datasets from the available literature. Computational results show that our proposed algorithm is competitive and generates new best solutions.
Journal Article
Improved approximations for two-stage min-cut and shortest path problems under uncertainty
In this paper, we study the robust and stochastic versions of the two-stage min-cut and shortest path problems introduced in Dhamdhere et al. (in How to pay, come what may: approximation algorithms for demand-robust covering problems. In: FOCS, pp 367–378,
2005
), and give approximation algorithms with improved approximation factors. Specifically, we give a 2-approximation for the robust min-cut problem and a 4-approximation for the stochastic version. For the two-stage shortest path problem, we give a
3.39
-approximation for the robust version and
6.78
-approximation for the stochastic version. Our results significantly improve the previous best approximation factors for the problems. In particular, we provide the first constant-factor approximation for the stochastic min-cut problem. Our algorithms are based on a guess and prune strategy that crucially exploits the nature of the robust and stochastic objective. In particular, we guess the worst-case second stage cost and based on the guess, select a subset of
costly
scenarios for the first-stage solution to address. The second-stage solution for any scenario is simply the min-cut (or shortest path) problem in the residual graph. The key contribution is to show that there is a near-optimal first-stage solution that completely satisfies the subset of costly scenarios that are selected by our procedure. While the guess and prune strategy is not directly applicable for the stochastic versions, we show that using a novel LP formulation, we can adapt a guess and prune algorithm for the stochastic versions. Our algorithms based on the guess and prune strategy provide insights about the applicability of this approach for more general robust and stochastic versions of combinatorial problems.
Journal Article