An incremental and parametrical algorithm for convex-concave fractional programming with a single constraint

A problem of the maximization of the ratio of a concave function to a convex function is considered, subject to an upper bound on a single convex constraint function; all these functions are assumed to be differentiable. An incremental algorithm is defined, which solves the problem parametrically for different values of the constraint function by the solution of a set of ordinary first order differential equations. If K is the number of variables in the problem and B(K) is an upper bound—dependent of K —of the time needed to evaluate any function value or any first or second order derivative, the complexity of the algorithm is of the order O[(B(K)K + K)a], where a is the number of integration steps applied in the solution of the differential equations. In particular, a cost-effectiveness resource allocation problem with separable functions is solved numerically in a time of the order O[Ka] if B(K) is independent of K; an example of such a problem is given with analytically solvable differential equations.     

Mixed duality without a constraint qualification for minimax fractional programming

Without the need of a constraint qualification, we establish the necessary and sufficient optimality conditions for minimax fractional programming. Using these optimality conditions, we construct a mixed dual model which unifies the Mond–Weir dual, Wolfe dual and a parameter dual models. Several duality theorems are established. Consequently, this article partly solves the problem posed by Lai et al. [H.C. Lai, J.C. Liu and K. Tanaka (1999). Duality without a constraint qualification for minimax fractional programming. Journal of Optimization Theory and Applications, 101, 109–125.].     

Convex programming with single separable constraint and bounded variables

In this paper a minimization problem with convex objective function subject to a separable convex inequality constraint “≤” and bounded variables (box constraints) is considered. We propose an iterative algorithm for solving this problem based on line search and convergence of this algorithm is proved. At each iteration, a separable convex programming problem with the same constraint set is solved using Karush-Kuhn-Tucker conditions. Convex minimization problems subject to linear equality/ linear inequality “≥” constraint and bounds on the variables are also considered. Numerical illustration is included in support of theory.     

Multiparametric sensitivity analysis of the constraint matrix in linear-plus-linear fractional programming problem

In this paper, we study multiparametric sensitivity analysis for programming problems with linear-plus-linear fractional objective function using the concept of maximum volume in the tolerance region. We construct critical regions for simultaneous and independent perturbations of one row or one column of the constraint matrix in the given problem. Necessary and sufficient conditions are given to classify perturbation parameters as ‘focal’ and ‘nonfocal’. Nonfocal parameters can have unlimited variations, because of their low sensitivity in practice, these parameters can be deleted from the analysis. For focal parameters, a maximum volume tolerance region is characterized. Theoretical results are illustrated with the help of a numerical example.     

Resource constraint scheduling with a fractional shared resource

We consider a scheduling problem motivated by mining in remote off-grid areas. In this model, mines have pre-assigned mineral processing jobs and their own machine for executing these jobs. Each job also needs a certain amount of electricity in order to get completed. The electricity, on the other hand, is of limited supply and must be shared between the mines. We present a mathematical formulation of the problem and a Lagrangian relaxation based heuristic. Computational results which compares our heuristic with genetic algorithm and simulated annealing are also presented.     

Duality and solutions for quadratic programming over single non-homogeneous quadratic constraint

This paper extends and completes the discussion by Xing et?al. (Canonical dual solutions to the quadratic programming over a quadratic constraint, submitted) about the quadratic programming over one quadratic constraint (QP1QC). In particular, we relax the assumption to cover more general cases when the two matrices from the objective and the constraint functions can be simultaneously diagonalizable via congruence. Under such an assumption, the nonconvex (QP1QC) problem can be solved through a dual approach with no duality gap. This is unusual for general nonconvex programming but we can explain by showing that (QP1QC) is indeed equivalent to a linearly constrained convex problem, which happens to be dual of the dual of itself. Another type of hidden convexity can be also found in the boundarification technique developed in Xing et?al. (Canonical dual solutions to the quadratic programming over a quadratic constraint, submitted).     

Bibliography in fractional programming

A bibliography in fractional programming is provided which contains 551 references. It was attempted to include all publications in this area of nonlinear programming as they have appeared in more than 45 years now.

---

Zusammenfassung Es wird eine Bibliographie zur Quotientenprogrammierung veröffentlicht, die 551 Titel enthält. Es wurde versucht, alle Beiträge zu diesem Gebiet der nichtlinearen Programmierung zu berücksichtigen, das nun seit mehr als 45 Jahren erforscht wird.

---

---

This research was supported by an earlier grant of Deutsche Forschungsgemeinschaft (West Germany), by Grant No. 4534 of Natural Sciences and Engineering Research Council (NSERC) and by the J.D. Muir Fund of the Faculty of Business, University of Alberta.     

Goal programming with linear fractional criteria

