Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints

When vehicle routing problems with additional constraints, such as capacity or time windows, are solved via column generation and branch-and-price, it is common that the pricing subproblem requires the computation of a minimum cost constrained path on a graph with costs on the arcs and prizes on the vertices. A common solution technique for this problem is dynamic programming. In this paper we illustrate how the basic dynamic programming algorithm can be improved by bounded bi-directional search and we experimentally evaluate the effectiveness of the enhancement proposed. We consider as benchmark problems the elementary shortest path problems arising as pricing subproblems in branch-and-price algorithms for the capacitated vehicle routing problem, the vehicle routing problem with distribution and collection and the capacitated vehicle routing problem with time windows.     

New second-order and first-order algorithms for determining optimal control: A differential dynamic programming approach

In this paper, the notion of differential dynamic programming is used to develop new second-order and first-order successive-approximation methods for determining optimal control. The unconstrained, nonlinear control problem is first considered, and a second-order algorithm is developed which has wider application then existing second-variation and second-order algorithms. A new first-order algorithm emerges as a special case of the second-order one. Control inequality constraints are introduced into the problem and a second-order algorithm is devised which is able to solve this constrained problem. It is believed that control constraints have not been handled previously in this way. Again, a first-order algorithm emerges as a special case. The usefulness of the second-order algorithms is illustrated by the computer solution of three control problems. The methods presented in this paper have been extended by the author to solve problems with terminal constraints and implicitly given final time. Details of these procedures are not given in this paper, but the relevant references are cited.     

Dynamic Programming Method for Constrained Discrete-Time Optimal Control

A dynamic programming method is presented for solving constrained, discrete-time, optimal control problems. The method is based on an efficient algorithm for solving the subproblems of sequential quadratic programming. By using an interior-point method to accommodate inequality constraints, a modification of an existing algorithm for equality constrained problems can be used iteratively to solve the subproblems. Two test problems and two application problems are presented. The application examples include a rest-to-rest maneuver of a flexible structure and a constrained brachistochrone problem.     

A compact labeling scheme for series-parallel graphs

A linear time labeling algorithm is presented for series-parallel graphs. The labels enable us to efficiently implement dynamic programming algorithms for sequencing problems with series-parallel precedence constraints. The labeling scheme can also be used to efficiently count and generate the initial sets, terminal sets and independent sets in transitive series-parallel digraphs and to provide a characterization of the maximal independent sets in transitive digraphs.     

Optimal Security Liquidation Algorithms

This paper develops trading strategies for liquidation of a financial security, which maximize the expected return. The problem is formulated as a stochastic programming problem that utilizes the scenario representation of possible returns. Two cases are considered, a case with no constraint on risk and a case when the risk of losses associated with trading strategy is constrained by Conditional Value-at-Risk (CVaR) measure. In the first case, two algorithms are proposed; one is based on linear programming techniques, and the other uses dynamic programming to solve the formulated stochastic program. The third proposed algorithm is obtained by adding the risk constraints to the linear program. The algorithms provide path-dependent strategies, i.e., the fraction of security sold depends upon price sample-path of the security up to the current moment. The performance of the considered approaches is tested using a set of historical sample-paths of prices.     

Efficient Sequential Quadratic Programming Implementations for Equality-Constrained Discrete-Time Optimal Control

Efficient sequential quadratic programming (SQP) implementations are presented for equality-constrained, discrete-time, optimal control problems. The algorithm developed calculates the search direction for the equality-based variant of SQP and is applicable to problems with either fixed or free final time. Problem solutions are obtained by solving iteratively a series of constrained quadratic programs. The number of mathematical operations required for each iteration is proportional to the number of discrete times N. This is contrasted by conventional methods in which this number is proportional to N ³. The algorithm results in quadratic convergence of the iterates under the same conditions as those for SQP and simplifies to an existing dynamic programming approach when there are no constraints and the final time is fixed. A simple test problem and two application problems are presented. The application examples include a satellite dynamics problem and a set of brachistochrone problems involving viscous friction.     

