A monotonic projective algorithm for fractional linear programming

We demonstrate that Karmarkar's projective algorithm is fundamentally an algorithm for fractional linear programming on the simplex. Convergence for the latter problem is established assuming only an initial lower bound on the optimal objective value. We also show that the algorithm can be easily modified so as to assure monotonicity of the true objective values, while retaining all global convergence properties. Finally, we show how the monotonic algorithm can be used to obtain an initial lower bound when none is otherwise available.     

Control applications of nonlinear convex programming

Since 1984 there has been a concentrated effort to develop efficient interior-point methods for linear programming (LP). In the last few years researchers have begun to appreciate a very important property of these interior-point methods (beyond their efficiency for LP): they extend gracefully to nonlinear convex optimization problems. New interior-point algorithms for problem classes such as semidefinite programming (SDP) or second-order cone programming (SOCP) are now approaching the extreme efficiency of modern linear programming codes. In this paper we discuss three examples of areas of control where our ability to efficiently solve nonlinear convex optimization problems opens up new applications. In the first example we show how SOCP can be used to solve robust open-loop optimal control problems. In the second example, we show how SOCP can be used to simultaneously design the set-point and feedback gains for a controller, and compare this method with the more standard approach. Our final application concerns analysis and synthesis via linear matrix inequalities and SDP.     

Tropical linear-fractional programming and parametric mean payoff games

Tropical polyhedra have been recently used to represent disjunctive invariants in static analysis. To handle larger instances, tropical analogues of classical linear programming results need to be developed. This motivation leads us to study the tropical analogue of the classical linear-fractional programming problem. We construct an associated parametric mean payoff game problem, and show that the optimality of a given point, or the unboundedness of the problem, can be certified by exhibiting a strategy for one of the players having certain infinitesimal properties (involving the value of the game and its derivative) that we characterize combinatorially. We use this idea to design a Newton-like algorithm to solve tropical linear-fractional programming problems, by reduction to a sequence of auxiliary mean payoff game problems.     

A minisum location problem with regional demand considering farthest Euclidean distances

We consider a continuous multi-facility location-allocation problem that aims to minimize the sum of weighted farthest Euclidean distances between (closed convex) polygonal and/or circular demand regions, and facilities they are assigned to. We show that the single facility version of the problem has a straightforward second-order cone programming formulation and can therefore be efficiently solved to optimality. To solve large size instances, we adapt a multi-dimensional direct search descent algorithm to our problem which is not guaranteed to find the optimal solution. In a special case with circular and rectangular demand regions, this algorithm, if converges, finds the optimal solution. We also apply a simple subgradient method to the problem. Furthermore, we review the algorithms proposed for the problem in the literature and compare all these algorithms in terms of both solution quality and time. Finally, we consider the multi-facility version of the problem and model it as a mixed integer second-order cone programming problem. As this formulation is weak, we use the alternate location-allocation heuristic to solve large size instances.     

Variational density matrix optimization using semidefinite programming

We discuss how semidefinite programming can be used to determine the second-order density matrix directly through a variational optimization. We show how the problem of characterizing a physical or N-representable density matrix leads to matrix-positivity constraints on the density matrix. We then formulate this in a standard semidefinite programming form, after which two interior point methods are discussed to solve the SDP. As an example we show the results of an application of the method on the isoelectronic series of Beryllium.     

求解一类特殊的双层规划问题的遗传算法

主要研究上层函数及其约束函数不要求具有凸性和可微性,下层是关于下层决策变量是凸二次规划的双层规划模型,通过Karush-Kuhn-Tucher 条件转化为一个单层规划,利用下层是正定二次规划,将下层的决策变量表示为关于 Lagrangian乘子的表达式,从而降低了搜索空间的维数,设计了遗传算法,并通过数值实验表明该遗传算非常有效。     

A dynamic convexized method for nonconvex mixed integer nonlinear programming

We consider in this paper the nonconvex mixed-integer nonlinear programming problem. We present a mixed local search method to find a local minimizer of an unconstrained nonconvex mixed-integer nonlinear programming problem. Then an auxiliary function which has the same global minimizers and the same global minimal value as the original problem is constructed. Minimization of the auxiliary function using our local search method can escape successfully from previously converged local minimizers by taking increasing values of parameters. For the constrained nonconvex mixed-integer nonlinear programming problem, we develop a penalty based method to convert the problem into an unconstrained one, and then use the above method to solve the later problem. Numerical experiments and comparisons on a set of MINLP benchmark problems show the effectiveness of the proposed algorithm.     

基于动态规划的商品装载问题及JAVA实现

如何装载商品使经济利益最大化是物流配载装箱问题中划分出的子问题。该子问题被抽象为0-1背包问题,根据动态规划算法建立数学模型,分析其优点,并用JAVA语言得以实现。最后给出测试实例,得出动态规划法具有高效性的特点,该算法可以广泛使用于物流领域。     

Sequence of linear programming for transmission of fine-scalable coded content in bandwidth-limited environments

