18 results
Search Results
2. Revisiting Some Duality Theorems via the Quasirelative Interior in Convex Optimization.
- Author
-
Boţ, R., Csetnek, E., and Moldovan, A.
- Subjects
MATHEMATICAL optimization ,MATHEMATICAL analysis ,OPERATIONS research ,SIMULATION methods & models ,COMBINATORIAL optimization ,COMBINATORICS ,ADDITIVE combinatorics ,COMBINATORIAL designs & configurations - Abstract
In this paper, we deal with regularity conditions formulated by making use of the quasirelative interior and/or of the quasi-interior of the sets involved, guaranteeing strong duality for a convex optimization problem with cone (and equality) constraints and its Lagrange dual. We discuss also some recent results on this topic, which are proved to have either superfluous or contradictory assumptions. Several examples illustrate the theoretical considerations. [ABSTRACT FROM AUTHOR]
- Published
- 2008
- Full Text
- View/download PDF
3. Reduced Vertex Set Result for Interval Semidefinite Optimization Problems.
- Author
-
Calafiore, G. and Dabbene, F.
- Subjects
MATHEMATICAL optimization ,MATHEMATICAL analysis ,OPERATIONS research ,SIMULATION methods & models ,COMBINATORIAL optimization ,COMBINATORICS ,QUADRATIC assignment problem ,CONSTRAINED optimization ,SYSTEM analysis - Abstract
In this paper we propose a reduced vertex result for the robust solution of uncertain semidefinite optimization problems subject to interval uncertainty. If the number of decision variables is m and the size of the coefficient matrices in the linear matrix inequality constraints is n× n, a direct vertex approach would require satisfaction of 2
n( m+1)( n+1)/2 vertex constraints: a huge number, even for small values of n and m. The conditions derived here are instead based on the introduction of m slack variables and a subset of vertex coefficient matrices of cardinality 2n−1 , thus reducing the problem to a practically manageable size, at least for small n. A similar size reduction is also obtained for a class of problems with affinely dependent interval uncertainty. [ABSTRACT FROM AUTHOR]- Published
- 2008
- Full Text
- View/download PDF
4. A unifid modeling and solution framework for combinatorial optimization problems.
- Author
-
Kochenberger, Gary A., Glover, Fred, Atidaee, Bahram, and Rego, Cesar
- Subjects
MATHEMATICAL optimization ,OPERATIONS research ,CLOTHING industry ,HEURISTIC ,MATHEMATICAL analysis ,SIMULATION methods & models - Abstract
Combinatorial optimization problems are often too complex to be solved within reasonable time limits by exact methods, in spite of the theoretical guarantee that such methods will ultimately obtain an optimal solution. instead, heuristic methods, which do not offer a convergence guarantee, but which have greater flexibility to take advantage of special properties of the search space, are commonly a preferred alternative. The standard procedure is to craft a heuristic method to suit the particular characteristics of the problem at hand, exploiting to the extent possible the structure available. Such tailored methods, however, typically have limited usefulness in other problems domains. An alternative to this problem specific solution approach is a more general methodology that recasts a given problem into a common modeling format, permitting solutions to be derived by a common, rather than tailor-made, heuristic method. Because such general purpose heuristic approaches forego the opportunity to capitalize on domain-specific knowledge, they are characteristically unable to provide the effectiveness or efficiency of special purpose approaches. indeed, they are typically regarded to have little value except for dealing with small or simple problems. This paper reports on recent work that calls this commonly held view into question. We describe how a particular unified modeling framework, coupled with latest advances in heuristic search methods, makes it possible to solve problems from a wide range of important model classes. [ABSTRACT FROM AUTHOR]
- Published
- 2004
- Full Text
- View/download PDF
5. Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes.
- Author
-
Anjos, Miguel F. and Vannelli, Anthony
- Subjects
COMBINATORIAL optimization ,COMBINATORICS ,MATHEMATICAL optimization ,FUNCTIONAL equations ,MATHEMATICAL programming ,OPERATIONS research ,SIMULATION methods & models ,GENETIC algorithms ,MATHEMATICAL analysis - Abstract
This paper is concerned with the single-row facility layout problem (SRFLP). A globally optimal solution to the SRFLP is a linear placement of rectangular facilities with varying lengths that achieves the minimum total cost associated with the (known or projected) interactions between them. We demonstrate that the combination of a semidefinite programming relaxation with cutting planes is able to compute globally optimal layouts for large SRFLPs with up to 30 facilities. In particular, we report the globally optimal solutions for two sets of SRFLPs previously studied in the literature, some of which have remained unsolved since 1988. [ABSTRACT FROM AUTHOR]
- Published
- 2008
- Full Text
- View/download PDF
6. An application of reactive tabu search for service restoration in distribution systems and its comparison with the genetic algorithm and parallel simulated annealing.
- Author
-
Fudo, Hiroyuki, Toune, Sakae, Genji, Takamu, Fukuyama, Yoshikazu, and Nakanishi, Yosuke
- Subjects
MATHEMATICAL optimization ,GENETIC algorithms ,MATHEMATICAL analysis ,MAXIMA & minima ,OPERATIONS research ,COMBINATORIAL optimization ,ALGORITHMS - Abstract
Service restoration in distribution systems can be formulated as a combinatorial optimization problem. It is the problem to determine power sources for each load considering various operational constraints in distribution systems. Up to now, the problem has been dealt with using conventional methods such as the branch and bound method, expert systems, neural networks, and fuzzy reasoning. Recently, modern heuristic methods such as genetic algorithms (GA), simulated annealing (SA), and tabu search (TS) have been attracting notice as efficient methods for solving large combinatorial optimization problems. Moreover, reactive tabu search (RTS) can solve the parameter tuning problem, which is recognized as the essential problem of the TS. Therefore, RTS, GA, and SA can be efficient search methods for service restoration in distribution systems. This paper develops an RTS for service restoration and compares RTS, GA, and PSA (parallel SA) for the problem. The feasibility of the proposed methods is shown and compared on a typical distribution system model with promising results. © 2000 Scripta Technica, Electr Eng Jpn, 133(3): 71–82, 2000 [ABSTRACT FROM AUTHOR]
- Published
- 2000
- Full Text
- View/download PDF
7. Solving Fuzzy TSP with Ant Algorithms.
- Author
-
Crişan, Gloria Cerasela and Nechita, Elena
- Subjects
ANT algorithms ,ALGORITHMS ,MATHEMATICAL optimization ,FUZZY algorithms ,MATHEMATICAL analysis ,OPERATIONS research ,SIMULATION methods & models ,INDUSTRIAL efficiency - Abstract
In this paper we describe the first Ant algorithm designated for fuzzy TSP (FTSP). Our work consists of two parts. The former part is dedicated to FTSP specification. The latter transforms the Ant System (chronologically the first Ant algorithm) in order to tackle the FTSP, and implement the new algorithm on a FTSP instance. [ABSTRACT FROM AUTHOR]
- Published
- 2008
8. GENETIC ALGORITHMS MULTI-OBJECTIVES OPTIMISATION OF NONSTANDARD SPUR GEARS.
- Author
-
CHIRA, Flavia, BANICA, Mihai, and BUTNAR, Lucian
- Subjects
- *
GENETIC programming , *COMBINATORIAL optimization , *COMBINATORICS , *GENETIC algorithms , *MATHEMATICAL optimization , *EXPERIMENTAL design , *OPERATIONS research , *MATHEMATICAL analysis - Abstract
The paper present a method for optimal design of non-standard spur gears, with the aim of minimising multi-objectives optimisation functions, obtained by weighted sum of different evaluation function, represented of the significant values of some functional parameters. Those parameters can be carrying out with designing and analysing computer applications. The paper is focused on using original MATLAB application, based on genetic algorithms, developed for optimal design, with the aim of simultaneous minimising the contact stress and bending stress on the pinion and on the gear, of asymmetric gears. Having asymmetrical involutes teeth profiles, asymmetric gears are non-standard gears obtained with the "direct gear design method", used for improving the performances of the involutes toothed gears. [ABSTRACT FROM AUTHOR]
- Published
- 2009
9. A Cutting Plane Algorithm for the Linear Ordering Problem.
- Author
-
Grötschel, Martin, Jünger, Michael, and Reinelt, Gerhard
- Subjects
LINEAR orderings ,MATHEMATICAL optimization ,COMBINATORIAL optimization ,ALGORITHMS ,MAXIMA & minima ,INPUT-output analysis ,MATHEMATICAL analysis ,PROBABILITY theory ,OPERATIONS research - Abstract
The linear ordering problem is an NP-hard combinatorial optimization problem with a large number of applications (including triangulation of input-output matrices, archaeological senation, minimizing total weighted completion time in one-machine scheduling, and aggregation of individual preferences). In a former paper, we have investigated the facet structure of the 0/1-polytope associated with the linear ordering problem. Here we report on a new algorithm that is based on these theoretical results. The main part of the algorithm is a cutting plane procedure using facet defining inequalities. This procedure is combined with various heuristics and branch and bound techniques. Our computational results compare favorably with the results of existing codes. In particular, we could triangulate all input-output matrices, of size up to 60 x 60, available to us within acceptable time bounds. [ABSTRACT FROM AUTHOR]
- Published
- 1984
10. A PRIORI OPTIMIZATION.
- Author
-
Bertsimas, Dimitris J., Jaillet, Patrick, and Odoni, Amedeo R.
- Subjects
MATHEMATICAL optimization ,OPERATIONS research ,COMBINATORIAL optimization ,PROBABILITY theory ,MATHEMATICAL analysis - Abstract
Consider a complete graph G = (K, E) in which each node is present with probability p,. We are interested in solving combinatorial optimization problems on subsets of nodes which are present with a certain probability. We introduce the idea of a priori optimization as a strategy competitive to the strategy of reoptimization, under which the combinatorial optimization problem is solved optimally for every instance. We consider four problems: the traveling salesman problem (TSP), the minimum spanning tree, vehicle routing, and traveling salesman facility location. We discuss the applicability of a priori optimization strategies in several areas and show that if the nodes are randomly distributed in the plane the a priori and reoptimization strategies are very close in terms of performance. We characterize the complexity of a priori optimization and address the question of approximating the optimal a priori solutions with polynomial time heuristics with provable worst-case guarantees. Finally, we use the TSP as an example to find practical solutions based on ideas of local optimality. [ABSTRACT FROM AUTHOR]
- Published
- 1990
- Full Text
- View/download PDF
11. Approximation Schemes for Functional Optimization Problems.
- Author
-
Giulini, S. and Sanguineti, M.
- Subjects
MATHEMATICAL optimization ,COMBINATORIAL optimization ,COMBINATORICS ,MATHEMATICAL analysis ,COMBINATORIAL identities ,MATCHING theory ,OPERATIONS research ,SPECIAL functions ,HARMONIC analysis (Mathematics) ,MATHEMATICAL combinations - Abstract
Approximation schemes for functional optimization problems with admissible solutions dependent on a large number d of variables are investigated. Suboptimal solutions are considered, expressed as linear combinations of n-tuples from a basis set of simple computational units with adjustable parameters. Different choices of basis sets are compared, which allow one to obtain suboptimal solutions using a number n of basis functions that does not grow “fast” with the number d of variables in the admissible decision functions for a fixed desired accuracy. In these cases, one mitigates the “curse of dimensionality,” which often makes unfeasible traditional linear approximation techniques for functional optimization problems, when admissible solutions depend on a large number d of variables. [ABSTRACT FROM AUTHOR]
- Published
- 2009
- Full Text
- View/download PDF
12. IMPROVED ALGORITHM AND REALIZATION OF MECHANICAL MULTI-PARAMETER FUZZY OPTIMIZATION.
- Author
-
LAI, YINAN, LAI, MINGZHU, YOU, BINDI, and YU, YANGTAO
- Subjects
MATHEMATICAL optimization ,MATHEMATICAL analysis ,OPERATIONS research ,ALGORITHMS ,COMBINATORIAL optimization - Abstract
Aiming at the problem of low efficiency and local optimum caused by traditional multi-objective fuzzy optimal methods, the multi-parameter fuzzy optimal mathematical models with improved symmetry and improved asymmetry genetic algorithm based on the overall optimal view are given by considering optimal membership of objectives and constraint. The best optimal solution and optimal constraint value of sub-objective function in the feasible field are found by the mathematical model. The example for helical gear with objective and constraint sets is demonstrated. The algorithm of multi-objective fuzzy optimization is realized by applying the Matlab optimum toolbox. Matlab program to realize multi-parameter fuzzy optimal GA of the helical gear is developed, the best optimal solutions of several fuzzy optimal models is obtained, and the penalty function is used to solve the problem of nonlinear constraint. The result shows that improved fuzzy GA can get satisfying results both in the computing speed and the quality of solution. The method can reflect fuzziness of the problems and practicability of the structure of the engineering project. [ABSTRACT FROM AUTHOR]
- Published
- 2008
- Full Text
- View/download PDF
13. An Organizational Evolutionary Algorithm for Numerical Optimization.
- Author
-
Jing Liu, Weicai Zhong, and Licheng Jiao
- Subjects
NUMERICAL analysis ,ALGORITHMS ,MATHEMATICAL optimization ,MATHEMATICAL analysis ,COMBINATORIAL optimization ,SIMULATION methods & models ,OPERATIONS research ,COMBINATORICS ,ASYMPTOTIC expansions - Abstract
Taking inspiration from the interacting process among organizations in human societies, this correspondence designs a kind of structured population and corresponding evolutionary operators to form a novel algorithm, Organizational Evolutionary Algorithm (OEA), for solving both unconstrained and constrained optimization problems. In OEA, a population consists of organizations, and an organization consists of individuals. All evolutionary operators are designed to simulate the interaction among organizations. In experiments, 15 unconstrained functions, 13 constrained functions, and 4 engineering design problems are used to validate the performance of OEA, and thorough comparisons are made between the OEA and the existing approaches. The results show that the OEA obtains good performances in both the solution quality and the computational cost. Moreover, for the constrained problems, the good performances are obtained by only incorporating two simple constraints handling techniques into the OEA. Furthermore, systematic analyses have been made on all parameters of the OEA. The results show that the OEA is quite robust and easy to use. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
14. Scaling Genetic Programming to Large Datasets Using Hierarchical Dynamic Subset Selection.
- Author
-
Curry, Robert, Lichodzijewski, Peter, and Heywood, Malcolm I.
- Subjects
GENETIC programming ,GENETIC algorithms ,COMBINATORIAL optimization ,MATHEMATICAL optimization ,COMBINATORICS ,ALGORITHMS ,HEURISTIC ,MATHEMATICAL analysis ,OPERATIONS research - Abstract
The computational overhead of genetic programming (GP) may be directly addressed without recourse to hardware solutions using active learning algorithms based on the random or dynamic subset selection heuristics (RSS or DSS). This correspondence begins by presenting a family of hierarchical DSS algorithms: RSS-DSS, cascaded RSS-DSS, and the balanced block DSS algorithm, where the latter has not been previously introduced. Extensive benchmarking over four unbalanced real-world binary classification problems with 30 000-500 000 training exemplars demonstrates that both the cascade and balanced block algorithms are able to reduce the likelihood of degenerates while providing a significant improvement in classification accuracy relative to the original RSS-DSS algorithm. Moreover, comparison with GP trained without an active learning algorithm indicates that classification performance is not compromised, while training is completed in minutes as opposed to half a day. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
15. Discrete optimization: An Austrian view.
- Author
-
Burkard, Rainer E.
- Subjects
MATHEMATICAL optimization ,QUADRATIC assignment problem ,COMBINATORIAL optimization ,MATHEMATICAL analysis ,OPERATIONS research - Abstract
The author offers his views on discrete optimization. According to him, the obvious analogies between quadratic assignment problems with a sum objective and quadratic assignment problems with a bottleneck objective led to an investigation on the common mathematical background of both problems. Some of the factors that makes the optimization attractive are the links to other mathematical areas like algebra and numerical analysis, geometry and combinatorics.
- Published
- 2007
- Full Text
- View/download PDF
16. A Stochastic Minimum Cross-Entropy Method for Combinatorial Optimization and Rare-event Estimation*.
- Author
-
Rubinstein, R. Y.
- Subjects
COMBINATORICS ,MATHEMATICAL analysis ,MATHEMATICAL optimization ,OPERATIONS research ,DECISION theory ,SYSTEMS theory - Abstract
We present a new method, called the minimum cross-entropy (MCE) method for approximating the optimal solution of NP-hard combinatorial optimization problems and rare-event probability estimation, which can be viewed as an alternative to the standard cross entropy (CE) method. The MCE method presents a generic adaptive stochastic version of Kull-back’s classic MinxEnt method. We discuss its similarities and differences with the standard cross-entropy (CE) method and prove its convergence. We show numerically that MCE is a little more accurate than CE, but at the same time a little slower than CE. We also present a new method for trajectory generation for TSP and some related problems. We finally give some numerical results using MCE for rare-events probability estimation for simple static models, the maximal cut problem and the TSP, and point out some new areas of possible applications. [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF
17. Synthesis of 2-Commodity Flow Networks.
- Author
-
Hassin, Refael and Levin, Asaf
- Subjects
COMBINATORIAL optimization ,MATHEMATICAL optimization ,COMBINATORICS ,OPERATIONS research ,MATHEMATICAL analysis - Abstract
We investigate network design under volatile conditions of link failures and trafic overload. Our model is a nonsimultaneous 2-commodity problem. We characterize the feasible solutions and, using this characterization, we reduce the size of the linear program. For 0/1 requirements we present a closed fractional optimal solution, a closed integer-capacities optimal solution, and 7/6-approximation for the case in which integer 2-commodity flows are required. [ABSTRACT FROM AUTHOR]
- Published
- 2004
- Full Text
- View/download PDF
18. Approximability of hard combinatorial optimization problems: an introduction.
- Author
-
Maffioli, Francesco and Galbiati, Giulia
- Subjects
COMBINATORICS ,MATHEMATICAL analysis ,COMBINATORIAL optimization ,MATHEMATICAL optimization ,OPERATIONS research ,RESEARCH - Abstract
Focuses on the approximability of hard combinatorial optimization problems. Description of developments in the theoretical characterization of approximation classes; Emphasis on Non-deterministic Polynomial Optimization problems; Suggestion that the study of approximability properties for optimization problems whose recognition version is NP-complete implies more subtle difficulties than that of NP-completeness.
- Published
- 2000
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.