Polynomial time solutions for scheduling problems on a proportionate flowshop with two competing agents

In scheduling problems with two competing agents, each one of the agents has his own set of jobs and his own objective function, but both share the same processor. The goal is to minimize the value of the objective function of one agent, subject to an upper bound on the value of the objective function of the second agent. In this paper we study two-agent scheduling problems on a proportionate flowshop. Three objective functions of the first agent are considered: minimum maximum cost of all the jobs, minimum total completion time, and minimum number of tardy jobs. For the second agent, an upper bound on the maximum allowable cost is assumed. We introduce efficient polynomial time solution algorithms for all cases.     

Directional approach to gradual cover: a maximin objective

The objective of original cover location models is to cover demand within a given distance by facilities. Locating a given number of facilities to cover as much demand as possible is referred to as max-cover, and finding the minimum number of facilities required to cover all the demand is referred to as set covering. When the objective is to maximize the minimum cover of demand points, the maximin objective is equivalent to set covering because each demand point is either covered or not. The gradual (or partial) cover replaces abrupt drop from full cover to no cover by defining gradual decline in cover. Both maximizing total cover and maximizing the minimum cover are useful objectives using the gradual cover measure. In this paper we use a recently proposed rule for calculating the joint cover of a demand point by several facilities termed “directional gradual cover”. The objective is to maximize the minimum cover of demand points. The solution approaches were extensively tested on a case study of covering Orange County, California.

     

Multiple objective minimum cost flow problems: A review

In this paper, theory and algorithms for solving the multiple objective minimum cost flow problem are reviewed. For both the continuous and integer case exact and approximation algorithms are presented. In addition, a section on compromise solutions summarizes corresponding results. The reference list consists of all papers known to the authors which deal with the multiple objective minimum cost flow problem.     

On the Minimum Norm Solution of Linear Programs

This paper describes a new technique to find the minimum norm solution of a linear program. The main idea is to reformulate this problem as an unconstrained minimization problem with a convex and smooth objective function. The minimization of this objective function can be carried out by a Newton-type method which is shown to be globally convergent. Furthermore, under certain assumptions, this Newton-type method converges in a finite number of iterations to the minimum norm solution of the underlying linear program.     

A portfolio theory approach to crop planning under environmental constraints

This paper presents a multiobjective model for crop planning in agriculture. The approach is based on portfolio theory. The model takes into account weather risks, market risks and environmental risks. Input data include historical land productivity data for various crops, soil types and yield response to fertilizer/pesticide application. Several environmental levels for the application of fertilizers/pesticides, and the monetary penalties for overcoming these levels, are also considered. Starting from the multiobjective model we formulate several single objective optimization problems: the minimum environmental risk problem, the maximum expected return problem and the minimum financial risk problem. We prove that the minimum environmental risk problem is equivalent to a mixed integer problem with a linear objective function. Two numerical results for the minimum environmental risk problem are presented.     

A novel three-phase trajectory informed search methodology for global optimization

A new deterministic method for solving a global optimization problem is proposed. The proposed method consists of three phases. The first phase is a typical local search to compute a local minimum. The second phase employs a discrete sup-local search to locate a so-called sup-local minimum taking the lowest objective value among the neighboring local minima. The third phase is an attractor-based global search to locate a new point of next descent with a lower objective value. The simulation results through well-known global optimization problems are shown to demonstrate the efficiency of the proposed method.     

Discrete optimization on a multivariable boolean lattice

Consider the problem of finding the minimum value of a scalar objective function whose arguments are theN components of 2 ^N vector elements partially ordered as a Boolean lattice. If the function is strictly decreasing along any shortest path from the minimum point to its logical complement, then the minimum can be located precisely after sequential measurement of the objective function atN + 1 points. This result suggests a new line of research on discrete optimization problems.This paper was presented at the 7th Mathematical Programming Symposium, The Hague, The Netherlands.This research was supported in part by U.S. Office of Saline Water Grant No. 699.     

Monotone Approximations of Minimum and Maximum Functions and Multi-objective Problems

