Computing the Pareto frontier of a bi-objective bi-level linear problem using a multiobjective mixed-integer programming algorithm

In this article, we study the bi-level linear programming problem with multiple objective functions on the upper level (with particular focus on the bi-objective case) and a single objective function on the lower level. We have restricted our attention to this type of problem because the consideration of several objectives at the lower level raises additional issues for the bi-level decision process resulting from the difficulty of anticipating a decision from the lower level decision maker. We examine some properties of the problem and propose a methodological approach based on the reformulation of the problem as a multiobjective mixed 0–1 linear programming problem. The basic idea consists in applying a reference point algorithm that has been originally developed as an interactive procedure for multiobjective mixed-integer programming. This approach further enables characterization of the whole Pareto frontier in the bi-objective case. Two illustrative numerical examples are included to show the viability of the proposed methodology.     

Designing a majorization scheme for the recourse function in two-stage stochastic linear programming

We discuss issues pertaining to the domination from above of the second-stage recourse function of a stochastic linear program and we present a scheme to majorize this function using a simpler sublinear function. This majorization is constructed using special geometrical attributes of the recourse function. The result is a proper, simplicial function with a simple characterization which is well-suited for calculations of its expectation as required in the computation of stochastic programs. Experiments indicate that the majorizing function is well-behaved and stable.     

A finite algorithm for the least two-norm solution of a linear program 1

By perturbing properly a linear program to a separable quadratic program it is possible to solve the latter in its dual variable space by iterative techniques such as sparsity-preserving SOR (successive overtaxation techniques). In this way large sparse linear programs can be handled.

In this paper we give a new computational criterion to check whether the solution of the perturbed quadratic program provides the least 2-norm solution of the original linear program. This criterion improves on the criterion proposed in an earlier paper.

We also describe an algorithm for solving linear programs which is based on the SOR methods. The main property of this algorithm is that, under mild assumptions, it finds the least 2-norm solution of a linear program in a finite number of iteration.s     

Global Maximization of a Generalized Concave Multiplicative Function

This article presents a branch-and-bound algorithm for globally solving the problem (P) of maximizing a generalized concave multiplicative function over a compact convex set. Since problem (P) does not seem to have been studied previously, the algorithm is apparently the first algorithm to be proposed for solving this problem. It works by globally solving a problem (P1) equivalent to problem (P). The branch-and-bound search undertaken by the algorithm uses rectangular partitioning and takes place in a space which typically has a much smaller dimension than the space to which the decision variables of problem (P) belong. Convergence of the algorithm is shown; computational considerations and benefits for users of the algorithm are given. A sample problem is also solved.     

Posynomial geometric programming as a special case of semi-infinite linear programming

This paper develops a wholly linear formulation of the posynomial geometric programming problem. It is shown that the primal geometric programming problem is equivalent to a semi-infinite linear program, and the dual problem is equivalent to a generalized linear program. Furthermore, the duality results that are available for the traditionally defined primal-dual pair are readily obtained from the duality theory for semi-infinite linear programs. It is also shown that two efficient algorithms (one primal based and the other dual based) for geometric programming actually operate on the semi-infinite linear program and its dual.     

A new result in the theory and computation of the least-norm solution of a linear program

By perturbing properly a linear program to a separable quadratic program, it is possible to solve the latter in its dual variable space by iterative techniques such as sparsity-preserving SOR (successive overrelaxation) algorithms. The main result of this paper gives an effective computational criterion to check whether the solutions of the perturbed quadratic programs provide the least-norm solution of the original linear program.This research was sponsored by the United States Army under Contract No. DAAG29-80-C-0041. This material is based upon work supported by the National Science Foundation, Grant Nos. DCR-84-20963 and DMS-82-109050, and by the Italian National Research Council (CNR).The author wishes to thank Professor O. L. Mangasarian for his helpful comments which helped to improve the paper.     

DC programming techniques for solving a class of nonlinear bilevel programs

We propose a method for finding a global solution of a class of nonlinear bilevel programs, in which the objective function in the first level is a DC function, and the second level consists of finding a Karush-Kuhn-Tucker point of a quadratic programming problem. This method is a combination of the local algorithm DCA in DC programming with a branch and bound scheme well known in discrete and global optimization. Computational results on a class of quadratic bilevel programs are reported.     

A New Semidefinite Programming Bound for Indefinite Quadratic Forms Over a Simplex

