Greedy algorithms for a class of knapsack problems with binary weights

In this article we identify a class of two-dimensional knapsack problems with binary weights and related three-criteria unconstrained combinatorial optimization problems that can be solved in polynomial time by greedy algorithms. Starting from the knapsack problem with two equality constraints we show that this problem can be solved efficiently by using an appropriate partitioning of the items with respect to their binary weights. Based on the results for this problem we derive an algorithm for the three-criteria unconstrained combinatorial optimization problem with two binary objectives that explores the connectedness of the set of efficient knapsacks with respect to a combinatorial definition of adjacency. Furthermore, we prove that our approach is asymptotically optimal and provide extensive computational experiments that shows that we can solve the three-criteria problem with up to one million items in less than half an hour. Finally, we derive an efficient algorithm for the two-dimensional knapsack problems with binary constraints that only takes into account the results we obtained for the unconstrained three-criteria problem with binary weights.     

Valuation of European continuous-installment options

This paper is concerned with the valuation of European continuous-installment options where the aim is to determine the initial premium given a constant installment payment plan. The distinctive feature of this pricing problem is the determination, along with the initial premium, of an optimal stopping boundary since the option holder has the right to stop making installment payments at any time before maturity. Given that the initial premium function of this option is governed by an inhomogeneous Black-Scholes partial differential equation, we can obtain two alternative characterizations of the European continuous-installment option pricing problem, for which no closed-form solution is available. First, we formulate the pricing problem as a free boundary problem and using the integral representation method, we derive integral expressions for both the initial premium and the optimal stopping boundary. Next, we use the linear complementarity formulation of the pricing problem for determining the initial premium and the early stopping curve implicitly with a finite difference scheme. Finally, the pricing problem is posed as an optimal stopping problem and then implemented by a Monte Carlo approach.     

An optimal control approach to robust tracking of linear systems

In our early work, we show that one way to solve a robust control problem of an uncertain system is to translate the robust control problem into an optimal control problem. If the system is linear, then the optimal control problem becomes a linear quadratic regulator (LQR) problem, which can be solved by solving an algebraic Riccati equation. In this article, we extend the optimal control approach to robust tracking of linear systems. We assume that the control objective is not simply to drive the state to zero but rather to track a non-zero reference signal. We assume that the reference signal to be tracked is a polynomial function of time. We first investigated the tracking problem under the conditions that all state variables are available for feedback and show that the robust tracking problem can be solved by solving an algebraic Riccati equation. Because the state feedback is not always available in practice, we also investigated the output feedback. We show that if we place the poles of the observer sufficiently left of the imaginary axis, the robust tracking problem can be solved. As in the case of the state feedback, the observer and feedback can be obtained by solving two algebraic Riccati equations.     

Hybrid techniques based on solving reduced problem instances for a longest common subsequence problem

Finding the longest common subsequence of a given set of input strings is a relevant problem arising in various practical settings. One of these problems is the so-called longest arc-preserving common subsequence problem. This NP-hard combinatorial optimization problem was introduced for the comparison of arc-annotated ribonucleic acid (RNA) sequences. In this work we present an integer linear programming (ILP) formulation of the problem. As even in the context of rather small problem instances the application of a general purpose ILP solver is not viable due to the size of the model, we study alternative ways based on model reduction in order to take profit from this ILP model. First, we present a heuristic way for reducing the model, with the subsequent application of an ILP solver. Second, we propose the application of an iterative hybrid algorithm that makes use of an ILP solver for generating high quality solutions at each iteration. Experimental results concerning artificial and real problem instances show that the proposed techniques outperform an available technique from the literature.     

限制树宽的图的最小标记生成数算法

本文研究了图的最小标记生成树问题。首先介绍在一般图上基于搜索树的最小标记生成树的算法;然后考虑了限制树宽的图,得到了效率更高的算法。该算法在树宽为常数的情况下,时间复杂度关于图的顶点个数为多项式,从而也证明了最小标记生成树在限制树宽的图上属于确定参数可解问题。     

Semirigid inclusions in elastic bodies: Mechanical interplay and optimal control

The paper concerns an analysis of an equilibrium problem for 2D elastic body with two semirigid inclusions. It is assumed that inclusions have a joint point, and we investigate a junction problem for these inclusions. The existence of solutions is proved, and different equivalent formulations of the problem are proposed. We investigate a convergence to infinity of a rigidity parameter of the semirigid inclusion. It is proved that in the limit, we obtain an equilibrium problem for the elastic body with a rigid inclusion and a semirigid one. A parameter identification problem is investigated. In particular, the existence of a solution to a suitable optimal control problem is proved.     

离散时间系统混合l1/H∞-控制问题

