共查询到20条相似文献,搜索用时 15 毫秒
1.
Variable neighbourhood search for redundancy allocation problems 总被引:1,自引:0,他引:1
** Email: ycliang{at}saturn.yzu.edu.tw*** Email: s929512{at}mail.yzu.edu.tw**** Email: s927522{at}mail.yzu.edu.tw A variable neighbourhood search (VNS) algorithm has been developedto solve the redundancy allocation problem (RAP). The VNS methodis perfectly suited to those combinatorial problems with potentialneighbourhood structures, as in the case of the RAP. The moststudied configuration of the RAP is a series system of s-independentk-out-of-n:G subsystems the so-called seriesparallelsystem. The RAP is to select the optimal combination and redundancylevels of components to meet system-level constraints. Two typesof objectives are considered in this studysystem reliabilitymaximization and system cost minimization. The VNS algorithmis tested on sets of benchmark problems and compared to thebest heuristics in the literature such as tabu search, multipleweighted objective heuristic, ant colony optimization and geneticalgorithm. Computational results show the advantages and benefitsof VNS for solving both types of RAP while considering bothsolution quality and computational efficiency. 相似文献
2.
Mostafa Khorramizadeh Nezam Mahdavi-Amiri 《4OR: A Quarterly Journal of Operations Research》2011,9(2):159-173
Recently, we described a generalization of Rosser’s algorithm for a single linear Diophantine equation to an algorithm for
solving systems of linear Diophantine equations. Here, we make use of the new formulation to present a new algorithm for solving
rank one perturbed linear Diophantine systems, based on using Rosser’s approach. Finally, we compare the efficiency and effectiveness
of our proposed algorithm with the algorithm proposed by Amini and Mahdavi-Amiri (Optim Methods Softw 21:819–831, 2006). 相似文献
3.
Alicia Cordero José L. Hueso Eulalia Martínez Juan R. Torregrosa 《Numerical Algorithms》2010,53(4):485-495
In this paper, we present two new three-step iterative methods for solving nonlinear equations with sixth convergence order.
The new methods are obtained by composing known methods of third order of convergence with Newton’s method and using an adequate
approximation for the derivative, that provides high order of convergence and reduces the required number of functional evaluations
per step. The first method is obtained from Potra-Pták’s method and the second one, from Homeier’s method, both reaching an
efficiency index of 1.5651. Our methods are comparable with the method of Parhi and Gupta (Appl Math Comput 203:50–55, 2008). Methods proposed by Kou and Li (Appl Math Comput 189:1816–1821, 2007), Wang et al. (Appl Math Comput 204:14–19, 2008) and Chun (Appl Math Comput 190:1432–1437, 2007) reach the same efficiency index, although they start from a fourth order method while we use third order methods and simpler
arithmetics. We prove the convergence results and check them with several numerical tests that allow us to compare the convergence
order, the computational cost and the efficiency order of our methods with those of the original methods. 相似文献
4.
In this paper, optimal derivative design when multiple firms compete for heterogenous customers is studied. Ties in the agents’
best responses generate discontinuous payoffs. Efficient tie-breaking rules are considered: In a first step, the model presented
by Carlier et al. (Math Financ Econ 1:57–80, 2007) is extended, and results of Page and Monteiro (J Math Econ 39:63–109, 2003, J Econ Theory 134:566–575, 2007, Econ Theory 34:503–524, 2008) are used to prove the existence of (mixed-strategies) Nash equilibria. In a second step, the case of risk minimizing firms
is studied. Socially efficient allocations are introduced, and their existence is proved. In particular, the entropic risk
measure is considered. 相似文献
5.
In multi-objective convex optimization it is necessary to compute an infinite set of nondominated points. We propose a method
for approximating the nondominated set of a multi-objective nonlinear programming problem, where the objective functions and
the feasible set are convex. This method is an extension of Benson’s outer approximation algorithm for multi-objective linear
programming problems. We prove that this method provides a set of weakly ε-nondominated points. For the case that the objectives and constraints are differentiable, we describe an efficient way to
carry out the main step of the algorithm, the construction of a hyperplane separating an exterior point from the feasible
set in objective space. We provide examples that show that this cannot always be done in the same way in the case of non-differentiable
objectives or constraints. 相似文献
6.
This paper gives a quantum algorithm for global optimization. The heart of such approaches employ Grover’s database search
(1996; Phys Rev Lett 79(23):4709–4712, 1997a; 79(2):325–328, 1997b). Chi and Kim (1998) show that when the phases of the generalized Grover database search operator are optimally chosen, it is capable of finding
a solution by a single query. To apply this method to global optimization requires knowledge of the number of marked points
m to calculate the optimal phases, but this value is seldom known. This paper focuses on overcoming this hurdle by showing
that an estimate of the optimal phases can be found and used to replace the optimal phases while maintaining a high probability
of finding a solution. Merging this finding with a recently discovered dynamic quantum global optimization algorithm (BBW2D)
that reduces the problem to finding successively improving regions using Grover’s search, we present a hybrid method that
improves the efficiency and reduces the variance of the search algorithm when empirically compared to other existing quantum
search algorithms. 相似文献
7.
Eric C. K. Cheung David Landriault 《Methodology and Computing in Applied Probability》2012,14(2):233-251
In this paper, the compound Poisson risk model with surplus-dependent premium rate is analyzed in the taxation system proposed
by Albrecher and Hipp (Bl?tter der DGVFM 28(1):13–28, 2007). In the compound Poisson risk model, Albrecher and Hipp (Bl?tter der DGVFM 28(1):13–28, 2007) showed that a simple relationship between the ruin probabilities in the risk model with and without tax exists. This so-called
tax identity was later generalized to a surplus-dependent tax rate by Albrecher et al. (Insur Math Econ 44(2):304–306, 2009). The present paper further generalizes these results to the Gerber–Shiu function with a generalized penalty function involving
the maximum surplus prior to ruin. We show that this generalized Gerber–Shiu function in the risk model with tax is closely
related to the ‘original’ Gerber–Shiu function in the risk model without tax defined in a dividend barrier framework. The
moments of the discounted tax payments before ruin and the optimal threshold level for the tax authority to start collecting
tax payments are also examined. 相似文献
8.
New approach for the nonlinear programming with transient stability constraints arising from power systems 总被引:1,自引:0,他引:1
Xiaojiao Tong Soon-Yi Wu Renjun Zhou 《Computational Optimization and Applications》2010,45(3):495-520
This paper presents a new approach for solving a class of complicated nonlinear programming problems arises from optimal power
flow with transient stability constraints (denoted by OTS) in power systems. By using a functional transformation technology
proposed in Chen et al. (IEEE Trans. Circuits Syst. I Fundam. Theory Appl. 48:327–339, [2001]), the OTS problem is transformed to a semi-infinite programming (SIP). Then based on the KKT (Karush-Kuhn-Tucker) system
of the reformulated SIP problem and the finite approximation technology, an iterative method is presented, which develops
Wu-Li-Qi-Zhou’ (Optim. Methods Softw. 20:629–643, [2005]) method. In order to save the computing cost, some typical computing technologies, such as active set strategy, quasi-Newton
method for the subproblems coming from the finite approximation model, are addressed. The global convergence of the proposed
algorithm is established. Numerical examples from power systems are tested. The computing results show the efficiency of the
new approach. 相似文献
9.
Multi-objective genetic algorithm for single machine scheduling problem under fuzziness 总被引:1,自引:0,他引:1
This paper presents a new multi-objective approach to a single machine scheduling problem in the presence of uncertainty.
The uncertain parameters under consideration are due dates of jobs. They are modelled by fuzzy sets where membership degrees
represent decision maker’s satisfaction grade with respect to the jobs’ completion times. The two objectives defined are to
minimise the maximum and the average tardiness of the jobs. Due to fuzziness in the due dates, the two objectives become fuzzy
too. In order to find a job schedule that maximises the aggregated satisfaction grade of the objectives, a hybrid algorithm
that combines a multi-objective genetic algorithm with local search is developed. The algorithm is applied to solve a real-life
problem of a manufacturing pottery company. 相似文献
10.
Extreme meteorological events have increased over the last decades and it is widely accepted that it is due to climate change
(IPCC, Climate Change 2007, Fourth Assessment Report of the Intergovernmental Panel on Climate Change, Cambridge University
Press, Cambridge, 2007; Beniston et al., Clim. Change 81:71–95, 2007). Some of these extremes, like drought or frost episodes, largely affect agricultural outputs, and risk management becomes
crucial. The goal of this paper it is to analyze farmers’ decisions about risk management, taking into account climatological
and meteorological information. We consider a situation in which the farmer, as part of crop management, has available technology
to protect the harvest from weather effects. This approach has been used by Murphy et al. (Mon. Weather Rev. 113:801–813,
1985), Katz and Murphy (J. Forecast. 9:75–86, 1990 and Economic Value of Weather and Climate Forecasts, pp. 183–217, Cambridge University Press, Cambridge, 1997) and others in the case when the farmer maximizes the expected returns. In our model, we introduce the attitude towards risk.
Thus we can evaluate how the optimal decision is affected by the absolute risk aversion coefficient of Arrow and Pratt, and
compute the economic value of the information in this context, while proposing a measure to estimate the amount of money that
the farmer is willing to pay for this information in terms of the certainty equivalent. 相似文献
11.
The quickest path problem is related to the classical shortest path problem, but its objective function concerns the transmission
time of a given amount of data throughout a path, which involves both cost and capacity. The K-quickest simple paths problem generalises the latter, by looking for a given number K of simple paths in non-decreasing order of transmission time.
Two categories of algorithms are known for ranking simple paths according to the transmission time. One is the adaptation
of deviation algorithms for ranking shortest simple paths (Pascoal et al. in Comput. Oper. Res. 32(3):509–520, 2005; Rosen et al. in Comput. Oper. Res. 18(6):571–584, 1991), and another is based on ranking shortest simple paths in a sequence of networks with fixed capacity lower bounds (Chen
in Inf. Process. Lett. 50:89–92, 1994), and afterwards selecting the K quickest ones.
After reviewing the quickest path and the K-quickest simple paths problems we describe a recent algorithm for ranking quickest simple paths (Pascoal et al. in Ann. Oper.
Res. 147(1):5–21, 2006). This is a lazy version of Chen’s algorithm, able to interchange the calculation of new simple paths and the output of each
k-quickest simple path.
Finally, the described algorithm is computationally compared to its former version, as well as to deviation algorithms.
相似文献
12.
John W. Pratt 《Annals of Operations Research》2010,176(1):379-387
Conditions one might impose on fair allocation procedures are introduced. Nondiscrimination requires that agents share an item in proportion to their entitlements if they receive nothing else. The “price” procedures
of Pratt (J. Risk Uncertain. 35:203–236, 2007), including the Nash bargaining procedure, satisfy this. Other prominent efficient procedures do not. 相似文献
13.
Ankur A. Kulkarni Uday V. Shanbhag 《Journal of Optimization Theory and Applications》2012,154(1):175-186
Generalized Nash games with shared constraints represent an extension of Nash games in which strategy sets are coupled across players through a shared or common constraint. The equilibrium conditions of such a game can be compactly stated as a quasi-variational inequality (QVI), an extension of the variational inequality (VI). In (Eur. J. Oper. Res. 54(1):81–94, 1991), Harker proved that for any QVI, under certain conditions, a solution to an appropriately defined VI solves the QVI. This is a particularly important result, given that VIs are generally far more tractable than QVIs. However Facchinei et al. (Oper. Res. Lett. 35(2):159–164, 2007) suggested that the hypotheses of this result are difficult to satisfy in practice for QVIs arising from generalized Nash games with shared constraints. We investigate the applicability of Harker’s result for these games with the aim of formally establishing its reach. Specifically, we show that if Harker’s result is applied in a natural manner, its hypotheses are impossible to satisfy in most settings, thereby supporting the observations of Facchinei et al. But we also show that an indirect application of the result extends the realm of applicability of Harker’s result to all shared-constraint games. In particular, this avenue allows us to recover as a special case of Harker’s result, a result provided by Facchinei et al. (Oper. Res. Lett. 35(2):159–164, 2007), in which it is shown that a suitably defined VI provides a solution to the QVI of a shared-constraint game. 相似文献
14.
A new iterative algorithm for solving initial data inverse problems from partial observations has been recently proposed in
Ramdani et al. (Automatica 46(10), 1616–1625, 2010). Based on the concept of observers (also called Luenberger observers), this algorithm covers a large class of abstract evolution
PDE’s. In this paper, we are concerned with the convergence analysis of this algorithm. More precisely, we provide a complete
numerical analysis for semi-discrete (in space) and fully discrete approximations derived using finite elements in space and
an implicit Euler method in time. The analysis is carried out for abstract Schr?dinger and wave conservative systems with
bounded observation (locally distributed). 相似文献
15.
In this paper, we investigate the strong convergence of an inexact proximal-point algorithm. It is known that the proximal-point
algorithm converges weakly to a solution of a maximal monotone operator, but fails to converge strongly. Solodov and Svaiter
(Math. Program. 87:189–202, 2000) introduced a new proximal-type algorithm to generate a strongly convergent sequence and established a convergence result
in Hilbert space. Subsequently, Kamimura and Takahashi (SIAM J. Optim. 13:938–945, 2003) extended the Solodov and Svaiter result to the setting of uniformly convex and uniformly smooth Banach space. On the other
hand, Rockafellar (SIAM J. Control Optim. 14:877–898, 1976) gave an inexact proximal-point algorithm which is more practical than the exact one. Our purpose is to extend the Kamimura
and Takahashi result to a new inexact proximal-type algorithm. Moreover, this result is applied to the problem of finding
the minimizer of a convex function on a uniformly convex and uniformly smooth Banach space.
L.C. Zeng’s research was partially supported by the Teaching and Research Award Fund for Outstanding Young Teachers in Higher
Education Institutions of MOE, China and by the Dawn Program Foundation in Shanghai.
J.C. Yao’s research was partially supported by the National Science Council of the Republic of China. 相似文献
16.
In this article we investigate a new variant of Variable Neighborhood Search (VNS): Relaxation Guided Variable Neighborhood
Search. It is based on the general VNS scheme and a new Variable Neighborhood Descent (VND) algorithm. The ordering of the
neighborhood structures in this VND is determined dynamically by solving relaxations of them. The objective values of these
relaxations are used as indicators for the potential gains of searching the corresponding neighborhoods. We tested this new
approach on the well-studied multidimensional knapsack problem. Computational experiments show that our approach is beneficial
to the search, improving the obtained results. The concept is, in principle, more generally applicable and seems to be promising
for many other combinatorial optimization problems approached by VNS.
NICTA is funded by the Australian Government’s Backing Australia’s Ability initiative, in part through the Australian Research
Council.The Institute of Computer Graphics and Algorithms is supported by the European RTN ADONET under grant 504438. 相似文献
17.
Changhe Liu Hongwei Liu Xinze Liu 《Journal of Optimization Theory and Applications》2012,154(3):949-965
This paper presents an extension of the variant of Mehrotra’s predictor–corrector algorithm which was proposed by Salahi and Mahdavi-Amiri (Appl. Math. Comput. 183:646–658, 2006) for linear programming to symmetric cones. This algorithm incorporates a safeguard in Mehrotra’s original predictor–corrector algorithm, which keeps the iterates in the prescribed neighborhood and allows us to get a reasonably large step size. In our algorithm, the safeguard strategy is not necessarily used when the affine scaling step behaves poorly, which is different from the algorithm of Salahi and Mahdavi-Amiri. We slightly modify the maximum step size in the affine scaling step and extend the algorithm to symmetric cones using the machinery of Euclidean Jordan algebras. Based on the Nesterov–Todd direction, we show that the iteration-complexity bound of the proposed algorithm is , where r is the rank of the associated Euclidean Jordan algebras and ε>0 is the required precision. 相似文献
18.
In this paper, a new methodology is presented to solve different versions of multi-objective system redundancy allocation
problems with prioritized objectives. Multi-objective problems are often solved by modifying them into equivalent single objective
problems using pre-defined weights or utility functions. Then, a multi-objective problem is solved similar to a single objective
problem returning a single solution. These methods can be problematic because assigning appropriate numerical values (i.e.,
weights) to an objective function can be challenging for many practitioners. On the other hand, methods such as genetic algorithms
and tabu search often yield numerous non-dominated Pareto optimal solutions, which makes the selection of one single best
solution very difficult. In this research, a tabu search meta-heuristic approach is used to initially find the entire Pareto-optimal
front, and then, Monte-Carlo simulation provides a decision maker with a pruned and prioritized set of Pareto-optimal solutions
based on user-defined objective function preferences. The purpose of this study is to create a bridge between Pareto optimality
and single solution approaches. 相似文献
19.
Curves in the Minkowski space are very well suited to describe the medial axis transform (MAT) of planar domains. Among them, Minkowski Pythagorean hodograph
(MPH) curves correspond to domains where both the boundaries and their offsets admit rational parameterizations (Choi et al.,
Comput Aided Design 31:59–72, 1999; Moon, Comput Aided Geom Design 16:739–753; 1999). We construct MPH quintics which interpolate two points with associated first derivative vectors and analyze the properties
of the system of solutions, including the approximation order of the ‘best’ interpolant.
相似文献
20.
In this paper, we analyze the outer approximation property of the algorithm for generalized semi-infinite programming from
Stein and Still (SIAM J. Control Optim. 42:769–788, 2003). A simple bound on the regularization error is found and used to formulate a feasible numerical method for generalized semi-infinite programming with convex lower-level problems. That is, all iterates of the
numerical method are feasible points of the original optimization problem. The new method has the same computational cost
as the original algorithm from Stein and Still (SIAM J. Control Optim. 42:769–788, 2003). We also discuss the merits of this approach for the adaptive convexification algorithm, a feasible point method for standard
semi-infinite programming from Floudas and Stein (SIAM J. Optim. 18:1187–1208, 2007). 相似文献