In this paper we present an extension of goal programming to include linear fractional criteria. The extension forms a natural link between goal programming (GP) and multiple objective linear fractional programming (MOLFP).     

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.     

On a fractional sublinear elliptic equation with a variable coefficient

We study the existence and uniqueness of bounded weak solutions to a fractional sublinear elliptic equation with a variable coefficient, in the whole space. Existence is investigated in connection to a certain fractional linear equation, whereas the proof of uniqueness relies on uniqueness of weak solutions to an associated fractional porous medium equation with variable density.     

Combining metaheuristics with mathematical programming, constraint programming and machine learning

During the last years, interest on hybrid metaheuristics has risen considerably in the field of optimization and machine learning. The best results found for many optimization problems in science and industry are obtained by hybrid optimization algorithms. Combinations of optimization tools such as metaheuristics, mathematical programming, constraint programming and machine learning, have provided very efficient optimization algorithms. Four different types of combinations are considered in this paper: (i) Combining metaheuristics with complementary metaheuristics. (ii) Combining metaheuristics with exact methods from mathematical programming approaches which are mostly used in the operations research community. (iii) Combining metaheuristics with constraint programming approaches developed in the artificial intelligence community. (iv) Combining metaheuristics with machine learning and data mining techniques.     

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.     

Combining metaheuristics with mathematical programming,constraint programming and machine learning

We consider the problem of creating fair course timetables in the setting of a university. The central idea is that undesirable arrangements in the course timetable, i.e., violations of soft constraints, should be distributed in a fair way among the stakeholders. We propose and discuss in detail two fair versions of the popular curriculum-based course timetabling (CB-CTT) problem, the MMF-CB-CTT problem and the JFI-CB-CTT problem, which are based on max–min fairness (MMF) and Jain’s fairness index (JFI), respectively. For solving the MMF-CB-CTT problem, we present and experimentally evaluate an optimization algorithm based on simulated annealing. We introduce three different energy difference measures and evaluate their impact on the overall algorithm performance. The proposed algorithm improves the fairness on 20 out of 32 standard instances compared to the known best timetables. The JFI-CB-CTT problem formulation focuses on the trade-off between fairness and the aggregated soft constraint violations. Here, our experimental evaluation shows that the known best solutions to 32 CB-CTT standard instances are quite fair with respect to JFI. Our experiments show that the fairness can often be improved at the cost of only a small increase in the overall amount of penalty.     

A well posed conservation law with a variable unilateral constraint

This paper considers the Cauchy problem for a conservation law with a variable unilateral constraint, its motivation being, for instance, the modeling of a toll gate along a highway. This problem is solved by means of nonclassical shocks and its well posedness is proved. Then, the solutions so obtained are shown to coincide with the limits of the classical solutions to suitable conservation laws with discontinuous flux function that approximate the constrained problem.     

Duality in nonlinear fractional programming

Summary The purpose of the present paper is to introduce, on the lines similar to that ofWolfe [1961], a dual program to a nonlinear fractional program in which the objective function, being the ratio of a convex function to a strictly positive linear function, is a special type of pseudo-convex function and the constraint set is a convex set constrained by convex functions in the form of inequalities. The main results proved are, (i) Weak duality theorem, (ii)Wolfe's (Direct) duality theorem and (iii)Mangasarian's Strict Converse duality theorem.Huard's [1963] andHanson's [1961] converse duality theorems for the present problem have just been stated because they can be obtained as a special case ofMangasarian's theorem [1969, p. 157]. The other important discussion included is to show that the dual program introduced in the present paper can also be obtained throughDinkelbach's Parametric Replacement [1967] of a nonlinear fractional program. Lastly, duality in convex programming is shown to be a special case of the present problem.The present research is partially supported by National Research Council of Canada.     

A procedure for parameterizing a constraint in linear programming

A post-optimal procedure for parameterizing a constraint in linear programming is proposed. In the derivation of the procedure, the technique of pivotal operations (Jordan eliminations) is applied. The procedure is compared to another by Orchard-Hays [2], and a numerical example of the procedure is provided.     

Optimality conditions in fractional programming

Optimality conditions of Kuhn-Tucker and Fritz John, with and without differentiability requirements, are established for a nonlinear fractional programming problem. The transformation introduced by Manas and Schaible plays a key role.     

Integrating operations research in constraint programming

This paper presents constraint programming (CP) as a natural formalism for modelling problems, and as a flexible platform for solving them. CP has a range of techniques for handling constraints including several forms of propagation and tailored algorithms for global constraints. It also allows linear programming to be combined with propagation and novel and varied search techniques which can be easily expressed in CP. The paper describes how CP can be used to exploit linear programming within different kinds of hybrid algorithm. In particular it can enhance techniques such as Lagrangian relaxation, Benders decomposition and column generation.