研究MIMO离散时间系统混合l₁/H_∞控制问题. 通过引入辅助优化问题, 证明了目标优化值关于约束H_∞指标的连续依赖性及其辅助问题最优化解的存在性, 同时证明了辅助优化问题的截断序列问题解的收敛性, 且其极限为混合l₁/H_∞_控制优化的辅助问题的最优化解. 还给出了优化目标值的上下界逼近.     

Bounded parallel-batch scheduling on single and multi machines for deteriorating jobs

We consider the bounded parallel-batch scheduling problem in which the processing time of a job is a simple linear function of its starting time. The objective is to minimize the makespan. When the jobs have identical release dates, we present an optimal algorithm for the single-machine problem and an fully polynomial-time approximation scheme for the parallel-machine problem. When the jobs have distinct release dates, we show that the single-machine problem is NP-hard and present an optimal algorithm for one special case.     

A fast approach to deformable surface 3D tracking

Deformable surface 3D tracking is a severely under-constrained problem and great efforts have been made to solve it. A recent state-of-the-art approach solves this problem by formulating it as a second order cone programming (SOCP) problem. However, one drawback of this approach is that it is time-consuming. In this paper, we propose an effective method for 3D deformable surface tracking. First, we formulate the deformable surface tracking problem as a linear programming (LP) problem. Then, we solve the LP problem with an algorithm which converges superlinearly rather than bisection algorithm whose convergence speed is linear. Our experimental studies on synthetic and real data have demonstrated the proposed method can not only reliably recover 3D structures of surfaces but also run faster than the state-of-the-art method.     

Exponential neighborhood search for a parallel machine scheduling problem

We consider the parallel machine scheduling problem where jobs have different earliness-tardiness penalties and a restrictive common due date. This problem is NP-hard in the strong sense. In this paper we define an exponential size neighborhood for this problem and prove that finding the local minimum in it is an NP-hard problem. The main contribution of this paper is to propose a pseudo-polynomial algorithm that finds the best solution of the exponential neighborhood. Additionally, we present some computational results.     

On the Flattest Common Supersequence Method for Deadlock-Free Routing in Arbitrary Networks

In this paper we consider the problem of deadlock-free routing in arbitrary parallel and distributed computers. We focus on asynchronous routing algorithms which continuously receive new packets to route and which do not discard packets that encounter congestion. Specifically, we examine what we call the deadlock-free routing (DFR ) problem. The input to the DFR problem consists of an arbitrary network and an arbitrary set of paths in the network. The output consists of a routing algorithm, which is a list of the buffers used along each of the paths. The routing algorithm is required to be free from deadlock and the goal is to minimize the number of buffers required in any one node. We study the DFR problem by converting it into an equivalent problem which we call the flattest common supersequence (FCS ) problem. The input to the FCS problem consists of a set of sequences and the output consists of a single sequence that contains all of the input sequences as (possibly noncontiguous) subsequences. The goal of the FCS problem is to minimize the maximum frequency of any symbol in the output sequence. We present three main results. First, we prove that the decision version of the FCS problem is NP-complete, and has no polynomial-time approximation scheme unless P= NP . An alternative proof is presented which shows that unlike the shortest common supersequence (SCS) problem, the FCS problem is still NP-complete for two input sequences. This implies that approximation algorithms for FCS based on an exact pairwise merge are not possible. Next, we propose and experimentally evaluate a range of heuristics for FCS. Our experimental results show that one of these heuristics performs very well over a wide range of inputs. Lastly, we prove that this heuristic is in fact optimal for certain restricted classes of inputs. Online publication November 27, 2000.     

Speed tracking control of PM synchronous motor by internal model design

In this article, we consider a speed tracking and load torque disturbance rejection problem of PM synchronous motor by internal model design. The problem is first formulated as a global robust output regulation problem of a special class of multivariable systems. Then the output regulation problem is further converted into a global stabilisation problem of an augmented system composed of the original plant and an internal model. As the augmented system does not take any known special form, we have developed a specific tool to deal with the stabilisation problem. In particular, a generalised changing supply function technique applicable to non-input-to-state stable (ISS) systems is developed. This technique, in conjunction with a particular nonlinear internal model, leads to an effective solution to the problem.     

On Approximation Scheme Preserving Reducibility and Its Applications

In this paper we introduce a new polynomial-time approximation scheme preserving reducibility, which we call PTAS-reducibility, that generalizes previous definitions. As a first application of this generalization, we prove the APX-completeness under PTAS-reducibility of a polynomially bounded optimization problem, that is, an APX problem whose measure function is bounded by a polynomial in the length of the instance and such that any APX problem is PTAS-reducible to it. As far as we know, no such problem was known before. This result combined with results of Khanna et al. allows us to infer that several natural optimization problems are APX-complete under PTAS-reducibility, such as MAX CUT and MAX SAT. Successively, we apply the notion of APX-completeness under PTAS-reducibility to the study of the relative complexity of evaluating an r -approximate value and computing an r -approximate solution for any r . We first show that if P NP co NP, then the former question can be easier than the latter even if the optimization problem is NP-hard. We then give strong evidence that if an optimization problem is APX-complete under PTAS-reducibility, then the two questions are both hard. Received February 15, 1996, and in final form May 28, 1999.     

