Parallel Construction Heuristic Combined with Constraint Propagation for the Car Sequencing Problem

For the car sequencing（CS） problem, the draw-backs of the ＂sliding windows＂ technique used in the objective function have not been rectified, and no high quality initial solution has been acquired to accelerate the improvement of the solution quality. Firstly, the objective function is improved to solve the double and bias counting of violations broadly discussed. Then, a new method combining heuristic with constraint propagation is proposed which constructs initial solutions under a parallel framework. Based on constraint propagation, three filtering rules are designed to intersecting with three greedy functions, so the variable domain is narrowed in the process of the construction. The parallel framework is served to show its robustness in terms of the quality of the solution since it greatly increases the performance of obtaining the best solution. In the computational experiments, 109 instances of 3 sets from the CSPLib＇ s benchmarks are used to test the performance of the proposed method. Experiment results show that the proposed method outperforms others in acquiring the best-known results for 85 best-known results of 109 are obtained with only one construction. The proposed research provides an avenue to remedy the deficiencies of ＂sliding windows＂ technique and construct high quality initial solutions.

Pairwise constraint propagation via low-rank matrix recovery

As a kind of weaker supervisory information, pairwise constraints can be exploited to guide the data analysis process, such as data clustering. This paper formulates pairwise constraint propagation, which aims to predict the large quantity of unknown constraints from scarce known constraints, as a low-rank matrix recovery(LMR) problem. Although recent advances in transductive learning based on matrix completion can be directly adopted to solve this problem, our work intends to develop a more general low-rank matrix recovery solution for pairwise constraint propagation, which not only completes the unknown entries in the constraint matrix but also removes the noise from the data matrix. The problem can be effectively solved using an augmented Lagrange multiplier method. Experimental results on constrained clustering tasks based on the propagated pairwise constraints have shown that our method can obtain more stable results than state-of-the-art algorithms,and outperform them.