Converging Marriage in Honey-Bees Optimization and Application to Stochastic Dynamic Programming

In this paper, we first refine a recently proposed metaheuristic called “Marriage in Honey-Bees Optimization” (MBO) for solving combinatorial optimization problems with some modifications to formally show that MBO converges to the global optimum value. We then adapt MBO into an algorithm called “Honey-Bees Policy Iteration” (HBPI) for solving infinite horizon-discounted cost stochastic dynamic programming problems and show that HBPI also converges to the optimal value.     

On the multi-attribute stopping problem with general value functions

We examine a sequential selection problem in which a single option must be selected. Each option's value is a function of its attributes, whose precise values can be ascertained at a given cost. We prove the optimality of a threshold stopping rule for a general class of objective functions.     

Tree-edges deletion problems with bounded diameter obstruction sets

We study the following problem: given a tree G and a finite set of trees H, find a subset O of the edges of G such that G-O does not contain a subtree isomorphic to a tree from H, and O has minimum cardinality. We give sharp boundaries on the tractability of this problem: the problem is polynomial when all the trees in H have diameter at most 5, while it is NP-hard when all the trees in H have diameter at most 6. We also show that the problem is polynomial when every tree in H has at most one vertex with degree more than 2, while it is NP-hard when the trees in H can have two such vertices.The polynomial-time algorithms use a variation of a known technique for solving graph problems. While the standard technique is based on defining an equivalence relation on graphs, we define a quasiorder. This new variation might be useful for giving more efficient algorithm for other graph problems.     

SDP diagonalizations and perspective cuts for a class of nonseparable MIQP

We present a new approach, requiring the solution of a SemiDefinite Program, for decomposing the Hessian of a nonseparable mixed-integer quadratic problem to permit using perspective cuts to improve its continuous relaxation bound. The new method favorably compares with a previously proposed one requiring a minimum eigenvalue computation.     

Solving the p-Median Problem with a Semi-Lagrangian Relaxation

Lagrangian relaxation is commonly used in combinatorial optimization to generate lower bounds for a minimization problem. We study a modified Lagrangian relaxation which generates an optimal integer solution. We call it semi-Lagrangian relaxation and illustrate its practical value by solving large-scale instances of the p-median problem. This work was partially supported by the Fonds National Suisse de la Recherche Scientifique, grant 12-57093.99 and the Spanish government, MCYT subsidy dpi2002-03330.     

Fast computation of a rational point of a variety over a finite field

We exhibit a probabilistic algorithm which computes a rational point of an absolutely irreducible variety over a finite field defined by a reduced regular sequence. Its time-space complexity is roughly quadratic in the logarithm of the cardinality of the field and a geometric invariant of the input system. This invariant, called the degree, is bounded by the Bézout number of the system. Our algorithm works for fields of any characteristic, but requires the cardinality of the field to be greater than a quantity which is roughly the fourth power of the degree of the input variety.

     

Solving multiple-objective problems in the objective space

Projection and relaxation techniques are employed to decompose a multiobjective problem into a two-level structure. The basic manipulation consists in projecting the decision variables onto the space of the implicit tradeoffs, allowing the definition of a relaxed multiobjective master problem directly in the objective space. An additional subproblem tests the feasibility of the solution encountered by the relaxed problem. Some properties of the relaxed problem (linearity, small number of variables, etc.) render its solution efficient by a number of methods. Representatives of two different classes of multiobjective methods [the Geoffrion, Dyer, Feinberg (GDF) method and the fuzzy method of Baptistella and Ollero] are implemented and applied within this context to a water resources allocation problem. The results attest the computational viability of the overall procedure and its usefulness for the solution of multiobjective problems.This work was partially sponsored by grants from CNP_q and FAPESP, Brazil. The authors are indebted to the anonymous reviewers for their valuable comments.     

Sample-path optimization of convex stochastic performance functions

In this paper we propose a method for optimizing convex performance functions in stochastic systems. These functions can include expected performance in static systems and steady-state performance in discrete-event dynamic systems; they may be nonsmooth. The method is closely related to retrospective simulation optimization; it appears to overcome some limitations of stochastic approximation, which is often applied to such problems. We explain the method and give computational results for two classes of problems: tandem production lines with up to 50 machines, and stochastic PERT (Program Evaluation and Review Technique) problems with up to 70 nodes and 110 arcs. Sponsored by the National Science Foundation under grant number CCR-9109345, by the Air Force Systems Command, USAF, under grant numbers F49620-93-1-0068 and F49620-95-1-0222, by the U.S. Army Research Office under grant number DAAL03-92-G-0408, and by the U.S. Army Space and Strategic Defense Command under contract number DASG60-91-C-0144. The U.S. Government has certain rights in this material, and is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. Sponsored by a Wisconsin/Hilldale Research Award, by the U.S. Army Space and Strategic Defense Command under contract number DASG60-91-C-0144, and the Air Force Systems Command, USAF, under grant number F49620-93-1-0068. Sponsored by the National Science Foundation under grant number DDM-9201813.     

Generating well-behaved utility functions for compromise programming

The purpose of this paper is to seek utility functions satisfying a weak condition which guarantees that the utility optimum always belongs to the compromise set. This set is a special subset of the attainable or feasible set, which is generated through the application of the well-known operational research approach called compromise programming. It is shown that there are large families of utility functions satisfying this condition, thus reinforcing the value of compromise programming as a good surrogate of the traditional utility optimum.Thanks are due to the reviewers for their helpful suggestions. The English editing by Ms. Christine Méndez is appreciated. The authors have been supported by the Comisión Interministerial de Ciencia y Tecnología (CICYT), Madrid, Spain.     

On the numerical solution of a class of Stackelberg problems

This study tries to develop two new approaches to the numerical solution of Stackelberg problems. In both of them the tools of nonsmooth analysis are extensively exploited; in particular we utilize some results concerning the differentiability of marginal functions and some stability results concerning the solutions of convex programs. The approaches are illustrated by simple examples and an optimum design problem with an elliptic variational inequality.Prepared while the author was visiting the Department of Mathematics, University of Bayreuth as a guest of the FSP Anwendungsbezogene Optimierung und Steuerung.