确保安全QoS的WFS路由算法

中的最关键的功能组件之一就是基于QoS的路由，从本质上看QoS路由实际就是端点到端点的带结点条件限制和边条件限制的最短路径问题，在文[1]中指出这种问题是NP完全的。本文研究对丢失敏感对延时不敏感的QoS路由模型——确保安全QoS的路由算法，并提出了一种新启发式算法；首先，我们讨论QoS一般模型，然后利用图论中的WFS算法求解QoS路由，该算法的时间复杂度为O(nlog(n)+n×d×K_0)，优于化前在该问题上的求解算法。     

Loss-Aversion with Kinked Linear Utility Functions

Prospect theory postulates that the utility function is characterized by a kink (a point of non-differentiability) that distinguishes gains from losses. In this paper we present an algorithm that efficiently solves the linear version of the kinked-utility problem. First, we transform the non-differentiable kinked linear-utility problem into a higher dimensional, differentiable, linear program. Second, we introduce an efficient algorithm that solves the higher dimensional linear program in a smaller dimensional space. Third, we employ a numerical example to show that solving the problem with our algorithm is 15 times faster than solving the higher dimensional linear program using the interior point method of Mosek. Finally, we provide a direct link between the piece-wise linear programming problem and conditional value-at-risk, a downside risk measure.     

The piecewise optimisation method for approximating uncertain optimal control problems under optimistic value criterion

In this paper, we introduce an approximate model and propose a piecewise optimisation method to simplify the expression of optimal control for an uncertain linear quadratic optimal control problem. First, we consider an optimal control problem of uncertain linear quadratic model under optimistic value criterion. Based on the equation of optimality, we deduce an analytic expression of optimal control. Then, we study an approximate model with control parameter and propose a piecewise optimisation method for solving the optimal parameter of such an approximate model. As an application, a four-wheel steering vehicle optimal control problem is given to show the utility of the proposed approximate model and the efficiency of the proposed piecewise optimisation method.     

A general formulation and solvability of the global robust output regulation problem

While the output regulation problem for linear systems accommodates both bounded and unbounded exogenous signals, the existing formulation of the output regulation problem for nonlinear systems only allows bounded exogenous signals produced by an exosystem with a neutrally stable equilibrium. In particular, when it comes to the robust output regulation problem, the only admissible exogenous signal is a finite combination of step and sinusoidal functions. In this paper, we give a general formulation of the robust output regulation problem that admits unbounded exogenous signals, and contains the previous formulations as special cases when the system is linear or when the exogenous signals are bounded. Then, we give conditions under which the problem can be solved by solving a robust stabilization problem of an augmented system. Finally, we apply our general result to obtain the solvability conditions of the general robust output regulation problem for the class of lower triangular nonlinear systems.     

基于Givens变换矩阵的时间结构信号盲源分离新算法

对于时间结构信号的盲源分离(Blind Source Separation,BSS),独立成分分析(Independent Component Analysis,ICA)是十分有效的方法。在对观测信号白化处理后,ICA的关键是寻找去除高阶相关性的正交分离矩阵。鉴于任意维数正交矩阵可以表示为Givens变换矩阵的乘积,提出了一种新的时间结构信号盲源分离算法。首先,利用Givens变换矩阵参数化表示正交分离矩阵,减少了要估计参数的个数;其次,以多步时延协方差矩阵的联合近似对角化为目标函数,将盲源分离问题转化为无约束优化问题,并利用拟牛顿法中的BFGS算法对Givens变换矩阵中的参数进行估计,得到分离矩阵;最后,以实际的混合语音信号分离做仿真实验,验证了该算法对时间结构信号的盲源分离是有效的。     

Combinatorial optimization model and MIP formulation for the structural analysis of conditional differential-algebraic systems

In this paper we consider the structural analysis problem for differential-algebraic systems with conditional equations. This problem consists, given a conditional differential-algebraic system, in verifying if the system is structurally nonsingular for every state, and if not in finding a state in which the system is structurally singular. We give a formulation for this problem as an integer linear program. This is based on a transformation of the problem into a matching problem in an auxiliary graph. We also show that the linear relaxation of that formulation can be solved in polynomial time. Using this, we develop a Branch-and-Cut algorithm for solving the problem and present some experimental results.