A critical review of discrete filled function methods in solving nonlinear discrete optimization problems

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.     

Closest assignment constraints in discrete location problems

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.     

A flexible model and efficient solution strategies for discrete location problems

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.     

求解应急医疗设施分层递进式选址问题的改进免疫算法

针对应急医疗设施的特点,提出分层递进式选址方法,对应急医疗设施进行合理选址.首先,通过熵权法对选址所需要考虑的因素进行权重计算,并进行初步选址;其次,考虑设施点的服务容量、重大公共卫生事件下轻重症患者的治疗与转移的实际情况,建立双层级整数规划模型;再次,根据模型的具体特点,设计改进的免疫优化算法对其进行求解;最后,以湖...     

GASUB: finding global optima to discrete location problems by a genetic-like algorithm

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.     

Genetic algorithms for solving the discrete ordered median problem

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.     

On the convergence of a modified algorithm for the spherical facility location problem

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.     

A discrete long-term location–price problem under the assumption of discriminatory pricing: Formulations and parametric analysis

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.     

The location of public facilities intermediate to the journey to work

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.     

Application of the discrete Fourier transform to solving the Cauchy integral equation

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.     

On the lexicographic minimax approach to location problems

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.     

Computation of lower bounds on the network cost in location problems subject to distance constraints

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.     

On the convergence of the Weiszfeld algorithm for continuous single facility location–allocation problems

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.     

一类离散动力系统的稳定性

研究一类作 为基因选择模 型的离散动力系 统ｙ ｎ ＋ １ ＝ ｙｎ ｅｂ（ １ － ２ ｙ ｎ － ｋ ）１－ ｙｎ ＋ ｙｎ ｅｂ（ １ － ２ ｙ ｎ － ｋ ） ,　ｎ ＝ ０,１,… ,的稳定性 ,其中 ｂ∈（０,∞）, Ｋ∈ ｛１,２,…｝     

On the global periodicity of discrete dynamical systems and application to rational difference equations

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.     

Approximate hierarchical facility location and applications to the bounded depth Steiner tree and range assignment problems

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 D₁,D₂,…,D_h−1 of locations that may open an intermediate transmission station and a set D_h of locations of clients. Each client in D_h must be serviced by an open transmission station in D_h−1 and every open transmission station in D_l must be serviced by an open transmission station on the next lower level, D_l−1. An open transmission station on the first level, D₁ 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 c_ij. For iF, the cost of opening a facility at location i is f_i0. 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.     

On the discounted penalty function in the discrete time stationary renewal risk model

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.     

Determinant formulas with applications to designing when the observations are correlated

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).     

On the regularity of second order cone programs and an application to solving large scale problems

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.     

On the Lanczos and Golub–Kahan reduction methods applied to discrete ill‐posed problems

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.