The paper describes a method for computing a lower bound of the global minimum of an indefinite quadratic form over a simplex. The bound is derived by computing an underestimator of the convex envelope by solving a semidefinite program (SDP). This results in a convex quadratic program (QP). It is shown that the optimal value of the QP is a lower bound of the optimal value of the original problem. Since there exist fast (polynomial time) algorithms for solving SDP's and QP's the bound can be computed in reasonable time. Numerical experiments indicate that the relative error of the bound is about 10 percent for problems up to 20 variables, which is much better than a known SDP bound.     

An algorithm for a singly constrained class of quadratic programs subject to upper and lower bounds

This paper gives an O(n) algorithm for a singly constrained convex quadratic program using binary search to solve the Kuhn-Tucker system. Computational results indicate that a randomized version of this algorithm runs in expected linear time and is suitable for practical applications. For the nonconvex case an-approximate algorithm is proposed which is based on convex and piecewise linear approximations of the objective function.     

Modelling a product-mix determination problem

This study presents a combined linear programming package and a user-oriented program for its data input employed in product-mix determination. An optimal product-mix is to be determined for a rapidly changing manufacturing environment. The study consists of developing an interactive computer program for the solution of a product-mix problem. The user-oriented program has been developed so that a person familiar with the plant can determine the ‘best’ mix which should be produced. This study provides a quantitative tool to aid in the decision-making process when time is limited and the production process dynamic.     

An equivalent subproblem relaxation for improving the solution of a class of transportation scheduling problems

In this paper an algorithm is presented for determining the K best paths that may contain cycles in a directed network.The basic idea behind the algorithm is quite simple. Once the best path has been determined it is excluded from the network in such a way that no new path is formed and no more paths are excluded. This step leads to an enlarged network where all the paths, but the best one, can be determined. The method is repeated until the desired paths have been computed.The proposed algorithm can be used not only for the classical K shortest paths problem but also for ranking paths under a nonlinear objective function, provided that an algorithm to determine the best path exists.Computational results are presented and comparisons with other approaches for the classical problem are made.     

Asymptotic behavior of the central path for a special class of degenerate SDP problems

This paper studies the asymptotic behavior of the central path (X(ν),S(ν),y(ν)) as ν↓0 for a class of degenerate semidefinite programming (SDP) problems, namely those that do not have strictly complementary primal-dual optimal solutions and whose “degenerate diagonal blocks” of the central path are assumed to satisfy We establish the convergence of the central path towards a primal-dual optimal solution, which is characterized as being the unique optimal solution of a certain log-barrier problem. A characterization of the class of SDP problems which satisfy our assumptions are also provided. It is shown that the re-parametrization t>0→(X(t⁴),S(t⁴),y(t⁴)) of the central path is analytic at t=0. The limiting behavior of the derivative of the central path is also investigated and it is shown that the order of convergence of the central path towards its limit point is Finally, we apply our results to the convex quadratically constrained convex programming (CQCCP) problem and characterize the class of CQCCP problems which can be formulated as SDPs satisfying the assumptions of this paper. In particular, we show that CQCCP problems with either a strictly convex objective function or at least one strictly convex constraint function lie in this class.This author was supported in part by CAPES and PRONEX-Otimização (FAPERJ/CNPq).This author was supported in part by FUNAPE/UFG, CAPES, PADCT-CNPq and PRONEX-Otimização (FAPERJ/CNPq).This author was supported in part by NSF Grants CCR-9902010, CCR-0203113 and INT-9910084 and ONR grant N00014-03-1-0401.Mathematics Subject Classification (1991): 90C20, 90C22, 90C25, 90C30, 90C33, 90C45, 90C51     

Minimizing the sum of a linear and a linear fractional function applying conic quadratic representation: continuous and discrete problems

This paper tries to minimize the sum of a linear and a linear fractional function over a closed convex set defined by some linear and conic quadratic constraints. At first, we represent some necessary and sufficient conditions for the pseudoconvexity of the problem. For each of the conditions, under some reasonable assumptions, an appropriate second-order cone programming (SOCP) reformulation of the problem is stated and a new applicable solution procedure is proposed. Efficiency of the proposed reformulations is demonstrated by numerical experiments. Secondly, we limit our attention to binary variables and derive a sufficient condition for SOCP representability. Using the experimental results on random instances, we show that the proposed conic reformulation is more efficient in comparison with the well-known linearization technique and it produces more eligible cuts for the branch and bound algorithm.     

The fleet assignment problem: Solving a large-scale integer program

