Multicriteria integer programming: A (hybrid) dynamic programming recursive approach

Dynamic programming recursive equations are used to develop a procedure to obtain the set of efficient solutions to the multicriteria integer linear programming problem. An alternate method is produced by combining this procedure with branch and bound rules. Computational results are reported.     

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.     

A bound-improving approach to discrete programming problems

This note deals with the extension of the bound-improving sequence idea to general discrete programming problems.Corresponding author.     

A differential equation approach to nonlinear programming

A new method is presented for finding a local optimum of the equality constrained nonlinear programming problem. A nonlinear autonomous system is introduced as the base of the theory instead of usual approaches. The relation between critical points and local optima of the original optimization problem is proved. Asymptotic stability of the critical points is also proved. A numerical algorithm which is capable of finding local optima systematically at the quadratic rate of convergence is developed from a detailed analysis of the nature of trajectories and critical points. Some numerical results are given to show the efficiency of the method.     

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     

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.     

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.     

Constrained integer linear fractional programming problem

An integer linear fractional programming problem, whose integer solution is required to satisfy any h out of given n sets of constraints has been discussed in this paper. Method for ranking and scanning all integer points has also been developed and a numerical illustration is included in support of theory.     

An unconstrained convex programming approach to solving convex quadratic programming problems

In this paper, we derive an unconstrained convex programming approach to solving convex quadratic programming problems in standard form. Related duality theory is established by using two simple inequalities. An ?-optimal solution is obtained by solving an unconstrained dual convex program. A dual-to-primal conversion formula is also provided. Some preliminary computational results of using a curved search method is included     

A polynomial algorithm for integer programming covering problems satisfying the integer round-up property

LetA be a non-negative matrix with integer entries and no zero column. The integer round-up property holds forA if for every integral vectorw the optimum objective value of the generalized covering problem min{1y: yA w, y 0 integer} is obtained by rounding up to the nearest integer the optimum objective value of the corresponding linear program. A polynomial time algorithm is presented that does the following: given any generalized covering problem with constraint matrixA and right hand side vectorw, the algorithm either finds an optimum solution vector for the covering problem or else it reveals that matrixA does not have the integer round-up property.     

Discrete global descent method for discrete global optimization and nonlinear integer programming

A novel method, entitled the discrete global descent method, is developed in this paper to solve discrete global optimization problems and nonlinear integer programming problems. This method moves from one discrete minimizer of the objective function f to another better one at each iteration with the help of an auxiliary function, entitled the discrete global descent function. The discrete global descent function guarantees that its discrete minimizers coincide with the better discrete minimizers of f under some standard assumptions. This property also ensures that a better discrete minimizer of f can be found by some classical local search methods. Numerical experiments on several test problems with up to 100 integer variables and up to 1.38 × 10¹⁰⁴ feasible points have demonstrated the applicability and efficiency of the proposed method.     

Integer programming approach to reactive scheduling in make-to-order manufacturing

New algorithms based on mixed integer programming formulations are proposed for reactive scheduling in a dynamic, make-to-order manufacturing environment. The problem objective is to update a long-term production schedule subject to service level and inventory constraints, whenever the customer orders are modified or new orders arrive. Different rescheduling policies are proposed, from a total reschedule of all remaining and unmodified customer orders to a non-reschedule of all such orders. In addition, a medium restrictive policy is considered for rescheduling only a subset of remaining customer orders awaiting material supplies. Numerical examples modeled after a real-world scheduling/rescheduling of customer orders in the electronics industry are presented and some results of computational experiments are reported.     

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.     

A unified approach to one-parametric general quadratic programming

A method is proposed for finding local minima to the parametric general quadratic programming problem where all the coefficients are linear or polynomial functions of a scalar parameter. The local minimum vector and the local minimum value are determined explicitly as rational functions of the parameter. A numerical example is given.     

A mathematical approach to solve the network reconstruction problem

The reconstruction of biochemical and genetic networks from experimental data is an important challenge in biology and medical basic research. We formalize this problem mathematically and present an exact algorithm for its solution. Our procedure yields either a complete list of all alternative network structures that explain the observed phenomena or proves that no solution exists using the given data set. This work was supported by the German Ministry of Education and Research (BMBF) through the FORSYS initiative.     

A stochastic programming approach to cash management in banking

The treasurer of a bank is responsible for the cash management of several banking activities. In this work, we focus on two of them: cash management in automatic teller machines (ATMs), and in the compensation of credit card transactions. In both cases a decision must be taken according to a future customers demand, which is uncertain. From historical data we can obtain a discrete probability distribution of this demand, which allows the application of stochastic programming techniques. We present stochastic programming models for each problem. Two short-term and one mid-term models are presented for ATMs. The short-term model with fixed costs results in an integer problem which is solved by a fast (i.e. linear running time) algorithm. The short-term model with fixed and staircase costs is solved through its MILP equivalent deterministic formulation. The mid-term model with fixed and staircase costs gives rise to a multi-stage stochastic problem, which is also solved by its MILP deterministic equivalent. The model for compensation of credit card transactions results in a closed form solution. The optimal solutions of those models are the best decisions to be taken by the bank, and provide the basis for a decision support system.     

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

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

A continuous DC programming approach to the strategic supply chain design problem from qualified partner set

We present a new continuous approach based on the DC (difference of convex functions) programming and DC algorithms (DCA) to the problem of supply chain design at the strategic level when production of a new market opportunity has to be launched among a set of qualified partners. A well known formulation of this problem is the mixed integer linear program. In this paper, we reformulate this problem as a DC program by using an exact penalty technique. The proposed algorithm is a combination of DCA and Branch and Bound scheme. It works in a continuous domain but provides mixed integer solutions. Numerical simulations on many empirical data sets show the efficiency of our approach with respect to the standard Branch and Bound algorithm.     

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.