Duality in fractional programming

This paper develops theoretical and computational aspects of the dual problem in linear fractional programming. This is done on the basis of two alternative methods for solving the primal fractional programming problem, both of which were presented in earlier literature. Parametric changes in the resource-vector are considered, and attention is given to infinitesimal as well as to discrete changes.     

Optimal set partitioning,matchings and lagrangian duality

We formulate the set partitioning problem as a matching problem with simple side constraints. As a result we obtain a Lagrangian relaxation of the set partitioning problem in which the primal problem is a matching problem. To solve the Lagrangian dual we must solve a sequence of matching problems each with different edge-weights. We use the cyclic coordinate method to iterate the multipliers, which implies that successive matching problems differ in only two edge-weights. This enables us to use sensitivity analysis to modify one optimal matching to obtain the next one. We give theoretical and empirical comparisons of these dual bounds with the conventional linear programming ones.     

An explicit general solution in linear fractional programming

A complete analysis and explicit solution is presented for the problem of linear fractional programming with interval programming constraints whose matrix is of full row rank. The analysis proceeds by simple transformation to canonical form, exploitation of the Farkas-Minkowki lemma and the duality relationships which emerge from the Charnes-Cooper linear programming equivalent for general linear fractional programming. The formulations as well as the proofs and the transformations provided by our general linear fractional programming theory are here employed to provide a substantial simplification for this class of cases. The augmentation developing the explicit solution is presented, for clarity, in an algorithmic format.     

Programming with linear fractional functionals

Charnes and Cooper [1] showed that a linear programming problem with a linear fractional objective function could be solved by solving at most two ordinary linear programming problems. In addition, they showed that where it is known a priori that the denominator of the objective function has a unique sign in the feasible region, only one problem need be solved. In the present note it is shown that if a finite solution to the problem exists, only one linear programming problem must be solved. This is because the denominator cannot have two different signs in the feasible region, except in ways which are not of practical importance.     

Duality in constrained multi‐facility location models

We consider the ??_p‐norm multi‐facility minisum location problem with linear and distance constraints, and develop the Lagrangian dual formulation for this problem. The model that we consider represents the most general location model in which the dual formulation is not found in the literature. We find that, because of its linear objective function and less number of variables, the Lagrangian dual is more useful. Additionally, the dual formulation eliminates the differentiability problem in the primal formulation. We also provide the Lagrangian dual formulation of the multi‐facility minisum location problem with the ??_pb‐norm. Finally, we provide a numerical example for solving the Lagrangian dual formulation and obtaining the optimum facility locations from the solution of the dual formulation. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 410–421, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10010     

Lagrangian relaxation approach to the targeting problem

In this paper, we consider a new weapon–target allocation problem with the objective of minimizing the overall firing cost. The problem is formulated as a nonlinear integer programming model. We applied Lagrangian relaxation and a branch‐and‐bound method to the problem after transforming the nonlinear constraints into linear ones. An efficient primal heuristic is developed to find a feasible solution to the problem to facilitate the procedure. In the branch‐and‐bound method, three different branching rules are considered and the performances are evaluated. Computational results using randomly generated data are presented. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 640–653, 1999     

A linear programming solution to the generalized rectangular distance weber problem

The Weber Problem generalized to the location of several new points with respect to existing points is formulated as a linear programming problem under the assumption that distances are rectangular. The dual problem is then formulated and subsequently reduced to a problem with substantially fewer variables and constraints than required by an existent alternative linear programming formulation. Flows may exist between new as well as between new and existing points. Linear constraints can be imposed to restrict the location of new points. Pairwise constraints limiting distances between new points and between new and existing points can also be accommodated.     

A node covering algorithm

This paper describes a node covering algorithm, i.e., a procedure for finding a smallest set of nodes covering all edges of an arbitrary graph. The algorithm is based on the concept of a dual node-clique set, which allows us to identify partial covers associated with integer dual feasible solutions to the linear programming equivalent of the node covering problem. An initial partial cover with the above property is first found by a labeling procedure. Another labeling procedure then successively modifies the dual node-clique set, so that more and more edges are covered, i.e., the (primal) infeasibility of the solution is gradually reduced, while integrality and dual feasibility are preserved. When this cannot be continued, the problem is partitioned and the procedure applied to the resulting subproblems. While the steps of the algorithm correspond to sequences of dual simplex pivots, these are carried out implicitly, by labeling. The procedure is illustrated by examples, and some early computational experience is reported. We conclude with a discussion of potential improvements and extensions.     

