Generalized linear multiplicative and fractional programming

This paper addresses itself to the algorithm for minimizing the sum of a convex function and a product of two linear functions over a polytope. It is shown that this nonconvex minimization problem can be solved by solving a sequence of convex programming problems. The basic idea of this algorithm is to embed the original problem into a problem in higher dimension and apply a parametric programming (path following) approach. Also it is shown that the same idea can be applied to a generalized linear fractional programming problem whose objective function is the sum of a convex function and a linear fractional function.     

Generalized fractional programming duality: A parametric approach

Using a parametric approach, duality is presented for a minimax fractional programming problem that involves several ratios in the objective function.The first author is thankful to Natural Science and Engineering Research Council of Canada for financial support through Grant A-5319, and the authors are thankful to the anonymous referees for useful suggestions.     

Generalized linear fractional programming under interval uncertainty

Data in many real-life engineering and economical problems suffer from inexactness. Herein we assume that we are given some intervals in which the data can simultaneously and independently perturb. We consider a generalized linear fractional programming problem with interval data and present an efficient method for computing the range of optimal values. The method reduces the problem to solving from two to four real-valued generalized linear fractional programs, which can be computed in polynomial time using an appropriate interior point method solver.     

Generalized fractional programming and cutting plane algorithms

In this paper, we introduce a variant of a cutting plane algorithm and show that this algorithm reduces to the well-known Dinkelbach-type procedure of Crouzeix, Ferland, and Schaible if the optimization problem is a generalized fractional program. By this observation, an easy geometrical interpretation of one of the most important algorithms in generalized fractional programming is obtained. Moreover, it is shown that the convergence of the Dinkelbach-type procedure is a direct consequence of the properties of this cutting plane method. Finally, a class of generalized fractional programs is considered where the standard positivity assumption on the denominators of the ratios of the objective function has to be imposed explicitly. It is also shown that, when using a Dinkelbach-type approach for this class of programs, the constraints ensuring the positivity on the denominators can be dropped.The authors like to thank the anonymous referees and Frank Plastria for their constructive remarks on an earlier version of this paper.This research was carried out at Erasmus University, Rotterdam, The Netherlands and was supported by JNICT, Lisboa, Portugal, under Contract BD/707/90-RM.     

Bicriteria linear fractional programming

As a step toward the investigation of the multicriteria linear fractional program, this paper provides a thorough analysis of the bicriteria case. It is shown that the set of efficient points is a finite union of linearly constrained sets and the efficient frontier is the image of a finite number of connected line segments of efficient points. A simple algorithm using only one-dimensional parametric linear programming techniques is developed to evaluate the efficient frontier.This research was partially supported by NRC Research Grant No. A4743. The authors wish to thank two anonymous referees for their helpful comments on an earlier draft of this paper.     

Convex programming with set-inclusive constraints and its applications to generalized linear and fractional programming

Duality results are established in convex programming with the set-inclusive constraints studied by Soyster. The recently developed duality theory for generalized linear programs by Thuente is further generalized and also brought into the framework of Soyster's theory. Convex programming with set-inclusive constraints is further extended to fractional programming.     

Strong duality for robust minimax fractional programming problems

We develop a duality theory for minimax fractional programming problems in the face of data uncertainty both in the objective and constraints. Following the framework of robust optimization, we establish strong duality between the robust counterpart of an uncertain minimax convex–concave fractional program, termed as robust minimax fractional program, and the optimistic counterpart of its uncertain conventional dual program, called optimistic dual. In the case of a robust minimax linear fractional program with scenario uncertainty in the numerator of the objective function, we show that the optimistic dual is a simple linear program when the constraint uncertainty is expressed as bounded intervals. We also show that the dual can be reformulated as a second-order cone programming problem when the constraint uncertainty is given by ellipsoids. In these cases, the optimistic dual problems are computationally tractable and their solutions can be validated in polynomial time. We further show that, for robust minimax linear fractional programs with interval uncertainty, the conventional dual of its robust counterpart and the optimistic dual are equivalent.     

Constrained ratio games and generalized fractional programming

A certain constrained ratio game is shown to be equivalent to a pair of mutually dual generalized fractional programming problems. This also extends the concept of symmetric duality to min-max fractional programming.Research by this author was carried out while he was visiting I.I.T. Delhi, India, under an Australian Vice-Chancellors' Committee Visiting Fellowship.     

A compromise procedure for the multiple objective linear fractional programming problem

A generalization of a well-known multiple objective linear fractional programming (MOLFP) problem, the multiple objective fractional programming (MOFP) problem, is formulated. A concept of multiple objective programming (MOP) problem corresponding to MOFP is introduced and some relations between those problems are examined. Based on these results, a compromise procedure for MOLFP problem is proposed. A numerical example is given to show how the procedure works.     

Partial linearization for generalized fractional programming

An algorithm based on partial linearization is proposed to deal with generalized fractional programs. This algorithm is shown to be equivalent to the so called generalized Dinkelbach's algorithm applying to this problem. Hence we have another setting for this last algorithm.This research was supported by NSERC (grant A8312) and FCAR (grant 0899).     

Ranking in integer linear fractional programming problems

An algorithm is developed which ranks the feasible solutions of an integer fractional programming problem in decreasing order of the objective function values.

---