In this paper the problem of accomplishing multiple objectives by a number of agents represented as dynamic systems is considered. Each agent is assumed to have a goal which is to accomplish one or more objectives where each objective is mathematically formulated using an appropriate objective function. Sufficient conditions for accomplishing objectives are derived using particular convergent approximations of minimum and maximum functions depending on the formulation of the goals and objectives. These approximations are differentiable functions and they monotonically converge to the corresponding minimum or maximum function. Finally, an illustrative pursuit-evasion game example with two evaders and two pursuers is provided.     

An exact method for computing the nadir values in multiple objective linear programming

In this paper we propose a new method to determine the exact nadir (minimum) criterion values over the efficient set in multiple objective linear programming (MOLP). The basic idea of the method is to determine, for each criterion, the region of the weight space associated with the efficient solutions that have a value in that criterion below the minimum already known (by default, the minimum in the payoff table). If this region is empty, the nadir value has been found. Otherwise, a new efficient solution is computed using a weight vector picked from the delimited region and a new iteration is performed. The method is able to find the nadir values in MOLP problems with any number of objective functions, although the computational effort increases significantly with the number of objectives. Computational experiments are described and discussed, comparing two slightly different versions of the method.     

A search technique for global optimization in a chaotic environment

We describe a new algorithm which uses the trajectories of a discrete dynamical system to sample the domain of an unconstrained objective function in search of global minima. The algorithm is unusually adept at avoiding nonoptimal local minima and successfully converging to a global minimum. Trajectories generated by the algorithm for objective functions with many local minima exhibit chaotic behavior, in the sense that they are extremely sensitive to changes in initial conditions and system parameters. In this context, chaos seems to have a beneficial effect: failure to converge to a global minimum from a given initial point can often be rectified by making arbitrarily small changes in the system parameters.     

The biobjective undirected two-commodity minimum cost flow problem

We address the two-commodity minimum cost flow problem considering two objectives. We show that the biobjective undirected two-commodity minimum cost flow problem can be split into two standard biobjective minimum cost flow problems using the change of variables approach. This technique allows us to develop a method that finds all the efficient extreme points in the objective space for the two-commodity problem solving two biobjective minimum cost flow problems. In other words, we generalize the Hu's theorem for the biobjective undirected two-commodity minimum cost flow problem. In addition, we develop a parametric network simplex method to solve the biobjective problem.     

SUSTAINABLE FOREST MANAGEMENT FOR OPTIMIZING MULTISPECIES WILDLIFE HABITAT: A COASTAL DOUGLAS-FIR EXAMPLE

Wildlife species viability optimization models are developed to convert a given set of initial forest conditions, through a combination of natural growth and management treatments, to a forest system which addresses the joint habitat needs of multispecies populations over time. A linear model of forest cover and wildlife populations is used to form a system of forest management control variables for wildlife habitat modification. The paper examines two objective functions coupled to this system for optimizing sustainable joint species viability. The first maximizes the product of periodic joint viabilities over all time periods, focusing management resources on long-term equilibria, with less emphasis on conversion strategy. The second iteratively maximizes the minimum periodic joint viability over all time periods. This focuses management resources on the most limiting time periods, typically the conversion phase periods. Both objective functions resulted in either point or cyclic equilibria, with cycle lengths equal to minimum forest treatment ages. A third objective, based on maximizing the minimum individual species periodic viability is used to examine single species emphasis. Examples are developed through a case study of 92 vertebrate species found in coastal Douglas-fir stands of northwestern California.     

混凝土重力坝多参数弹性位移反演分析不唯一性理论探讨

反演分析是现场监测⁃反演分析⁃工程实践检验⁃正演分析及预测的闭环系统的重要环节,而参数反分析是工程实践中研究最多的反分析问题.针对混凝土重力坝多参数反演分析是否具有唯一性,基于均质地基上重力坝在水压力作用下的位移解析解建立目标函数,进而以目标函数和非空凸集构建一个凸规划问题,然后通过分析目标函数的Hesse矩阵是否是正定矩阵,验证目标函数是否是严格凸函数,从而辨识构建的凸规划问题是否具有唯一全局极小点.对坝体和岩基弹性参数的不同组合方案分析表明,当采用理论值与实测值的差值的l1范数作为目标函数时,目标函数的Hesse矩阵均不能保证为正定矩阵,即混凝土重力坝多参数弹性位移反演分析凸规划问题不具有唯一全局极小点,反演分析不唯一.     