A gaussian upper bound for gaussian multi-stage stochastic linear programs

This paper deals with two-stage and multi-stage stochastic programs in which the right-hand sides of the constraints are Gaussian random variables. Such problems are of interest since the use of Gaussian estimators of random variables is widespread. We introduce algorithms to find upper bounds on the optimal value of two-stage and multi-stage stochastic (minimization) programs with Gaussian right-hand sides. The upper bounds are obtained by solving deterministic mathematical programming problems with dimensions that do not depend on the sample space size. The algorithm for the two-stage problem involves the solution of a deterministic linear program and a simple semidefinite program. The algorithm for the multi-stage problem invovles the solution of a quadratically constrained convex programming problem.     

Dynamic feedback Stackelberg games with non-unique solutions

Stackelberg games, which was originally introduced by Stackelberg, are widely applied in such fields as economics, management, politics and behavioral sciences. Stackelberg games can be modelled as a bi-level optimization problem. There exists an extensive literature about static bi-level optimization problems. However, the studies on dynamic bi-level optimization problems are fairly scarce in spite of the importance in explaining and predicting some phenomena rationally. In this paper, we consider discrete time dynamic Stackelberg games with feedback information. In general, the lower-level strategies are non-unique in practice. For a unique solution, dynamic programming algorithms have been presented with multiple players. We revisit dynamic programming for feedback information dynamic Stackelberg games with non-unique lower-level solution. First, we define some kind of solutions related to the decisions styles. Then, we analyze them, respectively. Moreover, dynamic programming algorithm is successful in solving solve feedback information dynamic Stackelberg games with non-unique lower-level solutions.     

Lower Bounds from State Space Relaxations for Concave Cost Network Flow Problems

In this paper we obtain Lower Bounds (LBs) to concave cost network flow problems. The LBs are derived from state space relaxations of a dynamic programming formulation, which involve the use of non-injective mapping functions guaranteing a reduction on the cardinality of the state space. The general state space relaxation procedure is extended to address problems involving transitions that go across several stages, as is the case of network flow problems. Applications for these LBs include: estimation of the quality of heuristic solutions; local search methods that use information of the LB solution structure to find initial solutions to restart the search (Fontes et al., 2003, Networks, 41, 221–228); and branch-and-bound (BB) methods having as a bounding procedure a modified version of the LB algorithm developed here, (see Fontes et al., 2005a). These LBs are iteratively improved by penalizing, in a Lagrangian fashion, customers not exactly satisfied or by performing state space modifications. Both the penalties and the state space are updated by using the subgradient method. Additional constraints are developed to improve further the LBs by reducing the searchable space. The computational results provided show that very good bounds can be obtained for concave cost network flow problems, particularly for fixed-charge problems.     

单机单转包商调度与外包联合优化问题的改进启发式算法

针对以总完工时间与总外包费用加权和为优化目标、总外包费用不超过给定上限的单机单转包商调度与外包联合优化问题,设计出一种改进的剔除型启发式算法。该算法通过运用动态规划技术求解新的辅助问题来获取初始外包工件集,并引入判定条件提前从初始外包工件集中剔除特定工件。为满足对总外包费用的上限约束,还利用新型的启发式筛选次序族逐一确定从当前外包工件集中剔除的工件。在仿真实验中,通过生成大量的测试算例,对比分析了改进算法与另2种已报道算法在求解质量、计算时间上的表现情况。实验结果表明所提出的改进算法在解的整体质量上具备显著的比较优势,并且能在5.6秒内完成对工件总数为1500的测试算例的求解。     

Sufficient optimality conditions for multidimensional optimal control problems with mixed constraints governed by an elliptic PDE

In this article, the idea of a dual dynamic programming is applied to the optimal control problems with multiple integrals governed by a semi-linear elliptic PDE and mixed state-control constraints. The main result called a verification theorem provides the new sufficient conditions for optimality in terms of a solution to the dual equation of a multidimensional dynamic programming. The optimality conditions are also obtained by using the concept of an optimal dual feedback control. Besides seeking the exact minimizers of problems considered some kind of an approximation is given and the sufficient conditions for an approximated optimal pair are derived.     

