共查询到20条相似文献,搜索用时 31 毫秒
1.
Many real life problems can be modeled as nonlinear discrete optimization problems. Such problems often have multiple local minima and thus require global optimization methods. Due to high complexity of these problems, heuristic based global optimization techniques are usually required when solving large scale discrete optimization or mixed discrete optimization problems. One of the more recent global optimization tools is known as the discrete filled function method. Nine variations of the discrete filled function method in literature are identified and a review on theoretical properties of each method is given. Some of the most promising filled functions are tested on various benchmark problems. Numerical results are given for comparison. 相似文献
2.
Inmaculada EspejoAlfredo Marín Antonio M. Rodríguez-Chía 《European Journal of Operational Research》2012,219(1):49-58
The objective of this paper is to identify the most promising sets of closest assignment constraints in the literature of Discrete Location Theory, helping the authors in the field to model their problems when clients must be assigned to the closest plant inside an Integer Programming formulation. In particular, constraints leading to weak Linear Programming relaxations should be avoided if no other good property supports their use. We also propose a new set of constraints with good theoretical properties. 相似文献
3.
Flexible discrete location problems are a generalization of most classical discrete locations problems like p-median or p-center problems. They can be modeled by using so-called ordered median functions. These functions multiply a weight to the cost of fulfilling the demand of a customer, which depends on the position of that cost relative to the costs of fulfilling the demand of other customers.In this paper a covering type of model for the discrete ordered median problem is presented. For the solution of this model two sets of valid inequalities, which reduces the number of binary variables tremendously, and several variable fixing strategies are identified. Based on these concepts a specialized branch & cut procedure is proposed and extensive computational results are reported. 相似文献
4.
5.
Blas Pelegrín Juani L. Redondo Pascual Fernández Inmaculada García Pilar M. Ortigosa 《Journal of Global Optimization》2007,38(2):249-264
In many discrete location problems, a given number s of facility locations must be selected from a set of m potential locations, so as to optimize a predetermined fitness function. Most of such problems can be formulated as integer
linear optimization problems, but the standard optimizers only are able to find one global optimum. We propose a new genetic-like
algorithm, GASUB, which is able to find a predetermined number of global optima, if they exist, for a variety of discrete
location problems. In this paper, a performance evaluation of GASUB in terms of its effectiveness (for finding optimal solutions)
and efficiency (computational cost) is carried out. GASUB is also compared to MSH, a multi-start substitution method widely
used for location problems. Computational experiments with three types of discrete location problems show that GASUB obtains
better solutions than MSH. Furthermore, the proposed algorithm finds global optima in all tested problems, which is shown
by solving those problems by Xpress-MP, an integer linear programing optimizer (21). Results from testing GASUB with a set
of known test problems are also provided. 相似文献
6.
In this paper we present two new heuristic approaches to solve the Discrete Ordered Median Problem (DOMP). Described heuristic methods, named HGA1 and HGA2 are based on a hybrid of genetic algorithms (GA) and a generalization of the well-known Fast Interchange heuristic (GFI). In order to investigate the effect of encoding on GA performance, two different encoding schemes are implemented: binary encoding in HGA1, and integer representation in HGA2. If binary encoding is used (HGA1), new genetic operators that keep the feasibility of individuals are proposed. Integer representation keeps the individuals feasible by default, so HGA2 uses slightly modified standard genetic operators. In both methods, caching GA technique was integrated with the GFI heuristic to improve computational performance. The algorithms are tested on standard ORLIB p-median instances with up to 900 nodes. The obtained results are also compared with the results of existing methods for solving DOMP in order to assess their merits. 相似文献
7.
Liping Zhang 《Operations Research Letters》2003,31(2):161-166
We study the spherical facility location problem which is a more realistic model than the Euclidean facilities location. We present a modified algorithm for this problem, which has the following good properties: (a) It is very easy to initialize the algorithm with an arbitrary point as its starting point; (b) Under suitable assumptions, it is proved that the algorithm globally converges to a global minimizer of the problem. 相似文献
8.
Pascual Fernández Blas Pelegrín María Dolores García Pérez Peter H. Peeters 《European Journal of Operational Research》2007
We consider a competitive location problem in which a new firm has to make decisions on the locations of several new facilities as well as on its price setting in order to maximise profit. Under the assumption of discriminatory prices, competing firms set a specific price for each market area. The customers buy one unit of a single homogeneous price-inelastic product from the facility that offers the lowest price in the area the consumers belong to. Three customer choice rules are considered in order to break ties in the offered prices. We prove that, considering long-term competition on price, this problem can be reduced to a problem with decisions on location only. For each one of the choice rules the location problem is formulated as an integer programming model and a parametric analysis of these models is given. To conclude, an application with real data is presented. 相似文献
9.
M. John Hodgson 《European Journal of Operational Research》1981,6(2):199-204
Location—allocation models typically locate facilities with respect to points to be served, for example to the homes of potential patrons. Certain types of facility, however, are employed by persons who travel to the facility from their homes and continue their journey to another location. Child care facilities are an example of this pattern of patronage, with parents dropping children off at a centre en route to work. The paper presents a discrete-space location—allocation model minimizing the diversion of patrons' journeys to work. The problem reduces to the structure and combinatorial dimensions of the simple P-median problem. The model is applied to the transit worktrip patterns of single parents in Edmonton, Canada. The facilities generated by the model tend to central locations in the city where workplaces are concentrated and transit connections are efficient. The model provides a compromise between ones minimizing home-facility travel times and facility-workplace travel times. 相似文献
10.
V.V. Kolybasova P.A. KrutitskiiK.V. Prozorov G. Vainikko 《Journal of Computational and Applied Mathematics》2011,235(5):1317-1325
The uniquely solvable system of the Cauchy integral equation of the first kind and index 1 and an additional integral condition is treated. Such a system arises, for example, when solving the skew derivative problem for the Laplace equation outside an open arc in a plane. This problem models the electric current from a thin electrode in a semiconductor film placed in a magnetic field. A fast and accurate numerical method based on the discrete Fourier transform is proposed. Some computational tests are given. It is shown that the convergence is close to exponential. 相似文献
11.
When locating public facilities, the distribution of travel distances among the service recipients is an important issue. It is usually tackled with the minimax (center) solution concept. The minimax solution concept, despite the most commonly used in the public sector location models, is criticized as it does not comply with the major principles of the efficiency and equity modeling. In this paper we develop a concept of the lexicographic minimax solution (lexicographic center) being a refinement of the standard minimax approach to location problems. We show that the lexicographic minimax approach complies with both the Pareto-optimality (efficiency) principle (crucial in multiple criteria optimization) and the principle of transfers (essential for equity measures) whereas the standard minimax approach may violate both these principles. Computational algorithms are developed for the lexicographic minimax solution of discrete location problems. 相似文献
12.
Computation of lower bounds on the network cost in location problems subject to distance constraints
G. G. Zabudsky 《Computational Mathematics and Mathematical Physics》2006,46(2):206-211
Methods for the computation of lower bounds on the cost of the connecting network for the continuous and discrete variants of the problem of location of interconnected objects subject to minimal or maximal distances between them are proposed. For the continuous variant, the bound is found by solving a linear programming problem. For the discrete variant, an assignment problem with a rectangular matrix containing forbidden entries is constructed. An application of the assignment problem for locating objects of various sizes is described. 相似文献
13.
A general family of single facility continuous location–allocation problems is introduced, which includes the decreasingly
weighted ordered median problem, the single facility Weber problem with supply surplus, and Weber problems with alternative
fast transportation network. We show in this paper that the extension of the well known Weiszfeld iterative decrease method
for solving the corresponding location problems with fixed allocation yields an always convergent scheme for the location
allocation problems. In a generic way, from each starting point, the limit point will be a locally minimal solution, whereas
for each possible exceptional situation, a possible solution is indicated. Some computational results are presented, comparing
this method with an alternating location–allocation approach.
The research of the second author was partially supported by the grant of the Algerian Ministry of High Education 001BIS/PNE/ENSEIGNANTS/BELGIQUE. 相似文献
14.
研究一类作 为基因选择模 型的离散动力系 统y n + 1 = yn eb( 1 - 2 y n - k )1- yn + yn eb( 1 - 2 y n - k ) , n = 0,1,… ,的稳定性 ,其中 b∈(0,∞), K∈ {1,2,…} 相似文献
15.
J. Rubió-Massegú 《Journal of Mathematical Analysis and Applications》2008,343(1):182-189
A new necessary condition for global periodicity of discrete dynamical systems and of difference equations is obtained here. This condition will be applied to contribute to solving the problem of global periodicity for second order rational difference equations. 相似文献
16.
The paper concerns a new variant of the hierarchical facility location problem on metric powers (HFLβ[h]), which is a multi-level uncapacitated facility location problem defined as follows. The input consists of a set F of locations that may open a facility, subsets D1,D2,…,Dh−1 of locations that may open an intermediate transmission station and a set Dh of locations of clients. Each client in Dh must be serviced by an open transmission station in Dh−1 and every open transmission station in Dl must be serviced by an open transmission station on the next lower level, Dl−1. An open transmission station on the first level, D1 must be serviced by an open facility. The cost of assigning a station j on level l1 to a station i on level l−1 is cij. For iF, the cost of opening a facility at location i is fi0. It is required to find a feasible assignment that minimizes the total cost. A constant ratio approximation algorithm is established for this problem. This algorithm is then used to develop constant ratio approximation algorithms for the bounded depth Steiner tree problem and the bounded hop strong-connectivity range assignment problem. 相似文献
17.
In this paper we consider the discrete time stationary renewal risk model. We express the Gerber-Shiu discounted penalty function in the stationary renewal risk model in terms of the corresponding Gerber-Shiu function in the ordinary model. In particular, we obtain a defective renewal equation for the probability generating function of ruin time. The solution of the renewal equation is then given. The explicit formulas for the discounted survival distribution of the deficit at ruin are also derived. 相似文献
18.
Wolfgang Bischoff 《Annals of the Institute of Statistical Mathematics》1995,47(2):385-399
In the general linear model consider the designing problem for the Gauß-Markov estimator or for the least squares estimator when the observations are correlated. Determinant formulas are proved being useful for theD-criterion. They allow, for example, a (nearly) elementary proof and a generalization of recent results for an important linear model with multiple response. In the second part of the paper the determinant formulas are used for deriving lower bounds for the efficiency of a design. These bounds are applied in examples for tridiagonal covariance matrices. For these examples maximin designs are determined.Parts of the paper are based on a part of the author's Habilitationsschrift Bischoff (1993a). 相似文献
19.
Katrin Schmallowsky 《Mathematical Methods of Operations Research》2008,68(3):551-564
We prove the nonsingularity of the standard primal–dual system for second order cone programs assuming Slater’s condition,
uniqueness and strict complementarity. This result is applied to the analysis of the augmented primal–dual method for solving
linear programs over second order cones. 相似文献
20.
Silvia Gazzola Enyinda Onunwor Lothar Reichel Giuseppe Rodriguez 《Numerical Linear Algebra with Applications》2016,23(1):187-204
The symmetric Lanczos method is commonly applied to reduce large‐scale symmetric linear discrete ill‐posed problems to small ones with a symmetric tridiagonal matrix. We investigate how quickly the nonnegative subdiagonal entries of this matrix decay to zero. Their fast decay to zero suggests that there is little benefit in expressing the solution of the discrete ill‐posed problems in terms of the eigenvectors of the matrix compared with using a basis of Lanczos vectors, which are cheaper to compute. Similarly, we show that the solution subspace determined by the LSQR method when applied to the solution of linear discrete ill‐posed problems with a nonsymmetric matrix often can be used instead of the solution subspace determined by the singular value decomposition without significant, if any, reduction of the quality of the computed solution. Copyright © 2015 John Wiley & Sons, Ltd. 相似文献