求非光滑全局优化问题的区间算法

本文通过区间工具和目标函数的特殊导数提出了一个非光滑全局优化问题的区间算法，所提出的方法能给出问题的全部全局极小点及全局极小值，理论分析和数值结构均表明本文方法是有效的。     

求广义几何规划全局最优解的线性化方法

对广义几何规划问题(GGP)提出了一个确定型全局优化算法，这类优化问题能广泛应用于工程设计和非线性系统的鲁棒稳定性分析等实际问题中，使用指数变换及对目标函数和约束函数的线性下界估计，建立了GGP的松弛线性规划(RLP)，通过对RLP可行域的细分以及一系列RLP的求解过程，从理论上证明了算法能收敛到GGP的全局最优解，对一个化学工程设计问题应用本文算法，数值实验表明本文方法是可行的。     

Elimination of bounds in optimization problems by transforming variables

The problem of minimizing a nonlinear objective function ofn variables, with continuous first and second partial derivatives, subject to nonnegativity constraints or upper and lower bounds on the variables is studied. The advisability of solving such a constrained optimization problem by making a suitable transformation of its variables in order to change the problem into one of unconstrained minimization is considered. A set of conditions which guarantees that every local minimum of the new unconstrained problem also satisfies the first-order necessary (Kuhn—Tucker) conditions for a local minimum of the original constrained problem is developed. It is shown that there are certain conditions under which the transformed objective function will maintain the convexity of the original objective function in a neighborhood of the solution. A modification of the method of transformations which moves away from extraneous stationary points is introduced and conditions under which the method generates a sequence of points which converges to the solution at a superlinear rate are given.     

Stochastic Analysis of the Weber Problem on the Sphere

In this paper we deal with the location of one facility on the surface of the sphere (globe) that minimizes the weighted sum of distances to a given set of demand points on the surface of the sphere. We assume that demand points are randomly generated on the sphere, and so are the weights. We prove that when the number of demand points increases to infinity, then the ratio between the maximum possible value of the objective function and the minimum possible value of the objective function converges to one. We also show that the expected number of demand points that are a local minimum is approximately one when there are a large number of demand points. Some computational experiments are presented.     

Direct solution to constrained tropical optimization problems with application to project scheduling

We examine a new optimization problem formulated in the tropical mathematics setting as a further extension of certain known problems. The problem is to minimize a nonlinear objective function, which is defined on vectors over an idempotent semifield by using multiplicative conjugate transposition, subject to inequality constraints. As compared to the known problems, the new one has a more general objective function and additional constraints. We provide a complete solution in an explicit form to the problem by using an approach that introduces an auxiliary variable to represent the values of the objective function, and then reduces the initial problem to a parametrized vector inequality. The minimum of the objective function is evaluated by applying the existence conditions for the solution of this inequality. A complete solution to the problem is given by solving the parametrized inequality, provided the parameter is set to the minimum value. As a consequence, we obtain solutions to new special cases of the general problem. To illustrate the application of the results, we solve a real-world problem drawn from time-constrained project scheduling, and offer a representative numerical example.     

Stability of Local Efficiency in Multiobjective Optimization

Analyzing the behavior and stability properties of a local optimum in an optimization problem, when small perturbations are added to the objective functions, are important considerations in optimization. The tilt stability of a local minimum in a scalar optimization problem is a well-studied concept in optimization which is a version of the Lipschitzian stability condition for a local minimum. In this paper, we define a new concept of stability pertinent to the study of multiobjective optimization problems. We prove that our new concept of stability is equivalent to tilt stability when scalar optimizations are available. We then use our new notions of stability to establish new necessary and sufficient conditions on when strict locally efficient solutions of a multiobjective optimization problem will have small changes when correspondingly small perturbations are added to the objective functions.     

非光滑总体优化的区间算法[英文]

本文利用区间工具及目标函数的特殊导数，给出一个非光滑总体优化的区间算法，该算法提供了目标函数总体极小值及总体极小点的取值界限（在给定的精度范围内）。我们也将算法推广到并行计算中。数值实验表明本文方法是可靠和有效的。