A tour construction heuristic for the travelling salesman problem

The tour construction heuristic that generates initial tours for the tour improvement heuristics plays an important role in solving the travelling salesman problem (TSP). With the help of an effective tour construction heuristic, the performance of a heuristic can be improved. In this study we present a new tour construction algorithm, the construction priority (CP). We incorporate the performance of the CP into metaheuristics such as tabu search, genetic algorithm, space smoothing, and noising methods. The performance of the CP is empirically compared with the nearest neighbour (NN) approach. Extensive computational comparison shows that the CP is considerably more effective compared to NN.     

Bounding,filtering and diversification in CP-based local branching

Local branching is a general purpose heuristic method which searches locally around the best known solution by employing tree search. It has been successfully used in Mixed-Integer Programming where local branching constraints are used to model the neighborhood of an incumbent solution and improve the bound. We propose the integration of local branching in Constraint Programming (CP). This integration is not simply a matter of implementation, but requires a number of significant extensions. The original contributions of this paper are: the definition of an efficient and incremental bound computation for the neighborhood, a cost-based filtering algorithm for the local branching constraint and a novel diversification strategy that can explore arbitrarily far regions of the search tree w.r.t. the already found solutions. We demonstrate the practical value of local branching in CP by providing an extensive experimental evaluation on the hard instances of the Asymmetric Traveling Salesman Problem with Time Windows.     

Hybrid Modelling for Robust Solving

We study a balanced academic curriculum problem and an industrial steel mill slab design problem. These problems can be modelled in different ways, using both Integer Linear Programming (ILP) and Constraint Programming (CP) techniques. We consider the utility of each model. We also propose integrating the models to create hybrids that benefit from the complementary strengths of each model. Experimental results show that hybridization significantly increases the domain pruning and decreases the run-time on many instances. Furthermore, a CP/ILP hybrid model gives a more robust performance in the face of varying instance data.     

Enhancing the performance of constraint programming through the introduction of linear programming

Constraint Programming (CP) has been successful in a number of combinatorial search and discrete optimisation problems. Yet other more traditional approaches, such as Integer Programming (IP), can still give a better performance on the same problem types. Central to IP's success is its reliance on a fast Linear Programming (LP) solver providing solutions during the search to the corresponding relaxed problems. These solutions are used to guide the search within IP as well as a means of detecting infeasibility and integrality. This paper shows that there is scope also to include LP within the CP framework, in order to similarly guide the CP search. The problems examined here are one for which CP on its own had proved markedly inferior to IP. Hence a hybrid solver based on the CP search and using an LP solver is configured and run on these problems. The outcome shows that using the LP solver within the CP search is a valuable addition to the available search strategies. An improved performance over the CP-only strategies is obtained and, further, comparable results are obtained to those from IP. Overall, CP+LP can be considered as a more robust approach than either CP or IP on their own on a variety of combinatorial search problems.     

Blockwise acceleration of alternating least squares for canonical tensor decomposition

The canonical polyadic (CP) decomposition of tensors is one of the most important tensor decompositions. While the well-known alternating least squares (ALS) algorithm is often considered the workhorse algorithm for computing the CP decomposition, it is known to suffer from slow convergence in many cases and various algorithms have been proposed to accelerate it. In this article, we propose a new accelerated ALS algorithm that accelerates ALS in a blockwise manner using a simple momentum-based extrapolation technique and a random perturbation technique. Specifically, our algorithm updates one factor matrix (i.e., block) at a time, as in ALS, with each update consisting of a minimization step that directly reduces the reconstruction error, an extrapolation step that moves the factor matrix along the previous update direction, and a random perturbation step for breaking convergence bottlenecks. Our extrapolation strategy takes a simpler form than the state-of-the-art extrapolation strategies and is easier to implement. Our algorithm has negligible computational overheads relative to ALS and is simple to apply. Empirically, our proposed algorithm shows strong performance as compared to the state-of-the-art acceleration techniques on both simulated and real tensors.     

Developing a dynamic portfolio selection model with a self-adjusted rebalancing method

In this paper, we propose a comprehensive investment strategy for not only selecting but also maintaining an investment portfolio that takes into account changing market conditions. First, we implement a dynamic portfolio selection model (DPSM) that uses a time-varying investment target according to market forecasts. We then develop a self-adjusted rebalancing (SAR) method to assess the portfolio’s relevance to current market conditions, and further identify the appropriate timing for rebalancing the portfolio. We then integrate the DPSM and SAR into a comprehensive investment strategy, and develop an adaptive learning heuristic for determining the parameter of the proposed investment strategy. We further evaluate the performance of the proposed investment strategy by simulating investments with historical stock return data from different markets around the world, across a period of 10 years. The SAR Portfolio, maintained according to the proposed investment strategy, showed superior performance compared with benchmarks in each of the target markets.     

Tournament Competition and its Merits for Coevolutionary Algorithms