A mutual primal-dual linear programming algorithm

A new primal-dual linear programming algorithm is exhibited. A proof is given that optimal solutions to both primal and dual problems (when such solutions exist) are found in a finite number of steps by this algorithm. A numerical example is included to illustrate the method.     

The fractional fixed-charge problem

Fractional fixed-charge problems arise in numerous applications, where the measure of economic performance is the time rate of earnings or profit (equivalent to an interest rate on capital investment). This paper treats the fractional objective function, after suitable transformation, as a linear parametric fixed-charge problem. It is proved, with wider generality than in the case of Hirsch and Dantzig, that some optimal solution to the generalized linear fixed-charge problem is an extreme point of the polyhedral set defined by the constraints. Furthermore, it is shown that the optimum of the generalized fractional fixed-charge problem is also a vertex of this set. The proof utilizes a suitable penalty function yielding an upper bound on the optimal value of the objective function; this is particularly useful when considering combinations of independent transportation-type networks. Finally, it is shown that the solution of a fractional fixed-charge problem is obtainable through that of a certain linear fixed-charge one.     

A primal-dual cutting-plane algorithm for all-integer programming

The integer programming literature contains many algorithms for solving all-integer programming problems but, in general, existing algorithms are less than satisfactory even in solving problems of modest size. In this paper we present a new technique for solving the all-integer, integer programming problem. This algorithm is a hybrid (i.e., primal-dual) cutting-plane method which alternates between a primal-feasible stage related to Young's simplified primal algorithm, and a dual-infeasible stage related to Gomory's dual all-integer algorithm. We present the results of computational testing.     

An algorithm (GIPC2) for solving integer programming problems with separable nonlinear objective functions

This paper presents an algorithm for solving the integer programming problem possessing a separable nonlinear objective function subject to linear constraints. The method is based on a generalization of the Balas implicit enumeration scheme. Computational experience is given for a set of seventeen linear and seventeen nonlinear test problems. The results indicate that the algorithm can solve the nonlinear integer programming problem in roughly the equivalent time required to solve the linear integer programming problem of similar size with existing algorithms. Although the algorithm is specifically designed to solve the nonlinear problem, the results indicate that the algorithm compares favorably with the Branch and Bound algorithm in the solution of linear integer programming problems.     

The conjugate gradient technique for certain quadratic network problems

We consider a class of network flow problems with pure quadratic costs and demonstrate that the conjugate gradient technique is highly effective for large-scale versions. It is shown that finding a saddle point for the Lagrangian of an m constraint, n variable network problem requires only the solution of an unconstrained quadratic programming problem with only m variables. It is demonstrated that the number of iterations for the conjugate gradient algorithm is substantially smaller than the number of variables or constraints in the (primal) network problem. Forty quadratic minimum-cost flow problems of various sizes up to 100 nodes are solved. Solution time for the largest problems (4,950 variables and 99 linear constraints) averaged 4 seconds on the CBC Cyber 70 Model 72 computer.     

Statistical decision analysis of stochastic linear programming problems

This paper presents a statistical decision analysis of a one-stage linear programming problem with deterministic constraints and stochastic criterion function. Procedures for obtaining numerical results are given which are applicable to any problem having this general form. We begin by stating the statistical decision problems to be considered, and then discuss the expected value of perfect information and the expected value of sample information. In obtaining these quantities, use is made of the distribution of the optimal value of the linear programming problem with stochastic criterion function, and so we discuss Monte Carlo and numerical integration procedures for estimating the mean of this distribution. The case in which the random criterion vector has a multivariate Normal distribution is discussed separately, and more detailed methods are offered. We discuss dual problems, including some relationships of this work with other work in probabilistic linear programming. An example is given in Appendix A showing application of the methods to a sample problem. In Appendix B we consider the accuracy of a procedure for approximating the expected value of information.     

An optimal procedure for the coordinated replenishment dynamic lot‐sizing problem with quantity discounts