Given a flight schedule and set of aircraft, the fleet assignment problem is to determine which type of aircraft should fly each flight segment. This paper describes a basic daily, domestic fleet assignment problem and then presents chronologically the steps taken to solve it efficiently. Our model of the fleet assignment problem is a large multi-commodity flow problem with side constraints defined on a time-expanded network. These problems are often severely degenerate, which leads to poor performance of standard linear programming techniques. Also, the large number of integer variables can make finding optimal integer solutions difficult and time-consuming. The methods used to attack this problem include an interior-point algorithm, dual steepest edge simplex, cost perturbation, model aggregation, branching on set-partitioning constraints and prioritizing the order of branching. The computational results show that the algorithm finds solutions with a maximum optimality gap of 0.02% and is more than two orders of magnitude faster than using default options of a standard LP-based branch-and-bound code.This work was supported by NSF and AFORS grant DDM-9115768 and NSF grant SES-9122674.Corresponding author.     

Optimality and Duality for a Class of Nondifferentiable Multiobjective Fractional Programming Problems

In this paper, we consider a class of nondifferentiable multiobjective fractional programs in which each component of the objective function contains a term involving the support function of a compact convex set. We establish necessary and sufficient optimality conditions and duality results for weakly efficient solutions of nondifferentiable multiobjective fractional programming problems. This work was supported by Grant R01-2003-000-10825-0 from the Basic Research Program of KOSEF.     

Stochastic semidefinite programming: a new paradigm for stochastic optimization

Semidefinite programs are a class of optimization problems that have been studied extensively during the past 15 years. Semidefinite programs are naturally related to linear programs, and both are defined using deterministic data. Stochastic programs were introduced in the 1950s as a paradigm for dealing with uncertainty in data defining linear programs. In this paper, we introduce stochastic semidefinite programs as a paradigm for dealing with uncertainty in data defining semidefinite programs.The work of this author was supported in part by the U.S. Army Research Office under Grant DAAD 19-00-1-0465. The material in this paper is part of the doctoral dissertation of this author in preparation at Washington State University.     

Analyzing the potential of a firm: an operations research approach

An approach to analyzing the potential of a firm, which is understood as the firm's ability to provide goods or (and) services to be supplied to a marketplace under restrictions imposed by a business environment in which the firm functions, is proposed. The approach is based on using linear inequalities and, generally, mixed variables in modelling this ability for a broad spectrum of industrial, transportation, agricultural, and other types of firms and allows one to formulate problems of analyzing the potential of a firm as linear programming problems or mixed programming problems with linear constraints. This approach generalizes the one proposed by the author earlier for a more narrow class of models and allows one to effectively employ a widely available software for solving practical problems of the considered kind, especially for firms described by large scale models of mathematical programming.     

On a posterior evaluation of a simple greedy method for set packing

We consider an approach for ex post evaluation of approximate solutions obtained by a well known simple greedy method for set packing. A performance bound is derived that is a function of the highest average reward per item over subsets as well as the number of allocated subsets and ground items. This a posterior bound can enable much revelation of optimality when the solution is near optimal. One of the advantages of the ex post analysis is that it does not require computing the optimal solution to the LP relaxation. The ex post bound will not be guaranteed to reveal substantial levels of optimality for all problem instances but can be a useful tool that is complementary to other traditional methods for ex post evaluation for the set packing problem.     

Capacity Planning Model for a Multipurpose Water Reservoir with Target-Priority Operation

We consider the capacity determination problem of a hydro reservoir. The reservoir is to be used primarily for hydropower generation; however, commitments on release targets for irrigation as well as mitigation of downstream flood hazards are also secondary objectives. This paper is concerned with studying the complex interaction among various system reliabilities (power, flood, irrigation, etc.) and to provide decision makers a planning tool for further investigation. The main tool is an optimization model that recognizes the randomness in streamflow. The model incorporates a special target-priority policy according to given system reliabilities. Optimized values are then used in a simulation model to investigate the system behavior. Detailed computational results are provided.     

Optimal control of a dam under seasonal electricity prices

This study concerns the optimal control of a hydroelectric dam under seasonal electricity prices: high in winter, low in summer. The goal is to maximize the expected discounted infinite-horizon return through a policy that determines the amount of electricity to be produced in each time period, depending on the water level at the beginning of the period under consideration. The prices are assumed to be deterministic, and the flows into the reservoir are seasonal, stochastic, but independent from one period to another. The electric power generated is proportional to the amount of water flow through the turbines. There exist seepage and evaporation losses.It is shown that in the simplest price structure, the optimal policy is entirely determined by a single critical water level in each period of time, at which one starts producing. An example shows that the discretization of the reservoir levels can destroy this property. A method is proposed to avoid this difficulty. Another way of defining a policy is through goal-levels. This approach is shown to give higher returns than the standard approach.