Duality for minmax programming involving V-invex functions

Sufficient optimality conditions and duality results for a class of minmax programming problems are obtained under V-invexity type assumptions on objective and constraint functions. Applications of these results to certain fractional and generalized fractional programming problems are also presented     

Polynomial Algorithms for a Class of Discrete Minmax Linear Programming Problems

We consider the problem of obtaining integer solutions to a minmax linear programming problem. Although this general problem is NP-complete, it is shown that a restricted version of this problem can be solved in polynomial time. For this restricted class of problems two polynomial time algorithms are suggested, one of which is strongly polynomial whenever its continuous analogue and an associated linear programming problem can be solved by a strongly polynomial algorithm. Our algorithms can also be used to obtain integer solutions for the minmax transportation problem with an inequality budget constraint. The equality constrained version of this problem is shown to be NP-complete. We also provide some new insights into the solution procedures for the continuous minmax linear programming problem.     

On the complexity of minmax regret linear programming

We consider linear programming problems with uncertain objective function coefficients. For each coefficient of the objective function, an interval of uncertainty is known, and it is assumed that any coefficient can take on any value from the corresponding interval of uncertainty, regardless of the values taken by other coefficients. It is required to find a minmax regret solution. This problem received considerable attention in the recent literature, but its computational complexity status remained unknown. We prove that the problem is strongly NP-hard. This gives the first known example of a minmax regret optimization problem that is NP-hard in the case of interval-data representation of uncertainty but is polynomially solvable in the case of discrete-scenario representation of uncertainty.     

Finding an efficient solution to linear bilevel programming problem: An effective approach

Multilevel programming is developed to solve the decentralized problem in which decision makers (DMs) are often arranged within a hierarchical administrative structure. The linear bilevel programming (BLP) problem, i.e., a special case of multilevel programming problems with a two level structure, is a set of nested linear optimization problems over polyhedral set of constraints. Two DMs are located at the different hierarchical levels, both controlling one set of decision variables independently, with different and perhaps conflicting objective functions. One of the interesting features of the linear BLP problem is that its solution may not be Paretooptimal. There may exist a feasible solution where one or both levels may increase their objective values without decreasing the objective value of any level. The result from such a system may be economically inadmissible. If the decision makers of the two levels are willing to find an efficient compromise solution, we propose a solution procedure which can generate effcient solutions, without finding the optimal solution in advance. When the near-optimal solution of the BLP problem is used as the reference point for finding the efficient solution, the result can be easily found during the decision process.     

The application of optimal control methodology to nonlinear programming problems

