Andrew Lim

EAAI Journal 2022 Journal Article

Learning variable ordering heuristics for solving Constraint Satisfaction Problems

• Wen Song
• Zhiguang Cao
• Jie Zhang
• Chi Xu
• Andrew Lim

Backtracking search algorithms are often used to solve the Constraint Satisfaction Problem (CSP), which is widely applied in various domains such as automated planning and scheduling. The efficiency of backtracking search depends greatly on the variable ordering heuristics. Currently, the most commonly used heuristics are hand-crafted based on expert knowledge. In this paper, we propose a deep reinforcement learning based approach to automatically discover new variable ordering heuristics that are better adapted for a given class of CSP instances, without the need of relying on hand-crafted features and heuristics. We show that directly optimizing the search tree size is not convenient for learning, and propose to optimize the expected cost of reaching a leaf node in the search tree. To capture the complex relations among the variables and constraints, we design a representation scheme based on Graph Neural Network that can process CSP instances with different sizes and constraint arities. Experimental results on random CSP instances show that on small and medium sized instances, the learned policies outperform classical hand-crafted heuristics with smaller search tree (up to 10. 36% reduction). Moreover, without further training, our policies directly generalize to instances of larger sizes and much harder to solve than those in training, with even larger reduction in the search tree size (up to 18. 74%).

NeurIPS Conference 2020 Conference Paper

Digraph Inception Convolutional Networks

• Zekun Tong
• Yuxuan Liang
• Changsheng Sun
• Xinke Li
• David Rosenblum
• Andrew Lim

Graph Convolutional Networks (GCNs) have shown promising results in modeling graph-structured data. However, they have difficulty with processing digraphs because of two reasons: 1) transforming directed to undirected graph to guarantee the symmetry of graph Laplacian is not reasonable since it not only misleads message passing scheme to aggregate incorrect weights but also deprives the unique characteristics of digraph structure; 2) due to the fixed receptive field in each layer, GCNs fail to obtain multi-scale features that can boost their performance. In this paper, we theoretically extend spectral-based graph convolution to digraphs and derive a simplified form using personalized PageRank. Specifically, we present the Digraph Inception Convolutional Networks (DiGCN) which utilizes digraph convolution and kth-order proximity to achieve larger receptive fields and learn multi-scale features in digraphs. We empirically show that DiGCN can encode more structural information from digraphs than GCNs and help achieve better performance when generalized to other models. Moreover, experiments on various benchmarks demonstrate its superiority against the state-of-the-art methods.

IJCAI Conference 2011 Conference Paper

Space Defragmentation Heuristic for 2D and 3D Bin Packing Problems

• Zhaoyi Zhang
• Songshan Guo
• Wenbin Zhu
• Wee-Chong Oon
• Andrew Lim

One of main difficulties of multi-dimensional packing problems is the fragmentation of free space into several unusable small parts after a few items are packed. This study proposes a defragmentation technique to combine the fragmented space into a continuous usable space, which potentially allows the packing of additional items. We illustrate the effectiveness of this technique on the two- and three-dimensional Bin Packing Problems. In conjunction with a bin shuffling strategy for incremental improvement, our resultant algorithm outperforms all leading meta-heuristic approaches.

AAAI Conference 2010 Conference Paper

The Tree Representation of Feasible Solutions for the TSP with Pickup and Delivery and LIFO Loading

• Dejian Tu
• Songshan Guo
• Hu Qin
• Wee-Chong Oon
• Andrew Lim

The feasible solutions of the traveling salesman problem with pickup and delivery (TSPPD) are represented by vertex lists in existing literature. However, when the TSPPD requires that the loading and unloading operations must be performed in a last-in-first-out (LIFO) manner, we show that its feasible solutions can be represented by trees. Consequently, we develop a variable neighbourhood search (VNS) heuristic for the TSPPD with last-in-first-out loading (TSPPDL) involving several search operators based on the tree data structure. Experiments show that our VNS heuristic is superior to the current best heuristics for TSPPDL in terms of both solution quality and computing time.

TCS Journal 2005 Journal Article

k -Center problems with minimum coverage

• Andrew Lim
• Brian Rodrigues
• Fan Wang
• Zhou Xu

In this work, we study an extension of the k-center facility location problem, where centers are required to service a minimum of clients. This problem is motivated by requirements to balance the workload of centers while allowing each center to cater to a spread of clients. We study three variants of this problem, all of which are shown to be NP -hard. In-approximation hardness and approximation algorithms with factors equal or close to the best lower bounds are provided. Generalizations, including vertex costs and vertex weights, are also studied.

IJCAI Conference 2003 Conference Paper

A New Node Centroid Algorithm for Bandwidth Minimization

• Andrew Lim
• Brian Rodrigues
• Fei Xiao

AAAI Conference 2002 System Paper

UTTSExam: A University Examination Timetable Scheduler

• Andrew Lim
• Wee-Kit Ho

UTTSExam is a university examination timetable-scheduling program that was successfully employed to create the examination timetable for semester 1 of the 2001/2002 academic year in the National University of Singapore. This demonstration provides insight on the various components of the system, including the hybrid centralized cum decentralized scheduling strategy, the Combined Method scheduling algorithm and the overall process required to create the final timetable.

IJCAI Conference 1999 Conference Paper

An Effective Ship Berthing Algorithm

• Andrew Lim