In a competitive coevolutionary algorithm, the competition strategy, selecting opposing individuals, has a great influence on the performance of the algorithm. Therefore, a good competition strategy is crucial for an effective and efficient competitive coevolutionary algorithm. In this paper, we propose a new competition strategy called tournament competition. We investigate its characteristics and merits when applied to adversarial problems. To verify the performance of the new strategy, we first classify adversarial problems into two types: solution-test problems and game problems. We apply the strategy to both types. A set of experiments compares our strategy to several existing competition strategies and analyzes several aspects such as solution quality, evolution speed, and coevolutionary balance. The experimental results indicate that some of the existing competition strategies give different patterns according to problem types. The results also support that the proposed tournament strategy has the potential for finding good solutions, regardless of problem types.     

Efficient mesh selection for collocation methods applied to singular BVPs

We describe a mesh selection strategy for the numerical solution of boundary value problems for singular ordinary differential equations. This mesh adaptation procedure is implemented in our MATLAB code sbvp which is based on polynomial collocation. We prove that under realistic assumptions our mesh selection strategy serves to approximately equidistribute the global error of the collocation solution, thus enabling to reach prescribed tolerances efficiently. Moreover, we demonstrate that this strategy yields a favorable performance of the code and compare its computational effort with other implementations of polynomial collocation.     

On the complete pivoting conjecture for Hadamard matrices: further progress and a good pivots property

Further progress is achieved for the growth conjecture for Hadamard matrices. It is proved that the leading principal minors of a CP Hadamard matrix form an increasing sequence. Bounds for the sixth and seventh pivot of any CP Hadamard matrix are given. A new proof demonstrating that the growth of a Hadamard matrix of order 12 is 12, is presented. Moreover, a new notion of good pivots is introduced and its importance for the study of the growth problem for CP Hadamard matrices is examined. We establish that CP Hadamard matrices with good pivots satisfy Cryer’s growth conjecture with equality, namely their growth factor is equal to their order. A construction of an infinite class of Hadamard matrices is proposed.     

Copositive Programming via Semi-Infinite Optimization

Copositive programming (CP) can be regarded as a special instance of linear semi-infinite programming (SIP). We study CP from the viewpoint of SIP and discuss optimality and duality results. Different approximation schemes for solving CP are interpreted as discretization schemes in SIP. This leads to sharp explicit error bounds for the values and solutions in dependence on the mesh size. Examples illustrate the structure of the original program and the approximation schemes.     

Separating doubly nonnegative and completely positive matrices

The cone of Completely Positive (CP) matrices can be used to exactly formulate a variety of NP-Hard optimization problems. A tractable relaxation for CP matrices is provided by the cone of Doubly Nonnegative (DNN) matrices; that is, matrices that are both positive semidefinite and componentwise nonnegative. A natural problem in the optimization setting is then to separate a given DNN but non-CP matrix from the cone of CP matrices. We describe two different constructions for such a separation that apply to 5 × 5 matrices that are DNN but non-CP. We also describe a generalization that applies to larger DNN but non-CP matrices having block structure. Computational results illustrate the applicability of these separation procedures to generate improved bounds on difficult problems.     

On the spectral problem for trivariate functions

Using a variational approach applied to generalized Rayleigh functionals, we extend the concepts of singular values and singular functions to trivariate functions defined on a rectangular parallelepiped. We also consider eigenvalues and eigenfunctions for trivariate functions whose domain is a cube. For a general finite-rank trivariate function, we describe an algorithm for computing the canonical polyadic (CP) decomposition, provided that the CP factors are linearly independent in two variables. All these notions are computed using Chebfun3; a part of Chebfun for numerical computing with 3D functions. Application in finding the best rank-1 approximation of trivariate functions is investigated. We also prove that if the function is analytic and two-way orthogonally decomposable (odeco), then the CP values decay geometrically, and optimal finite-rank approximants converge at the same rate.     

An improved vertex enumeration algorithm

The main computational burden in pivoting methods for determining all vertices of a convex polytope appears to be in testing pairs of vertices for adjacency. We show how, in the Dyer-Proll algorithm, this burden can be reduced by a new labelling of the search tree and by a mechanism for removing redundant branches. We also introduce an implementation strategy, the barred pivot strategy, which further improves the algorithm's performance.     

An examination of HMM‐based investment strategies for asset allocation

