Continuity of the optimal value function and optimal solutions of parametric mixed-integer quadratic programs

To properly describe and solve complex decision problems, research on theoretical properties and solution of mixed-integer quadratic programs is becoming very important. We establish in this paper different Lipschitz-type continuity results about the optimal value function and optimal solutions of mixed-integer parametric quadratic programs with parameters in the linear part of the objective function and in the right-hand sides of the linear constraints. The obtained results extend some existing results for continuous quadratic programs, and, more importantly, lay the foundation for further theoretical study and corresponding algorithm analysis on mixed-integer quadratic programs.     

On the continuity of the minimum in parametric quadratic programs

This paper establishes results on the lower semicontinuity and continuity of the optimal objective value of a parametric quadratic program with continuous dependence of the coefficients on parameters. The results established herein generalize directly well-known results on parametric linear programs.This research was supported by the Natural Sciences and Engineering Research Council of Canada under Grant No. A8189.     

Purification for separated continuous linear programs

This paper presents a purification algorithm for a class of infinite-dimensional linear programs called separated continuous linear programs (SCLP). This takes an initial feasible solution and produces an extreme point solution without a decrease in objective function value. The algorithm presented here for SCLP is also shown to be the best possible purification algorithm in a certain class.     

An extended algorithm for separated continuous linear programs

Separated continuous linear programs (SCLP) are a class of continuous linear programs which, among other things, can serve as a useful model for dynamic network problems where storage is permitted at the nodes. Recent work on SCLP has produced a detailed duality theory, conditions under which an optimal solution exists with a finite number of breakpoints, a purification algorithm, as well as a convergent algorithm for solving SCLP under certain assumptions on the problem data. This paper combines much of this work to develop a possible approach for solving a wider range of SCLP problems, namely those with fairly general costs. The techniques required to implement the algorithm are no more than standard (finite-dimensional) linear programming and line searching, and the resulting algorithm is simplex-like in nature. We conclude the paper with the numerical results obtained by using a simple implementation of the algorithm to solve a small problem. Received: May 1994 / Accepted: March 2002?Published online June 25, 2002     

Holder continuity of solutions to a parametric variational inequality

We prove a Hölder continuity property of the locally unique solution to a parametric variational inequality without assuming differentiability of the given data.This research was supported by the World Laboratory (Lausanne).     

关于使用最大改进规则的对偶单纯形算法

本举例证明了[3]的定理10-1是错误的。     

A homogeneous smoothing-type algorithm for symmetric cone linear programs

In this paper, we investigate a smoothing-type algorithm for solving the symmetric cone linear program （（SCLP） for short） by making use of an augmented system of its optimality conditions. The algorithm only needs to solve one system of linear equations and to perform one line search at each iteration. It is proved that the algorithm is globally convergent without assuming any prior knowledge of feasibility/infeasibility of the problem. In particular, the algorithm may correctly detect solvability of （SCLP）. Furthermore, if （SCLP） has a solution, then the algorithm will generate a solution of （SCLP）, and if the problem is strongly infeasible, the algorithm will correctly detect infeasibility of （SCLP）.     

On the parametric linear complementarity problem: A generalized solution procedure

This paper presents a solution procedure for the parametric linear complementarity problemIw–Mz=q+sp,w ^T z=0,w0, andz0, whereM is a positive semidefinite matrix or aP-matrix. This procedure is different from existing ones in the way it handles initialization. By exploiting special relationships between the vectorsq andp, it can reduce computational effort. Sinceq is an arbitrary vector, the procedure can be used for the ordinary linear complementarity problem. In that case, it produces pivots exactly analogous to those of Lemke's algorithm.This paper is based on the author's doctoral dissertation at Johns Hopkins University, 1977. The author wishes to thank her advisors, Professors C. S. ReVelle and D. J. Elzinga. During the last year of her graduate studies, the author held an AAUW-IBM dissertation fellowship.     

第一阶段原有单纯形和对偶单纯形算法的计算比较

线性最优化广泛应用于经济与管理的各个领域.在线性规划问题的求解中,如果一个初始基本可行解没有直接给出,则常采用经典的两阶段法求解.对含有"≥"不等式约束的线性规划问题,讨论了第一阶段原有单纯形法和对偶单纯形法两种算法形式,并根据第一阶段问题的特点提出了改进的对偶单纯形枢轴准则.最后,通过大规模数值试验对两种算法进行计算比较,结果表明,改进后的对偶单纯形算法在计算效率上明显优于原有单纯形算法.     

Adjustable robust solutions of uncertain linear programs

We consider linear programs with uncertain parameters, lying in some prescribed uncertainty set, where part of the variables must be determined before the realization of the uncertain parameters (``non-adjustable variables'), while the other part are variables that can be chosen after the realization (``adjustable variables'). We extend the Robust Optimization methodology ([1, 3-6, 9, 13, 14]) to this situation by introducing the Adjustable Robust Counterpart (ARC) associated with an LP of the above structure. Often the ARC is significantly less conservative than the usual Robust Counterpart (RC), however, in most cases the ARC is computationally intractable (NP-hard). This difficulty is addressed by restricting the adjustable variables to be affine functions of the uncertain data. The ensuing Affinely Adjustable Robust Counterpart (AARC) problem is then shown to be, in certain important cases, equivalent to a tractable optimization problem (typically an LP or a Semidefinite problem), and in other cases, having a tight approximation which is tractable. The AARC approach is illustrated by applying it to a multi-stage inventory management problem.Research was partially supported by the Israeli Ministry of Science grant #0200-1-98, the Israel Science Foundation founded by The Israel Academy of Sciences and Humanities, grant #683/99-10.0, and the Fund for Promotion of Research at the Technion.     

