Optimization models for the single delay management problem in public transportation

Passengers travelling in public transportation networks often have to use different lines to cover the trip from their origin to the desired destination. As a consequence, the reliability of connections between vehicles is a key issue for the attractiveness of the intermodal transportation network and it is strongly affected by some unpredictable events like breakdowns or vehicle delays. In such cases, a decision is required to determine if the connected vehicles should wait for the delayed ones or keep their schedule. The delay management problem (DMP) consists in defining the wait/depart policy which minimizes the total delay on the network. In this work, we present two equivalent mixed integer linear programming models for the DMP with a single initial delay, able to reduce the number of variables with respect to the formulations proposed by the literature. The two models are solved by a branch and cut procedure and by a constraint generation approach respectively, and preliminary computational results are presented.     

Optimal control synthesis in therapy of solid tumor growth

A mathematical model of tumor growth therapy is considered. The total amount of a drug is bounded and fixed. The problem is to choose an optimal therapeutic strategy, i.e., to choose an amount of the drug permanently affecting the tumor that minimizes the number of tumor cells by a given time. The problem is solved by the dynamic programming method. Exact and approximate solutions to the corresponding Hamilton-Jacobi-Bellman equation are found. An error estimate is proved. Numerical results are presented.     

一类动态规划的解法及其在Turbo码解码中的应用

研究一类多阶段动态规划问题,给出了求最优解的方法.将这种多阶段动态规划应用于Turbo译码中,不仅可以减少运算量,还可以避免传统的Turbo译码算法需要进行指数运算以及其随着迭代次数的增加容易出现的数据溢出问题,因此是一种十分有效的方法,是对系统工程理论应用领域的拓宽.     

求解非线性规划的原始对偶内点法(英文)

In this paper, we propose a primal-dual interior point method for solving general constrained nonlinear programming problems. To avoid the situation that the algorithm we use may converge to a saddle point or a local maximum, we utilize a merit function to guide the iterates toward a local minimum. Especially, we add the parameter ε to the Newton system when calculating the decrease directions. The global convergence is achieved by the decrease of a merit function. Furthermore, the numerical results confirm that the algorithm can solve this kind of problems in an efficient way.     

On the symmetry-breaking bifurcation of chaotic attractors

A new type of crisis is shown to exist in a broad class of systems (including the Lorenz model) which leads to an anomalous band splitting or to a symmetry-breaking bifurcation of the strange attractor, depending on the actual values of the control parameters. A piecewise linear model is used to understand the mechanism of this crisis and to obtain exact results.     

Calculating risk neutral probabilities and optimal portfolio policies in a dynamic investment model with downside risk control

This paper presents a method for solving multiperiod investment models with downside risk control characterized by the portfolio’s worst outcome. The stochastic programming problem is decomposed into two subproblems: a nonlinear optimization model identifying the optimal terminal wealth distribution and a stochastic linear programming model replicating the identified optimal portfolio wealth. The replicating portfolio coincides with the optimal solution to the investor’s problem if the market is frictionless. The multiperiod stochastic linear programming model tests for the absence of arbitrage opportunities and its dual feasible solutions generate all risk neutral probability measures. When there are constraints such as liquidity or position requirements, the method yields approximate portfolio policies by minimizing the initial cost of the replication portfolio. A numerical example illustrates the difference between the replicating result and the optimal unconstrained portfolio.     

Bifurcation problems in nonlinear parametric programming

The nonlinear parametric programming problem is reformulated as a closed system of nonlinear equations so that numerical continuation and bifurcation techniques can be used to investigate the dependence of the optimal solution on the system parameters. This system, which is motivated by the Fritz John first-order necessary conditions, contains all Fritz John and all Karush-Kuhn-Tucker points as well as local minima and maxima, saddle points, feasible and nonfeasible critical points. Necessary and sufficient conditions for a singularity to occur in this system are characterized in terms of the loss of a complementarity condition, the linear dependence of the gradients of the active constraints, and the singularity of the Hessian of the Lagrangian on a tangent space. Any singularity can be placed in one of seven distinct classes depending upon which subset of these three conditions hold true at a solution. For problems with one parameter, we analyze simple and multiple bifurcation of critical points from a singularity arising from the loss of the complementarity condition, and then develop a set of conditions which guarantees the unique persistence of a minimum through this singularity. The research of this author was supported by National Science Foundation through NSF Grant DMS-85-10201 and by the Air Force Office of Scientific Research through instrument number AFOSR-ISSA-85-00079.     

一类切换线性系统的动态输出反馈H_∞控制:LMIs方法

研究一类由任意有限多个线性子系统组成的切换系统的动态输出反馈H∞控制问题.利用共同Lyapunov函数方法和凸组合技术,给出由矩阵不等式表示的控制器存在的充分条件,并设计了相应的子控制器和切换规则.采用消元法,将该矩阵不等式转化为一组线性矩阵不等式(LMIs).最后给出一个数值仿真实例证明结论的有效性.     

An efficient computational approach for railway booking problems

This paper deals with the determination of seat allocations for a rail booking system. It is assumed that demand for each trip in the network can be divided into two segments, namely a full fare segment and a discounted fare segment. A constrained nonlinear integer programming model is formulated to deal with this problem. The purpose of this paper is to develop an efficient heuristic approach to develop the booking limits for all ticket types in the railway network. The solutions obtained by the heuristic approach are compared with those found by the Lingo software and the DICOPT solver. Numerical results show that the proposed heuristic approach only require a small number of CPU time to obtain superior solutions.     

An exact and polynomial distance-based algorithm to reconstruct single copy tandem duplication trees

The problem of reconstructing the duplication tree of a set of tandemly repeated sequences which are supposed to have arisen by unequal recombination, was first introduced by Fitch (1977), and has recently received a lot of attention. In this paper, we place ourselves in a distance framework and deal with the restricted problem of reconstructing single copy duplication trees. We describe an exact and polynomial distance based algorithm for solving this problem, the parsimony version of which has previously been shown to be NP-hard (like most evolutionary tree reconstruction problems). This algorithm is based on the minimum evolution principle, and thus involves selecting the shortest tree as being the correct duplication tree. After presenting the underlying mathematical concepts behind the minimum evolution principle, and some of its benefits (such as statistical consistency), we provide a new recurrence formula to estimate the tree length using ordinary least-squares, given a matrix of pairwise distances between the copies. We then show how this formula naturally forms the dynamic programming framework on which our algorithm is based, and provide an implementation in O(n³) time and O(n²) space, where n is the number of copies.