Dynamic programming techniques have proven to be more successful than alternative nonlinear programming algorithms for solving many discrete-time optimal control problems. The reason for this is that, because of the stagewise decomposition which characterizes dynamic programming, the computational burden grows approximately linearly with the numbern of decision times, whereas the burden for other methods tends to grow faster (e.g.,n ³ for Newton's method). The idea motivating the present study is that the advantages of dynamic programming can be brought to bear on classical nonlinear programming problems if only they can somehow be rephrased as optimal control problems.As shown herein, it is indeed the case that many prominent problems in the nonlinear programming literature can be viewed as optimal control problems, and for these problems, modern dynamic programming methodology is competitive with respect to processing time. The mechanism behind this success is that such methodology achieves quadratic convergence without requiring solution of large systems of linear equations.     

Comments on properties of the minmax solutions in goal programming

This note discusses the properties of solutions generated by the minmax models of goal programming (GP) and compromise programming (CP). GP approaches use a certain target point in the criterion (attribute) space to model decision maker's preferences. When the ideal (utopia) point is used as the target, the minmax GP model coincides with the minmax (Chebyshev) CP model. In a recent review of the current GP state-of-the-art, there have been included suggestions that the two equivalent models ensure Pareto efficiency of solutions and they guarantee a perfectly balanced allocation among the achievement of the individual targets. In this note, it is shown that the models, in general, do not ensure the efficiency of solutions and they do not guarantee the perfect equity among the individual achievements. Moreover, there are given sufficient and necessary conditions clarifying when the discussed properties of minmax solutions do occur.     

<Emphasis Type="Italic">K</Emphasis>-Sum Linear Programming

In this note we introduce the k-sum linear programming problem (KLP) which subsumes the classical linear programming problem and the minmax linear programming problem. KLP can be transformed into a linear program with an exponential number of additional constraints and one additional variable. Exploiting the special structure of these additional constraints, we show that KLP can be solved in polynomial time. Two promising simplex-based algorithms are also suggested to solve KLP.     

An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem

The well-known Shortest Path problem (SP) consists in finding a shortest path from a source to a destination such that the total cost is minimized. The SP models practical and theoretical problems. However, several shortest path applications rely on uncertain data. The Robust Shortest Path problem (RSP) is a generalization of SP. In the former, the cost of each arc is defined by an interval of possible values for the arc cost. The objective is to minimize the maximum relative regret of the path from the source to the destination. This problem is known as the minmax relative regret RSP and it is NP-Hard. We propose a mixed integer linear programming formulation for this problem. The CPLEX branch-and-bound algorithm based on this formulation is able to find optimal solutions for all instances with 100 nodes, and has an average gap of 17 % on the instances with up to 1,500 nodes. We also develop heuristics with emphasis on providing efficient and scalable methods for solving large instances for the minmax relative regret RSP, based on Pilot method and random-key genetic algorithms. To the best of our knowledge, this is the first work to propose a linear formulation, an exact algorithm and metaheuristics for the minmax relative regret RSP.     

Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming

Decomposition has proved to be one of the more effective tools for the solution of large-scale problems, especially those arising in stochastic programming. A decomposition method with wide applicability is Benders' decomposition, which has been applied to both stochastic programming as well as integer programming problems. However, this method of decomposition relies on convexity of the value function of linear programming subproblems. This paper is devoted to a class of problems in which the second-stage subproblem(s) may impose integer restrictions on some variables. The value function of such integer subproblem(s) is not convex, and new approaches must be designed. In this paper, we discuss alternative decomposition methods in which the second-stage integer subproblems are solved using branch-and-cut methods. One of the main advantages of our decomposition scheme is that Stochastic Mixed-Integer Programming (SMIP) problems can be solved by dividing a large problem into smaller MIP subproblems that can be solved in parallel. This paper lays the foundation for such decomposition methods for two-stage stochastic mixed-integer programs.     

Error bounds for the aggregated convex programming problem

Applied mathematical programming problems are often approximations of larger, more detailed problems. One criterion to evaluate an approximating program is the magnitude of the difference between the optimal objective values of the original and the approximating program. The approximation we consider is variable aggregation in a convex program. Bounds are derived on the difference between the two optimal objective values. Previous results of Geoffrion and Zipkin are obtained by specializing our results to linear programming. Also, we apply our bounds to a convex transportation problem. Thanks are due to Ron Dembo, Paul Zipkin and the referees for valuable comments. This research was supported by NSF Grant ENG-76-15599.     

Optimization Techniques for State-Constrained Control and Obstacle Problems

The design of control laws for systems subject to complex state constraints still presents a significant challenge. This paper explores a dynamic programming approach to a specific class of such problems, that of reachability under state constraints. The problems are formulated in terms of nonstandard minmax and maxmin cost functionals, and the corresponding value functions are given in terms of Hamilton-Jacobi-Bellman (HJB) equations or variational inequalities. The solution of these relations is complicated in general; however, for linear systems, the value functions may be described also in terms of duality relations of convex analysis and minmax theory. Consequently, solution techniques specific to systems with a linear structure may be designed independently of HJB theory. These techniques are illustrated through two examples.The first author was supported by the Russian Foundation for Basic Research, Grant 03-01-00663, by the program Universities of Russia, Grant 03.03.007, and by the program of the Russian Federation President for the support of scientific research in leading scientific schools, Grant NSh-1889.2003.1.The second author was supported by the National Science and Engineering Research Council of Canada and by ONR MURI Contract 79846-23800-44-NDSAS.The third and first authors were supported by NSF Grants ECS-0099824 and ECS-0424445.Communicated by G. Leitmann     

Optimality in transient markov chains and linear programming

It is shown how a discrete Markov programming problem can be transformed, using a linear program, into an equivalent problem from which the optimal decision rule can be trivially deduced. This transformation is applied to problems which have either transient probabilities or discounted costs.This research was supported by the National Research Council of Canada, Grant A7751.     

A simplex algorithm for piecewise-linear programming I: Derivation and proof

The simplex method for linear programming can be extended to permit the minimization of any convex separable piecewise-linear objective, subject to linear constraints. This three-part paper develops and analyzes a general, computationally practical simplex algorithm for piecewiselinear programming.Part I derives and justifies the essential steps of the algorithm, by extension from the simplex method for linear programming in bounded variables. The proof employs familiar finite-termination arguments and established piecewise-linear duality theory.Part II considers the relaxation of technical assumptions pertaining to finiteness, feasibility and nondegeneracy of piecewise-linear programs. Degeneracy is found to have broader consequences than in the linear case, and the standard techniques for prevention of cycling are extended accordingly.Part III analyzes the computational requirements of piecewise-linear programming. The direct approach embodied in the piecewise-linear simplex algorithm is shown to be inherently more efficient than indirect approaches that rely on transformation of piecewise-linear programs to equivalent linear programs. A concluding section surveys the many applications of piecewise-linear programming in linear programming,l ₁ estimation, goal programming, interval programming, and nonlinear optimization.This research has been supported in part by the National Science Foundation under grant MCS-8217261.     

A bump triangular dynamic factorization algorithm for the simplex method

A dynamic factorization algorithm is developed which algebraically partitions the basis inverse in such a manner so that the simplex method can be executed from a series of small inverses and the basis itself. This partition is maintained dynamically so that the additional memory required to represent the basis inverse reduces to this series of small inverses for in-core implementations.The algorithm is intended for use in solving general large-scale linear programming problems. This new method of basis representation should permit rather large problems to be solved completely in-core.Preliminary computational experience is presented and comparisons are made with Reid's sparsity-exploiting variant of the Bartels—Golub decomposition for linear programming bases. The computational experience indicated that a significant reduction in memory requirements can usually be obtained using the dynamic factorization approach with only a slight (up to about 20%) degradation of execution time.This research was supported in part by the Air Force Office of Scientific Research, Air Force System Command, USAF, under AFOSR Contract/Grant Number AFOSR-74-2715.     

An inexact approach to solving linear semi-infinite programming problems

In this paper, we propose an “inexact solution” approach to deal with linear semi-infinite programming problems with finitely many variables and infinitely many constraints over a compact metric space. A general convergence proof with some numerical examples are given and the advantages of using this approach are discussed     

The reformulation of two mixed integer programming problems

Two practical problems are described, each of which can be formulated in more than one way as a mixed integer programming problem. The computational experience with two formulations of each problem is given. It is pointed out how in each case a reformulation results in the associated linear programming problem being more constrained. As a result the reformulated mixed integer problem is easier to solve. The problems are a multi-period blending problem and a mining investment problem.     

背包问题的两阶段动态规划算法

本文通过理论分析给出了背包问题的两阶段动态规划算法，用例题说明了其求解过程。在计算机上运用本文所述算法和背包问题的动态规划算法求解了大量例题。解题实践说明，对于大中型背包问题，两阶段动态规划算法由于只要求对少量变量进行排序而使解题时间大为缩短，是一种值得推荐的算法。     

Transient policies in discrete dynamic programming: Linear programming including suboptimality tests and additional constraints

This paper investigates the computation of transient-optimal policies in discrete dynamic programming. The model, is quite general: it may contain transient as well as nontransient policies. and the transition matrices are not necessarily substochastic. A functional equation for the so-called transient-value-vector is derived and the concept of superharmonicity is introduced. This concept provides the linear program to compute the transientvalue-vector and a transient-optimal policy. We also discuss the elimination of suboptimal actions, the solution of problems with additional constraints, and the computation of an efficient policy for a multiple objective dynamic programming problem.     

An algorithm for computing equilibria in a linear monetary economy

An algorithm is presented for computing equilibria in a linear monetary economy, that is, an exchange economy in which all individuals have linear utility functions and in which goods are bought and sold only in exchange for money. The algorithm computes the equilibrium prices by solving a finite sequence of linear programming problems.     

An MPEC approach to second-best toll pricing

This paper addresses two second-best toll pricing problems, one with fixed and the other with elastic travel demands, as mathematical programs with equilibrium constraints. Several equivalent nonlinear programming formulations for the two problems are discussed. One formulation leads to properties that are of interest to transportation economists. Another produces an algorithm that is capable of solving large problems and easy to implement with existing software for linear and nonlinear programming problems. Numerical results using transportation networks from the literature are also presented.This research was partially supported by NSF grants DMI-9978642 and DMI-0300316.