We develop and analyse investment strategies relying on hidden Markov model approaches. In particular, we use filtering techniques to aid an investor in his decision to allocate all of his investment fund to either growth or value stocks at a given time. As this allows the investor to switch between growth and value stocks, we call this first strategy a switching investment strategy. This switching strategy is compared with the strategies of purely investing in growth or value stocks by tracking the quarterly terminal wealth of a hypothetical portfolio for each strategy. Using the data sets on Russell 3000 growth index and Russell 3000 value index compiled by Russell Investment Services for the period 1995–2008, we find that the overall risk‐adjusted performance of the switching strategy is better than that of solely investing in either one of the indices. We also consider a second strategy referred to as a mixed investment strategy which enables the investor to allocate an optimal proportion of his investment between growth and value stocks given a level of risk aversion. Numerical demonstrations are provided using the same data sets on Russell 3000 growth and value indices. The switching investment strategy yields the best or second best Sharpe ratio as compared with those obtained from the pure index strategies and mixed strategy in 14 intervals. The performance of the mixed investment strategy under the HMM setting is also compared with that of the classical mean–variance approach. To make the comparison valid, we choose the same level of risk aversion for each set‐up. Our findings show that the mixed investment strategy within the HMM framework gives higher Sharpe ratios in 5 intervals of the time series than that given by the standard mean–variance approach. The calculated weights through time from the strategy incorporating the HMM set‐up are more stable. A simulation analysis further shows a higher performance stability of the HMM strategies compared with the pure strategies and the mean–variance strategy. Copyright © 2009 John Wiley & Sons, Ltd.     

Invariants for normal completely positive maps on the hyperfinite II1 factor

We investigate certain classes of normal completely positive (CP) maps on the hyperfinite II₁ factorA. Using the representation theory of a suitable irrational rotation algebra, we propose some computable invariants for such CP maps. Dedicated to Professor K B Sinha     

Performance evaluation of distribution strategies for the inventory routing problem

Direct shipping strategy is an easy-to-implement distribution strategy frequently used in industrial distribution systems. In this paper, an analytic method is developed for performance evaluation of the strategy for the infinite horizon inventory routing problem with delivery frequency constraint. With the method, the effectiveness of direct shipping strategy can be represented as a function of some system parameters. We demonstrate that the effectiveness of direct shipping is at least the square root of the smallest utilization ratio of vehicle capacity. This implies that the effectiveness of the strategy can reach 100% (respectively, 94.86%) whenever the demand rate of each retailer is 100% (respectively, 90%) of the vehicle capacity multiplied by the upper bound of the delivery frequency. This insight can help a firm answer questions such as: under what conditions direct shipping strategy is effective and why, and how effective the strategy is under a specific condition? In case direct shipping strategy is proven ineffective, a more general Fixed Partition Policy (FPP) that combines direct shipping strategy and multiple-stop shipping strategy must be used. An analytic method is also developed for performance evaluation of general FPPs. We demonstrate that the effectiveness of an FPP depends on the total demand rate of the retailers in each partition (each retailer set) and their closeness level. This insight provides a useful guideline to the design of effective FPPs. The analytic methods make the performance improvement of a distribution system possible through adjusting its system parameters.     

Crew Assignment via Constraint Programming: Integrating Column Generation and Heuristic Tree Search

The Airline Crew Assignment Problem (ACA) consists of assigning lines of work to a set of crew members such that a set of activities is partitioned and the costs for that assignment are minimized. Especially for European airline companies, complex constraints defining the feasibility of a line of work have to be respected. We developed two different algorithms to tackle the large scale optimization problem of Airline Crew Assignment. The first is an application of the Constraint Programming (CP) based Column Generation Framework. The second approach performs a CP based heuristic tree search. We present how both algorithms can be coupled to overcome their inherent weaknesses by integrating methods from Constraint Programming and Operations Research. Numerical results show the superiority of the hybrid algorithm in comparison to CP based tree search and column generation alone.     

A constraint programming-based approach to the crew scheduling problem of the Taipei mass rapid transit system

This paper addresses the crew scheduling problem for a mass rapid transit (MRT) system. The problem is to find a minimum number of duties to cover all tasks while satisfying all the hard and soft scheduling rules. Such rules are complicated in real-world operations and difficult to follow through optimization methods alone. In this paper, we propose a constraint programming (CP)-based approach to solve the problem. The approach involves a CP model for duty generation, a set covering problem model for duty optimization, and alternative ways to identify the final solution in different situations. We applied the proposed CP-based approach to solve a case problem for the Taipei MRT. Case application results using real-world data showed that our approach is capable of reducing the number of daily duties from 58 to 55 and achieving a 5.2 % savings in labor costs. We also incorporated the soft rule considerations into the CP model in order to generate alternative optimum solutions that would improve the workload balance. The coefficient of variation of the work time distribution improves significantly, falling from 21 % to approximately 5 %. Given the CP model’s comprehensive coverage of various scheduling rules, our proposed approach and models would also be applicable to other MRT systems.     

复射影空间中子流形的Gauss映照

本文利用复射影空间到欧氏空间的第一标准嵌入，对于复射影空间的子流形建立了一种广义的Ｇａｕｓｓ映照，并给出了这种广义的Ｇａｕ８ｓ映照是调和映照和相对仿射映照的条件。     

Mixed strategies in maximin testing of robust stabilization performance

We consider algorithms for testing robust stabilization performance for bilinear systems of special form, discrete-continuous systems of control of a dynamic object. We present an example of synthesis of a mixed testing strategy in the space module-orbital station rendezvous problem.