Search

Model reference adaptive search (MRAS) for solving global optimization problems works with a parameterized probabilistic model on the solution space and generates at each iteration a group of candidate solutions. These candidate solutions are then used to update the parameters associated with the probabilistic model in such a way that the future search will be biased toward the region containing high-quality solutions. The parameter updating procedure in MRAS is guided by a sequence of implicit probabilistic models we call reference models. We provide a particular algorithm instantiation of the MRAS method, where the sequence of reference models can be viewed as the generalized probability distribution models for estimation of distribution algorithms (EDAs) with proportional selection scheme. In addition, we show that the model reference framework can also be used to describe the recently proposed cross-entropy (CE) method for optimization and to study its properties. Hence, this paper can also be seen as a study on the effectiveness of combining CE and EDAs. We prove global convergence of the proposed algorithm in both continuous and combinatorial domains, and we carry out numerical studies to illustrate the performance of the algorithm. [ABSTRACT FROM AUTHOR]

T = (V, E) is a tree with nonnegative weights associated with each of its vertices. A fleet of vehicles of capacity Q is located at the depot represented by vertex v[sub 1]. The Capacitated Vehicle Routing Problem on Trees (TCVRP) consists of determining vehicle collection routes starting and ending at the depot such that: the weight associated with any given vertex is collected by exactly one vehicle; the sum of all weights collected by a vehicle does not exceed Q; a linear combination of the number of vehicles and of the total distance traveled by these vehicles is minimized. The TCVRP is shown to be NP-hard. This paper presents lower bounds for the TCVRP based on the solutions of associated bin packing problems. We develop a linear time heuristic (upper bound) procedure and present a bound on its worst case performance. These lower and upper bounds are then embedded in an enumerative algorithm. Numerical results follow. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm to compute reliability measures on a stochastic network m which both nodes and links can fad The measures considered are the probability that nodes s and t can communicate for all node pairs s and t, the probability that all operative node pairs can communicate, and the expected number of node pairs communicating It also computes the latter two measures when all communication must proceed through a root node A specialized version of the algorithm is given for networks in which only nodes can fail. [ABSTRACT FROM AUTHOR]

A previous research report of the authors presented a formal model of the one-machine job-shop scheduling problem with variable labor capacity. This report presents some computational experience with the algorithm proposed previously and a discussion of the structural aspects of the problem. Extensions and refinements of the algorithm are introduced to deal with nonsimultaneous job arrivals and the production smoothing problem. These results provide insight into the structure of the aggregate-detailed cost trade-off problem and suggest a good heuristic decision rule for problems of realistic size and complexity. [ABSTRACT FROM AUTHOR]

This paper presents two versions of a method for solving large linear programs through decomposition. In both versions the problem is decomposed into subprograms as in the DANTZIG-WOLFE model, but each version uses a different type of linking program. The subprograms are first solved, and then the infeasibility of the resulting solution for the linking program is used to generate a price-adjustment process (much like a market mechanism), which gradually corrects the objective functions of the subprograms, until either some optimal solutions to the latter yield a feasible solution to the linking program (then the problem is solved), or evidence is obtained that the problem has no feasible solution. [ABSTRACT FROM AUTHOR]

We consider a special case of the transportation problem with 3 supply points and n demand points. An efficient algorithm is provided and the problem is illustrated with an example concerning financial aid to students. [ABSTRACT FROM AUTHOR]