A NEW DETERMINISTIC FORMULATION FOR DYNAMIC STOCHASTIC PROGRAMMING PROBLEMS AND ITS NUMERICAL COMPARISON WITH OTHERS

A new deterministic formulation, called the conditional expectation formulation, is proposed for dynamic stochastic programming problems in order to overcome some disadvantages of existing deterministic formulations. We then check the impact of the new deterministic formulation and other two deterministic formulations on the corresponding problem size, nonzero elements and solution time by solving some typi     

An approach to find redundant objective function(s) and redundant constraint(s) in multi-objective nonlinear stochastic fractional programming problems

Structural redundancies in mathematical programming models are nothing uncommon and nonlinear programming problems are no exception. Over the past few decades numerous papers have been written on redundancy. Redundancy in constraints and variables are usually studied in a class of mathematical programming problems. However, main emphasis has so far been given only to linear programming problems. In this paper, an algorithm that identifies redundant objective function(s) and redundant constraint(s) simultaneously in multi-objective nonlinear stochastic fractional programming problems is provided. A solution procedure is also illustrated with numerical examples. The proposed algorithm reduces the number of nonlinear fractional objective functions and constraints in cases where redundancy exists.     

An exact algorithm for the precedence-constrained single-machine scheduling problem

This study proposes an efficient exact algorithm for the precedence-constrained single-machine scheduling problem to minimize total job completion cost where machine idle time is forbidden. The proposed algorithm is based on the SSDP (Successive Sublimation Dynamic Programming) method and is an extension of the authors’ previous algorithms for the problem without precedence constraints. In this method, a lower bound is computed by solving a Lagrangian relaxation of the original problem via dynamic programming and then it is improved successively by adding constraints to the relaxation until the gap between the lower and upper bounds vanishes. Numerical experiments will show that the algorithm can solve all instances with up to 50 jobs of the precedence-constrained total weighted tardiness and total weighted earliness–tardiness problems, and most instances with 100 jobs of the former problem.     

Exact Algorithms for Large-Scale Unconstrained Two and Three Staged Cutting Problems

In this paper we propose two exact algorithms for solving both two-staged and three staged unconstrained (un)weighted cutting problems. The two-staged problem is solved by applying a dynamic programming procedure originally developed by Gilmore and Gomory [Gilmore and Gomory, Operations Research, vol. 13, pp. 94–119, 1965]. The three-staged problem is solved by using a top-down approach combined with a dynamic programming procedure. The performance of the exact algorithms are evaluated on some problem instances of the literature and other hard randomly-generated problem instances (a total of 53 problem instances). A parallel implementation is an important feature of the algorithm used for solving the three-staged version.     

Bounded knapsack sharing

A bounded knapsack sharing problem is a maximin or minimax mathematical programming problem with one or more linear inequality constraints, an objective function composed of single variable continuous functions called tradeoff functions, and lower and upper bounds on the variables. A single constraint problem which can have negative or positive constraint coefficients and any type of continuous tradeoff functions (including multi-modal, multiple-valued and staircase functions) is considered first. Limiting conditions where the optimal value of a variable may be plus or minus infinity are explicitly considered. A preprocessor procedure to transform any single constraint problem to a finite form problem (an optimal feasible solution exists with finite variable values) is developed. Optimality conditions and three algorithms are then developed for the finite form problem. For piecewise linear tradeoff functions, the preprocessor and algorithms are polynomially bounded. The preprocessor is then modified to handle bounded knapsack sharing problems with multiple constraints. An optimality condition and algorithm is developed for the multiple constraint finite form problem. For multiple constraints, the time needed for the multiple constraint finite form algorithm is the time needed to solve a single constraint finite form problem multiplied by the number of constraints. Some multiple constraint problems cannot be transformed to multiple constraint finite form problems.     