In this paper, we propose an optimal peer assignment algorithm on peer-to-peer networks. This algorithm is designed to maximize the quality of transmitting fine-scalable coded content by exploiting the embedding property of scalable coding. To be more realistic, we assume that the requesting peer has a delay constraint to display the content within a certain delay bound, and it also has limited incoming bandwidth. We first use a simple example to illustrate the peer assignment problem, and then formulate this problem as a linear programming problem, followed by a nonlinear programming problem. To efficiently solve the second nonlinear problem, we transform it into a sequence of linear programming problems. Finally, we apply our proposed algorithm to both image and video transmissions in bandwidth-limited environments. Extensive experiments have been carried out to evaluate the complexity and performance of our approach by comparing it with both nonlinear formulation and two heuristic schemes. The results have verified the superior performance of our proposed algorithm.     

Efficient DC programming approaches for the asymmetric eigenvalue complementarity problem

In this paper, we propose nonlinear programming (NLP) formulations and difference of convex functions (DC) programming approaches for the asymmetric eigenvalue complementarity problem (EiCP). The EiCP has a solution if and only if these NLP formulations have zero global optimal value. We reformulate the NLP formulations as DC programs which can be efficiently solved by a DC algorithm. Some preliminary numerical results illustrate the good performance of the proposed methods.     

Optimal decision making in multi-product dual sourcing procurement with demand forecast updating

In this paper, we will investigate a buyer's decision making problem in procuring multiple products, each treated as a newsvendor, from two markets. The contract market has a long lead time, a fixed wholesale price and resource constraints. While the spot market has an instant lead time and a highly volatile price. The purchasing decision at the spot market can be made near the beginning of the selling season to take the advantage of the most recent demand forecast. The buyer needs to determine the purchasing quantity for each product at the two markets to maximize the expected profit by trading off between the resource availability, demand uncertainty and price variability. The procurement decision making is modeled as a bi-level programming problem under both a single resource constraint and under multiple resource constraints. We show that this bi-level programming problem can be formulated as a single-level concave programming problem. We then develop a sequential algorithm which solves for a linear approximation of the concave programming problem in each iteration. This algorithm can be used to solve a real world problem with up to thousands of kinds of products, and is found to be highly efficient and effective.     

Solving a linear multiperiod portfolio problem by interior-point methodology

In this report we formulate a linear multiperiod programming problem and show how it can be solved by a new interior point algorithm. The conditions of convergence and applicability of the algorithm of centers are explicitly connected to the multiperiod programming problem. For the former, effective application is supported by a set of simplifying conditions stated and proved in the text. For the latter, boundedness and nontriviality under real world conditions is demonstrated, allowing for its solution by the interior point algorithm. The use of a fast interior point algorithm is motivated by some empirical evidence from a Revised Simplex optimizer.     

On using priced timed automata to achieve optimal scheduling

In this paper, we describe an approach for solving the general class of energy-optimal task graph scheduling problems using priced timed automata. We provide an efficient zone-based algorithm for minimum-cost reachability. Furthermore, we show how the simple structure of the linear programs encountered during symbolic minimum-cost reachability analysis of priced timed automata can be exploited in order to substantially improve the performance of the current algorithm. The idea is rooted in duality of linear programs and we show that each encountered linear program can be reduced to the dual problem of an instance of the min-cost flow problem. Experimental results using Uppaal show a 70–80 percent performance gain. We provide priced timed automata models for the scheduling problems and provide experimental results illustrating the potential competitiveness of our approach compared to existing approaches such as mixed integer linear programming.This research was conducted in part at Aalborg University, where the author was supported by a CISS Faculty Fellowship.

---

     

Scenario aggregation for supply chain quantity-flexibility contract

In this research, we apply a scenario aggregation approach to solving the supply chain contract model formulated by two-stage stochastic programming problem. The supply chain contract can achieve the coordination between the buyer and the supplier. We formulate the stochastic programming model for a quantity-flexibility contract. The scenario aggregation method called the progressive hedging method is used to solve this problem. Experimental results show the convergence behaviour of the algorithm and the sensitivity of parameters.     

基于遗传算法的频繁项挖掘算法

从数学规划的角度重新表述了单维布尔型频繁项挖掘问题,利用新定义的加法和数乘及范数运算将其归结为一个非线性0－1规划问题,并利用遗传算法进行求解。在分析频繁项挖掘问题困难原因的基础上,提出了利用原数据库记录确定初始种群的方法,并在IBM公布的ticeval2000数据库上进行了数值实验。实际计算结果表明,该方法一般在几代内即可找到一批长频繁模式。     

Semi-Markov adaptive critic heuristics with application to airline revenue management