全方位搜索的亚基迭代算法

文章改进了单纯形算法中的进基规则和迭代方式,与原始单纯形算法相比,能够有效地减少迭代次数,提高计算速度     

The continuity of the optimum in parametric programming and applications to stochastic programming

It is proved a sufficient condition that the optimal value of a linear program be a continuous function of the coefficients. The condition isessential, in the sense that, if it is not imposed, then examples with discontinuous optimal-value function may be found. It is shown that certain classes of linear programs important in applications satisfy this condition. Using the relation between parametric linear programming and the distribution problem in stochastic programming, a necessary and sufficient condition is given that such a program has optimal value. Stable stochastic linear programs are introduced, and a sufficient condition of such stability, important in computation problems, is established.This note is a slightly modified version of a paper presented at the Institute of Econometrics and Operations Research of the University of Bonn, Bonn, Germany, 1972.The author is grateful to G. B. Dantzig and S. Karamardian for useful comments on an earlier draft of this paper. In particular, S. Karamardian proposed modifications which made clearer the proof of Lemma 2.1.     

A note on solutions for asymptotically linear elliptic systems

In this paper, we are concerned with the elliptic system of
{ -△u＋V（x）u=g（x,v）, x∈R^N,
-△v＋V（x）v=f（x,u）, x∈R^N,
where V（x） is a continuous potential well, f, g are continuous and asymptotically linear as t→∞. The existence of a positive solution and ground state solution are established via variational methods.     

求线性规划对偶问题最优解的一种方法

线性规划对偶问题的最优解有重要的经济意义,中给出了一种较为简捷的求对偶问题最优解的方法。     

A dual strategy for solving the linear programming relaxation of a driver scheduling system

A Mathematical Programming model of a driver scheduling system is described. This consists of set covering and partitioning constraints, possibly user-supplied side constraints, and two pre-emptively ordered objectives. The previous solution strategy addressed the two objectives using separate Primal Simplex optimisations; a new strategy uses a single weighted objective function and a Dual Simplex algorithm initiated by a specially developed heuristic. Computational results are reported.     

线性规划的目标函数最速递减算法

在对偶单纯形方法的基础上，提出了线性规划的目标函数最速递减算法。它避开求初始可行基或初始基，以目标函数全局快速递减作为选基准则，将选基过程与换基迭代合二为一，从而大大减少了迭代次数。数值算例显示了该算法的有效性和优越性。     

Inner and outer bounds for the solution set of parametric linear systems

Consider linear systems involving affine-linear dependencies on interval parameters. Presented is a free C-XSC software implementing a generalized parametric fixed-point iteration method for verified enclosure of the parametric solution set. Some specific features of the corresponding algorithm concerning sharp enclosure of the contracting matrix and inner approximation of the solution enclosure are discussed.     

A note on the parametric maximum flow problem and some related reoptimization issues

In this paper, we will extend the results about the parametric maximum flow problem to networks in which the parametrization of the arc capacities can involve both the source and the sink, as in Gallo, Grigoriadis, and Tarjan (1989), and also an additional node. We will show that the minimum cuts of the investigated networks satisfy a relaxed form of the generalized nesting property (Arai, Ueno, and Kajitani, 1993). A consequence is that the corresponding parametric maximum flow value function has at most n −1 breakpoints. All the minimum cut capacities can therefore be computed by O(1) maximum flow computations. We will show then that, given O(n) increasing values of the parameter, it is possible to compute the corresponding maximum flows by O(1) maximum flow computations, by suitably extending Goldberg and Tarjan’s maximum flow algorithm.     

A primal—dual infeasible-interior-point algorithm for linear programming

As in many primal—dual interior-point algorithms, a primal—dual infeasible-interior-point algorithm chooses a new point along the Newton direction towards a point on the central trajectory, but it does not confine the iterates within the feasible region. This paper proposes a step length rule with which the algorithm takes large distinct step lengths in the primal and dual spaces and enjoys the global convergence.Part of this research was done when M. Kojima and S. Mizuno visited at the IBM Almaden Research Center. Partial support from the Office of Naval Research under Contract N00014-91-C-0026 is acknowledged.Supported by Grant-in-Aids for Co-operative Research (03832017) of The Japan Ministry of Education, Science and Culture.Supported by Grant-in-Aids for Encouragement of Young Scientist (03740125) and Co-operative Research (03832017) of The Japan Ministry of Education, Science and Culture.     

On alternative optimal solutions to quasimonotonic programming with linear constraints

In this paper, the nonlinear programming problem with quasimonotonic （ both quasiconvex and quasiconcave ）objective function and linear constraints is considered. With the decomposition theorem of polyhedral sets, the structure of optimal solution set for the programming problem is depicted. Based on a simplified version of the convex simplex method, the uniqueness condition of optimal solution and the computational procedures to determine all optimal solutions are given, if the uniqueness condition is not satisfied. An illustrative example is also presented.