A Deterministic Approach To Stochastic Optimal Control With Application To Anticipative Control

Using the decomposition of solution of SDE, we consider the stochastic optimal control problem with anticipative controls as a family of deterministic control problems parametrized by the paths of the driving Wiener process and of a newly introduced Lagrange multiplier stochastic process (nonanticipativity equality constraint). It is shown that the value function of these problems is the unique global solution of a robust equation (random partial differential equation) associated to a linear backward Hamilton-Jacobi-Bellman stochastic partial differential equation (HJB SPDE). This appears as limiting SPDE for a sequence of random HJB PDE's when linear interpolation approximation of the Wiener process is used. Our approach extends the Wong-Zakai type results [20] from SDE to the stochastic dynamic programming equation by showing how this arises as average of the limit of a sequence of deterministic dynamic programming equations. The stochastic characteristics method of Kunita [13] is used to represent the value function. By choosing the Lagrange multiplier equal to its nonanticipative constraint value the usual stochastic (nonanticipative) optimal control and optimal cost are recovered. This suggests a method for solving the anticipative control problems by almost sure deterministic optimal control. We obtain a PDE for the “cost of perfect information” the difference between the cost function of the nonanticipative control problem and the cost of the anticipative problem which satisfies a nonlinear backward HJB SPDE. Poisson bracket conditions are found ensuring this has a global solution. The cost of perfect information is shown to be zero when a Lagrangian submanifold is invariant for the stochastic characteristics. The LQG problem and a nonlinear anticipative control problem are considered as examples in this framework     

Differential dynamic programming and separable programs

This paper deals with differential dynamic programming for solving nonlinear separable programs. The present algorithm and its derivation are rather different from differential dynamic programming algorithms and their derivations by Mayne and Jacobson, who have not proved the convergence of their algorithms. The local convergence of the present algorithm is proved, and numerical examples are given.The author would like to express his appreciation to Professors H. Mine and T. Katayama for their helpful discussions. The author is also indebted to Professor D. Q. Mayne for drawing his attention to Refs. 1–2.     

动态模糊规划模型的构建及应用

常规规划模型通常存在如下两种缺陷:首先,它的目标系数及约束条件都是在硬性限制下的确定值,因而在建模方面弹性小、硬度大;其次,它的目标系数与时间无关,因此不能有效地刻划时时刻刻变化着的目标系数,而动态模糊规划模型可以有效地解决上述缺陷.首先应用模糊动态AHP确定目标系数;然后根据L-R模糊数的强序关系准则,将动态模糊规划模型分解为最优与最劣两个模糊规划模型;再根据以α水平截集为基础的求解方法,将上述两个模型进行相应的转换,建立具有风险分析功能的动态模糊规划模型;最后将其应用到一个实际算例中,收到较好的结果.     

The min-Knapsack problem with compactness constraints and applications in statistics

In the min-Knapsack problem, one is given a set of items, each having a certain cost and weight. The objective is to select a subset with minimum cost, such that the sum of the weights is not smaller than a given constant. In this paper, we introduce an extension of the min-Knapsack problem with additional “compactness constraints” (mKPC), stating that selected items cannot lie too far apart. This extension has applications in statistics, including in algorithms for change-point detection in time series. We propose three solution methods for the mKPC. The first two methods use the same Mixed-Integer Programming (MIP) formulation but with two different approaches: passing the complete model with a quadratic number of constraints to a black-box MIP solver or dynamically separating the constraints using a branch-and-cut algorithm. Numerical experiments highlight the advantages of this dynamic separation. The third approach is a dynamic programming labelling algorithm. Finally, we focus on the particular case of the unit-cost mKPC (1c-mKPC), which has a specific interpretation in the context of the statistical applications mentioned above. We prove that the 1c-mKPC is solvable in polynomial time with a different ad-hoc dynamic programming algorithm. Experimental results show that this algorithm vastly outperforms both generic approaches for the mKPC and a simple greedy heuristic from the literature.