Zusammenfassung Es wird ein Algorithmus angegeben, der die zulässigen Lösungen eines ganzzahligen Quotientenprogrammes nach fallenden Zielfunktionswerten liefert.

     

A linear programming approach to test efficiency in multi-objective linear fractional programming problems

In a multi-objective linear fractional programming problem (MOLFPP), it is often useful to check the efficiency of a given feasible solution, and if the solution is efficient, it is useful to check strong or weak efficiency. In this paper, by applying a geometrical interpretation, a linear programming approach is achieved to test weak efficiency. Also, in order to test strong efficiency for a given weakly efficient point, a linear programming approach is constructed.     

A duality theorem for a homogeneous fractional programming problem

The usual theory of duality for linear fractional programs is extended by replacing the linear functions in the numerator and denominator by arbitrary positively homogeneous convex functions. In the constraints, the positive orthant inR ⁿ is replaced by an arbitrary cone. The resultant duality theorem contains a recent result of Chandra and Gulati as a special case.The authors wish to thank the referee for a number of valuable suggestions, particularly improvements in Theorem 3.4 and Corollary 3.1.     

Weighting method for bi-level linear fractional programming problems

In this paper we consider the solution of a bi-level linear fractional programming problem (BLLFPP) by weighting method. A non-dominated solution set is obtained by this method. In this article decision makers (DMs) provide their preference bounds to the decision variables that is the upper and lower bounds to the decision variables they control. We convert the hierarchical system into scalar optimization problem (SOP) by finding proper weights using the analytic hierarchy process (AHP) so that objective functions of both levels can be combined into one objective function. Here the relative weights represent the relative importance of the objective functions.     

Duality in inexact fractional programming with set-inclusive constraints

This paper extends the fractional programming problem with set-inclusive constraints studied earlier by replacing every coefficient vector in the objective function with a convex set. A dual is formulated, and well-known duality results are established. A numerical example illustrates the dual strategy to obtain the value of the initial problem.The research of the first author was conducted while he was on sabbatical at the Department of Operations Research, Stanford University, Stanford, California. The financial assistance of the International Council for Exchange of Scholars is gratefully acknowledged. The author is grateful to the Department of Operations Research at Stanford for the use of its research facilities.     

Multiobjective fractional programming with generalized convexity

This paper derives several results regarding the optimality conditions and duality properties for the class of multiobjective fractional programs under generalized convexity assumptions. These results are obtained by applying a parametric approach to reduce the problem to a more conventional form.     

Approximation algorithms for combinatorial fractional programming problems

We are concerned with a combinatorial optimization problem which has the ratio of two linear functions as the objective function. This type of problems can be solved by an algorithm that uses an auxiliary problem with a parametrized linear objective function. Because of its combinatorial nature, however, it is often difficult to solve the auxiliary problem exactly. In this paper, we propose an algorithm which assumes that the auxiliary problems are solved only approximately, and prove that it gives an approximate solution to the original problem, of which the accuracy is at least as good as that of approximate solutions to the auxiliary problems. It is also shown that the time complexity is bounded by the square of the computation time of the approximate algorithm for the auxiliary problem. As an example of the proposed algorithm, we present a fully polynomial time approximation scheme for the fractional 0–1 knapsack problem.     

Using duality to solve generalized fractional programming problems

In this paper we explore the relations between the standard dual problem of a convex generalized fractional programming problem and the partial dual problem proposed by Barros et al. (1994). Taking into account the similarities between these dual problems and using basic duality results we propose a new algorithm to directly solve the standard dual of a convex generalized fractional programming problem, and hence the original primal problem, if strong duality holds. This new algorithm works in a similar way as the algorithm proposed in Barros et al. (1994) to solve the partial dual problem. Although the convergence rates of both algorithms are similar, the new algorithm requires slightly more restrictive assumptions to ensure a superlinear convergence rate. An important characteristic of the new algorithm is that it extends to the nonlinear case the Dinkelbach-type algorithm of Crouzeix et al. (1985) applied to the standard dual problem of a generalized linear fractional program. Moreover, the general duality results derived for the nonlinear case, yield an alternative way to derive the standard dual of a generalized linear fractional program. The numerical results, in case of quadratic-linear ratios and linear constraints, show that solving the standard dual via the new algorithm is in most cases more efficient than applying directly the Dinkelbach-type algorithm to the original generalized fractional programming problem. However, the numerical results also indicate that solving the alternative dual (Barros et al., 1994) is in general more efficient than solving the standard dual.This research was carried out at the Econometric Institute, Erasmus University Rotterdam, the Netherlands and was supported by the Tinbergen Institute Rotterdam     

The tolerance approach in multiobjective linear fractional programming

When solving a multiobjective programming problem by the weighted sum approach, weights represent the relative importance associated to the objectives. As these values are usually imprecise, it is important to analyze the sensitivity of the solution under possible deviations on the estimated values. In this sense, the tolerance approach provides a direct measure of how weights may vary simultaneously and independently from their estimated values while still retaining the same efficient solution. This paper provides an explicit expression to the maximum tolerance on weights in a multiobjective linear fractional programming problem when all the denominators are equal. An application is also presented to illustrate how the results may help the decision maker to choose a most satisfactory solution in a production problem.     

NP-hardness of linear multiplicative programming and related problems

The linear multiplicative programming problem minimizes a product of two (positive) variables subject to linear inequality constraints. In this paper, we show NP-hardness of linear multiplicative programming problems and related problems.