The Bottleneck Linear programming problem (BLP) is to maximizex0 = max j c j ,x j > 0 subject toAx = b, x ⩾ 0. A relationship between the BLP and a problem solvable by a “greedy” algorithm is established. Two alg...
详细信息
The Bottleneck Linear programming problem (BLP) is to maximizex0 = max j c j ,x j > 0 subject toAx = b, x ⩾ 0. A relationship between the BLP and a problem solvable by a “greedy” algorithm is established. Two algorithms for the BLP are developed and computational experience is reported.
In this paper we establish a theoretical basis for utilizing a penalty-function method to estimate sensitivity information (i.e., the partial derivatives) of a localsolution and its associated Lagrange multipliers of ...
详细信息
In this paper we establish a theoretical basis for utilizing a penalty-function method to estimate sensitivity information (i.e., the partial derivatives) of a localsolution and its associated Lagrange multipliers of a large class of nonlinear programming problems with respect to a general parametric variation in the problem functions. The local solution is assumed to satisfy the second order sufficient conditions for a strict minimum. Although theoretically valid for higher order derivatives, the analysis concentrates on the estimation of the first order (first partial derivative) sensitivity information, which can be explicitly expressed in terms of the problem functions. For greater clarity, the results are given in terms of the mixed logarithmic-barrier quadratic-loss function. However, the approach is clearly applicable toany algorithm that generates a once differentiable “solution trajectory”.
It is shown that the linear complementarity problem of finding az inRn such thatMz + q ⩾ 0, z ⩾ 0 andzT(Mz + q) = 0 can be solved by a single linear program in some important special cases including those whenM or its...
详细信息
It is shown that the linear complementarity problem of finding az inRn such thatMz + q ⩾ 0, z ⩾ 0 andzT(Mz + q) = 0 can be solved by a single linear program in some important special cases including those whenM or its inverse is a Z-matrix, that is a real square matrix with nonpositive off-diagonal elements. As a consequence certain problems in mechanics, certain problems of finding the least element of a polyhedral set and certain quadratic programming problems, can each be solved by a single linear program.
For nonlinear programming problems which are factorable, a computable procedure for obtaining tight underestimating convex programs is presented. This is used to exclude from consideration regions where the global min...
详细信息
For nonlinear programming problems which are factorable, a computable procedure for obtaining tight underestimating convex programs is presented. This is used to exclude from consideration regions where the global minimizer cannot exist.
Large practical linear and integer programming problems are not always presented in a form which is the most compact representation of the problem. Such problems are likely to posses generalized upper bound(GUB) and r...
详细信息
Large practical linear and integer programming problems are not always presented in a form which is the most compact representation of the problem. Such problems are likely to posses generalized upper bound(GUB) and related structures which may be exploited by algorithms designed to solve them *** steps of an algorithm which by repeated application reduces the rows, columns, and bounds in a problem matrix and leads to the freeing of some variables are first presented. The ‘unbounded solution’ and ‘no feasible solution’ conditions may also be detected by this. Computational results of applying this algorithm are presented and *** algorithm to detect structure is then described. This algorithm identifies sets of variables and the corresponding constraint relationships so that the total number of GUB-type constraints is maximized. Comparisons of computational results of applying different heuristics in this algorithm are presented and discussed.
Abstract. The paper develops a new algorithm for parameter identification in a partial differential equation associated with an inhomogeneous aquifer system. The parameters chosen for identification are the storage co...
详细信息
Abstract. The paper develops a new algorithm for parameter identification in a partial differential equation associated with an inhomogeneous aquifer system. The parameters chosen for identification are the storage coefficient, a constant, and transmissivities, functions of the space variable. An implicit finite-difference scheme is used to approximate the solutions of the governing equation. A least-squares criterion is then established. Using distributed observations on the dependent variable within the system, parameters are identified directly by solving a sequence of quadratic programming problems such that the final solution converges to the original problem. The advantages of this new algorithm problem. The advantages of this new algorithm include rapid rate of convergence, ability to handle any inequality constraints, and easy computer implementation. The numerical example presented demonstrates the simultaneous identification of 12 parameters in only seconds of computer time. parameters in only seconds of computer timeIntroduction. Simulation and mathematical models are often used in analyzing aquifer systems. Physically based mathematical models are implemented by high-speed computers. Most models are of a parametric type, in which parameters used in parametric type, in which parameters used in deriving the governing equation are not measurable directly from the physical point of view and, therefore, must be determined from historical records. The literature dealing with parameter identification in partial differential equations has become available only within the last decade. The approaches include gradient searching procedures, the balanced error-weighted gradient method, the classical Gauss-Newton least-squares procedure, optimal control and gradient optimization, quasi linearization, influence coefficient algorithm, linear programming, maximum principle, and regression analysis allied with the steepest-descent algorithm. Yeh analyzed a typical paramet
We discuss the problem of selecting the points in an (n×n) Vandermonde matrix so as to minimize the condition number of the matrix. We give numerical answers for 2≦n≦6 in the case of symmetric point configurati...
详细信息
We discuss the problem of selecting the points in an (n×n) Vandermonde matrix so as to minimize the condition number of the matrix. We give numerical answers for 2≦n≦6 in the case of symmetric point configurations. We also consider points on the non-negative real line, and give numerical results forn=2 andn=3. For generaln, the problem can be formulated as a nonlinear minimax problem with nonlinear constraints or, equivalently, as a nonlinear programming problem.
The role of 0–1 programming problems having monotone or regular feasible sets was pointed out in [6]. The solution sets of covering and of knapsack problems are examples of monotone and of regular sets respectively. ...
详细信息
The role of 0–1 programming problems having monotone or regular feasible sets was pointed out in [6]. The solution sets of covering and of knapsack problems are examples of monotone and of regular sets respectively. Some connections are established between prime implicants of a monotone or a regular Boolean functionβ on the one hand, and facets of the convex hullH of the zeros ofβ on the other. In particular (Corollary 2) a necessary and sufficient condition is given for a constraint of a covering problem to be a facet of the corresponding integer polyhedron. For any prime implicantP ofβ, a nonempty familyF(P) of facets ofH is constructed. Proposition 17 gives easy-to-determine sharp upper bounds for the coefficients of these facets whenβ is regular. A special class of prime implicants is described for regular functions and it is shown that for anyP in this class,F(P) consists of one facet ofH, and this facet has 0–1 coefficients. Every nontrivial facet ofH with 0–1 coefficients is obtained from this class.
This paper identifies necessary and sufficient conditions for a penalty method to yield an optimal solution or a Lagrange multiplier of a convex programming problem by means of a single unconstrained minimization. The...
详细信息
This paper identifies necessary and sufficient conditions for a penalty method to yield an optimal solution or a Lagrange multiplier of a convex programming problem by means of a single unconstrained minimization. The conditions are given in terms of properties of the objective and constraint functions of the problem as well as the penalty function adopted. It is shown among other things that all linear programs with finite optimal value satisfy such conditions when the penalty function is quadratic.
暂无评论