We consider in this paper the coordinated replenishment dynamic lot‐sizing problem when quantity discounts are offered. In addition to the coordination required due to the presence of major and minor setup costs, a separate element of coordination made possible by the offer of quantity discounts needs to be considered as well. The mathematical programming formulation for the incremental discount version of the extended problem and a tighter reformulation of the problem based on variable redefinition are provided. These then serve as the basis for the development of a primal‐dual based approach that yields a strong lower bound for our problem. This lower bound is then used in a branch and bound scheme to find an optimal solution to the problem. Computational results for this optimal solution procedure are reported in the paper. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 686–695, 2000     

Balancing a one‐way corridor capacity and safety‐oriented reliability: A stochastic optimization approach for metro train timetabling

In urban rail transit systems of large cities, the headway and following distance of successive trains have been compressed as much as possible to enhance the corridor capacity to satisfy extremely high passenger demand during peak hours. To prevent train collisions and ensure the safety of trains, a safe following distance of trains must be maintained. However, this requirement is subject to a series of complex factors, such as the uncertain train braking performance, train communication delay, and driver reaction time. In this paper, we propose a unified mathematical framework to analyze the safety‐oriented reliability of metro train timetables with different corridor capacities, that is, the train traffic density, and determine the most reliable train timetable for metro lines in an uncertain environment. By employing a space‐time network representation in the formulations, the reliability‐based train timetabling problem is formulated as a nonlinear stochastic programming model, in which we use 0‐1 variables to denote the time‐dependent velocity and position of all involved trains. Several reformulation techniques are developed to obtain an equivalent mixed integer programming model with quadratic constraints (MIQCP) that can be solved to optimality by some commercial solvers. To improve the computational efficiency of the MIQCP model, we develop a dual decomposition solution framework that decomposes the primal problem into several sets of subproblems by dualizing the coupling constraints across different samples. An exact dynamic programming combined with search space reduction strategies is also developed to solve the exact optimal solutions of these subproblems. Two sets of numerical experiments, which involve a relatively small‐scale case and a real‐world instance based on the operation data of the Beijing subway Changping Line are implemented to verify the effectiveness of the proposed approaches.     

Postoptimality analysis in nonlinear integer programming: The right-hand side case

An algorithm is presented to gain postoptimality data about the family of nonlinear pure integer programming problems in which the objective function and constraints remain the same except for changes in the right-hand side of the constraints. It is possible to solve such families of problems simultaneously to give a global optimum for each problem in the family, with additional problems solved in under 2 CPU seconds. This represents a small fraction of the time necessary to solve each problem individually.     

Minimizing sums and products of linear fractional functions over a polytope

In this paper, we develop efficient deterministic algorithms for globally minimizing the sum and the product of several linear fractional functions over a polytope. We will show that an elaborate implementation of an outer approximation algorithm applied to the master problem generated by a parametric transformation of the objective function serves as an efficient method for calculating global minima of these nonconvex minimization problems if the number of linear fractional terms in the objective function is less than four or five. It will be shown that the Charnes–Cooper transformation plays an essential role in solving these problems. Also a simple bounding technique using linear multiplicative programming techniques has remarkable effects on structured problems. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 583–596, 1999     

Mathematical control theory solution of an interactive accounting flows model

In this paper we have applied the mathematical control theory to the accounting network flows, where the flow rates are constrained by linear inequalities. The optimal control policy is of the “generalized bang-bang” variety which is obtained by solving at each instant in time a linear programming problem whose objective function parameters are determined by the “switching function” which is derived from the Hamiltonian function. The interpretation of the adjoint variables of the control problem and the dual evaluators of the linear programming problem demonstrates an interesting interaction of the cross section phase of the problem, which is characterized by linear programming, and the dynamic phase of the problem, which is characterized by control theory.     

Coordinated replenishments from multiple suppliers with price discounts

In this study we present an integer programming model for determining an optimal inbound consolidation strategy for a purchasing manager who receives items from several suppliers. The model considers multiple suppliers with limited capacity, transportation economies, and quantity discounts. We propose an integrated branch and bound procedure for solving the model. This procedure, applied to a Lagrangean dual at every node of the search tree, combines the subgradient method with a primal heuristic that interact to change the Lagrangean multipliers and tighten the upper and lower bounds. An enhancement to the branch and bound procedure is developed using surrogate constraints, which is found to be beneficial for solving large problems. We report computational results for a variety of problems, with as many as 70,200 variables and 3665 constraints. Computational testing indicates that our procedure is significantly faster than the general purpose integer programming code OSL. A regression analysis is performed to determine the most significant parameters of our model. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 579–598, 1998