The adaptive critic heuristic has been a popular algorithm in reinforcement learning(RL) and approximate dynamic programming(ADP) alike.It is one of the first RL and ADP algorithms.RL and ADP algorithms are particularly useful for solving Markov decision processes(MDPs) that suffer from the curses of dimensionality and modeling.Many real-world problems,however,tend to be semi-Markov decision processes(SMDPs) in which the time spent in each transition of the underlying Markov chains is itself a random variable.Unfortunately for the average reward case,unlike the discounted reward case,the MDP does not have an easy extension to the SMDP.Examples of SMDPs can be found in the area of supply chain management,maintenance management,and airline revenue management.In this paper,we propose an adaptive critic heuristic for the SMDP under the long-run average reward criterion.We present the convergence analysis of the algorithm which shows that under certain mild conditions,which can be ensured within a simulator,the algorithm converges to an optimal solution with probability 1.We test the algorithm extensively on a problem of airline revenue management in which the manager has to set prices for airline tickets over the booking horizon.The problem has a large scale,suffering from the curse of dimensionality,and hence it is difficult to solve it via classical methods of dynamic programming.Our numerical results are encouraging and show that the algorithm outperforms an existing heuristic used widely in the airline industry.     

自适应表压缩方法优化STR算法

表约束,也称为外延式约束,是约束编程领域最常见的约束形式,表压缩方法通过紧凑的表示元组集可以极大地缩减空间消耗,同时加速 GAC 算法。笛卡尔乘积表示和短支持是表约束中最常见的两种表压缩方法,两种表压缩方法在同一问题上的压缩率是影响它们优化效果的主要原因。基于 STR 算法提出一种自适应表压缩方法,在求解问题时自适应选择压缩率大的表压缩方法,将自适应表压缩方法应用到 STR2 上提出了 STR2 Adaptive 算法,可以同时覆盖两种表压缩方法的优势。实验结果表明,STR2 Adaptive 算法在绝大部分实例上都能自适应选择最佳的表压缩方法,有效地减少了STR2算法空间消耗和CPU运行时间。然后将自适应表压缩方法扩展到采用了高效的比特向量表示的 STRbit 算法上提出了 STRbit Adaptive 算法。实验结果表明,STRbit Adaptive 算法效率同样普遍优于 STRbit 算法。     

Constraint Retraction in CLP(FD): Formal Framework and Performance Results

Constraint retraction can be described, in general, as the possibility of deleting a previously stated piece of information. This is obviously very convenient in many programming frameworks, especially in those that involve some level of interaction between the user and the system, or also in those concerning rescheduling or replanning. Nevertheless, constraint retraction is usually not provided in current constraint programming environments. This is mainly due to its high complexity and also to its non-monotonic nature, which would make most of such systems much more complex to reason with. In this paper we avoid these problems by considering a specific constraint programming framework, called clpFD, that is, constraint logic programming (CLP) over finite domain (FD) constraints. We propose an algorithm which deletes a constraint from a set of FD constraints, while maintaining partial arc-consistency, which is usual in this programming framework. What is crucial is that the retraction operation we propose is incremental, in that it follows the chain of dependencies among variables which are set by the nature of the FD constraints, and by doing so it updates only the part of the constraint set which is affected by the deletion. We also detail how constraint retraction can be incorporated in the FD constraint solver and we evaluate its behavior within the clpFD system. Experimental results on usual benchmarks, on classes of problems of increasing connectivity, and also on a real-life problem show that in almost all cases the use of our retraction algorithm provides great speed-up with respect to standard methods while not slowing down the clpFD system when no retraction is performed. This provides the system with an efficient way of retracting constraints while not changing its performance when the user does not want to use this new feature.     

支持向量机理论与基于规划的神经网络学习算法

近年来支持向量机（SVM）理论得到国外学者高度的重视,普遍认为这是神经网络学习的新研究方向,近来也开始得到国内学者的注意。该文将研究SVM理论与神经网络的规划算法的关系,首先指出,Vapnik的基于SVM的算法与该文作者1994年提出的神经网络的基于规划的算法是等价的,即在样本集是线性可分的情况下,二者求得的均是最大边缘（maximal margin)解。不同的是,前者（通常用拉格郎日乘子法）求解的复杂性将随规模呈指数增长,而后者的复杂性是规模的多项式函数。其次,作者将规划算法化为求一点到某一凸集上的投影,利用这个几何的直观,给出一个构造性的迭代求解算法－－“单纯形迭代算法”。新算法有很强的几何直观性,这个直观性将加深对神经网络（线性可分情况下）学习的理解,并由此导出一个样本集是线性可分的充分必要条件。另外,新算法对知识扩充问题,给出一个非常方便的增量学习算法。最后指出,“将一些必须满足的条件,化成问题的约束条件,将网络的某一性能,作为目标函数,将网络的学习问题化为某种规划问题来求解”的原则,将是研究神经网络学习问题的一个十分有效的办法。     

求解模糊机会约束规划的混合智能算法

模糊机会约束规划是一类重要的模糊规划,它广泛地存在于许多领域中,微粒群算法已实现了对其的有效求解,但求解速度仍不能满足大规模模糊机会约束规划问题的求解,为了寻找更为高效的求解模糊机会约束规划的算法,通过采用模糊模拟产生样本训练BP网络以逼近模糊函数,然后应用微粒群算法并以逼近模糊函数的神经网络作为适应值估计及检验解的可行性,从而提出了一种求解模糊机会约束规划的混合智能算法。最后通过仿真结果说明了算法的正确性和有效性。