Author name cluster

Jinkun Lin

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers

2 author rows

AIJ Journal 2025 Journal Article

Local-MIP: Efficient local search for mixed integer programming

Peng Lin
Shaowei Cai
Mengchuan Zou
Jinkun Lin

Mixed Integer Programming (MIP) is a fundamental model in operations research with broad industrial applications. Local search is a powerful methodology for solving complex optimization problems; however, the development of local search algorithms for MIP still needs exploration. In this work, we propose Local-MIP, an efficient local search algorithm tailored for MIP that integrates novel operators and employs a two-mode architecture to adaptively apply operators based on the current solution's feasibility. For the feasible mode, we propose the lift move operator and a corresponding lift process to improve the objective value while maintaining feasibility. For the infeasible mode, we propose the breakthrough move and mixed tight move operators to respectively optimize the objective function and satisfy constraints. To apply operators intelligently, we develop a dynamic weighting scheme that balances the priorities of the objective function and constraints. Furthermore, we propose a two-level scoring function structure that hierarchically selects operations, guiding the search toward high-quality feasible solutions. Experiments are conducted on public benchmarks to compare Local-MIP with state-of-the-art MIP solvers in finding high-quality solutions. The results show that Local-MIP significantly outperforms CPLEX, HiGHS, SCIP, and Feasibility Jump while remaining competitive with the commercial solver Gurobi on challenging problems within short time limits. Moreover, Local-MIP establishes 10 new records on MIPLIB open instances.

Details DOI

ICML Conference 2022 Conference Paper

Measuring the Effect of Training Data on Deep Learning Predictions via Randomized Experiments

Jinkun Lin
Anqi Zhang
Mathias Lécuyer
Jinyang Li 0001
Aurojit Panda
Siddhartha Sen 0001

We develop a new, principled algorithm for estimating the contribution of training data points to the behavior of a deep learning model, such as a specific prediction it makes. Our algorithm estimates the AME, a quantity that measures the expected (average) marginal effect of adding a data point to a subset of the training data, sampled from a given distribution. When subsets are sampled from the uniform distribution, the AME reduces to the well-known Shapley value. Our approach is inspired by causal inference and randomized experiments: we sample different subsets of the training data to train multiple submodels, and evaluate each submodel’s behavior. We then use a LASSO regression to jointly estimate the AME of each data point, based on the subset compositions. Under sparsity assumptions ($k \ll N$ datapoints have large AME), our estimator requires only $O(k\log N)$ randomized submodel trainings, improving upon the best prior Shapley value estimators.

Details

JAIR Journal 2021 Journal Article

A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs

Shaowei Cai
Jinkun Lin
Yiyuan Wang
Darren Strash

This paper explores techniques to quickly solve the maximum weight clique problem (MWCP) in very large scale sparse graphs. Due to their size, and the hardness of MWCP, it is infeasible to solve many of these graphs with exact algorithms. Although recent heuristic algorithms make progress in solving MWCP in large graphs, they still need considerable time to get a high-quality solution. In this work, we focus on solving MWCP for large sparse graphs within a short time limit. We propose a new method for MWCP which interleaves clique finding with data reduction rules. We propose novel ideas to make this process efficient, and develop an algorithm called FastWClq. Experiments on a broad range of large sparse graphs show that FastWClq finds better solutions than state-of-the-art algorithms while the running time of FastWClq is much shorter than the competitors for most instances. Further, FastWClq proves the optimality of its solutions for roughly half of the graphs, all with at least 105 vertices, with an average time of 21 seconds.

PDF Details DOI

IJCAI Conference 2020 Conference Paper

NuCDS: An Efficient Local Search Algorithm for Minimum Connected Dominating Set

Bohan Li
Xindi Zhang
Shaowei Cai
Jinkun Lin
Yiyuan Wang
Christian Blum

The minimum connected dominating set (MCDS) problem is an important extension of the minimum dominating set problem, with wide applications, especially in wireless networks. Despite its practical importance, there are few works on solving MCDS for massive graphs, mainly due to the complexity of maintaining connectivity. In this paper, we propose two novel ideas, and develop a new local search algorithm for MCDS called NuCDS. First, a hybrid dynamic connectivity maintenance method is designed to switch alternately between a novel fast connectivity maintenance method based on spanning tree and its previous counterpart. Second, we define a new vertex property called \emph{safety} to make the algorithm more considerate when selecting vertices. Experiments show that NuCDS significantly outperforms the state-of-the-art MCDS algorithms on both massive graphs and classic benchmarks.

PDF Details DOI

IJCAI Conference 2018 Conference Paper

Improving Local Search for Minimum Weight Vertex Cover by Dynamic Strategies

Shaowei Cai
Wenying Hou
Jinkun Lin
Yuanjie Li

The minimum weight vertex cover (MWVC) problem is an important combinatorial optimization problem with various real-world applications. Due to its NP hardness, most works on solving MWVC focus on heuristic algorithms that can return a good quality solution in reasonable time. In this work, we propose two dynamic strategies that adjust the behavior of the algorithm during search, which are used to improve a state of the art local search for MWVC named FastWVC, resulting in two local search algorithms called DynWVC1 and DynWVC2. Previous MWVC algorithms are evaluated on graphs with random or hand crafted weights. In this work, we evaluate the algorithms on the vertex weighted graphs that obtained from an important real world problem, the map labeling problem. Experiments show that our algorithm obtains better results than previous algorithms for MWVC and maximum weight independent set (MWIS) on these real world instances. We also test our algorithms on massive graphs studied in previous works, and show significant improvements there.

PDF Details

IJCAI Conference 2017 Conference Paper

A Reduction based Method for Coloring Very Large Graphs

Jinkun Lin
Shaowei Cai
Chuan Luo
Kaile Su

The graph coloring problem (GCP) is one of the most studied NP hard problems and has numerous applications. Despite the practical importance of GCP, there are limited works in solving GCP for very large graphs. This paper explores techniques for solving GCP on very large real world graphs. We first propose a reduction rule for GCP, which is based on a novel concept called degree bounded independent set. The rule is iteratively executed by interleaving between lower bound computation and graph reduction. Based on this rule, we develop a novel method called FastColor, which also exploits fast clique and coloring heuristics. We carry out experiments to compare our method FastColor with two best algorithms for coloring large graphs we could find. Experiments on a broad range of real world large graphs show the superiority of our method. Additionally, our method maintains both upper bound and lower bound on the optimal solution, and thus it proves an optimal solution when the upper bound meets the lower bound. In our experiments, it proves the optimal solution for 97 out of 142 instances.

PDF Details

JAIR Journal 2017 Journal Article

Finding A Small Vertex Cover in Massive Sparse Graphs: Construct, Local Search, and Preprocess

Shaowei Cai
Jinkun Lin
Chuan Luo

The problem of finding a minimum vertex cover (MinVC) in a graph is a well known NP-hard combinatorial optimization problem of great importance in theory and practice. Due to its NP-hardness, there has been much interest in developing heuristic algorithms for finding a small vertex cover in reasonable time. Previously, heuristic algorithms for MinVC have focused on solving graphs of relatively small size, and they are not suitable for solving massive graphs as they usually have high-complexity heuristics. This paper explores techniques for solving MinVC in very large scale real-world graphs, including a construction algorithm, a local search algorithm and a preprocessing algorithm. Both the construction and search algorithms are based on low-complexity heuristics, and we combine them to develop a heuristic algorithm for MinVC called FastVC. Experimental results on a broad range of real-world massive graphs show that, our algorithms are very fast and have better performance than previous heuristic algorithms for MinVC. We also develop a preprocessing algorithm to simplify graphs for MinVC algorithms. By applying the preprocessing algorithm to local search algorithms, we obtain two efficient MinVC solvers called NuMVC2+p and FastVC2+p, which show further improvement on the massive graphs.

PDF Details DOI

IJCAI Conference 2016 Conference Paper

Fast Solving Maximum Weight Clique Problem in Massive Graphs

Shaowei Cai
Jinkun Lin

This paper explores techniques for fast solving the maximum weight clique problem (MWCP) in very large scale real-world graphs. Because of the size of such graphs and the intractability of MWCP, previously developed algorithms may not be applicable. Although recent heuristic algorithms make progress in solving MWCP in massive graphs, they still need considerable time to get a good solution. In this work, we propose a new method for MWCP which interleaves between clique construction and graph reduction. We also propose three novel ideas to make it efficient, and develop an algorithm called FastWClq. Experiments on massive graphs from various applications show that, FastWClq finds better solutions than state of the art algorithms while the run time is much less. Further, FastWClq proves the optimal solution for about half of the graphs in an averaged time less than one second.

PDF Details

AIJ Journal 2016 Journal Article

New local search methods for partial MaxSAT

Shaowei Cai
Chuan Luo
Jinkun Lin
Kaile Su

Maximum Satisfiability (MaxSAT) is the optimization version of the Satisfiability (SAT) problem. Partial Maximum Satisfiability (PMS) is a generalization of MaxSAT which involves hard and soft clauses and has important real world applications. Local search is a popular approach to solving SAT and MaxSAT and has witnessed great success in these two problems. However, unfortunately, local search algorithms for PMS do not benefit much from local search techniques for SAT and MaxSAT, mainly due to the fact that it contains both hard and soft clauses. This feature makes it more challenging to design efficient local search algorithms for PMS, which is likely the reason of the stagnation of this direction in more than one decade. In this paper, we propose a number of new ideas for local search for PMS, which mainly rely on the distinction between hard and soft clauses. The first three ideas, including weighting for hard clauses, separating hard and soft score, and a variable selection heuristic based on hard and soft score, are used to develop a local search algorithm for PMS called Dist. The fourth idea, which uses unit propagation with priority on hard unit clauses to generate the initial assignment, is used to improve Dist on industrial instances, leading to the DistUP algorithm. The effectiveness of our solvers and ideas is illustrated through experimental evaluations on all PMS benchmarks from the MaxSAT Evaluation 2014. According to our experimental results, Dist shows a significant improvement over previous local search solvers on all benchmarks. We also compare our solvers with state-of-the-art complete PMS solvers and a state-of-the-art portfolio solver, and the results show that our solvers have better performance in random and crafted instances but worse in industrial instances. The good performance of Dist has also been confirmed by the fact that Dist won all random and crafted categories of PMS and Weighted PMS in the incomplete solvers track of the MaxSAT Evaluation 2014.

Details DOI

AAAI Conference 2015 Conference Paper

Two Weighting Local Search for Minimum Vertex Cover

Shaowei Cai
Jinkun Lin
Kaile Su

Minimum Vertex Cover (MinVC) is a well known NP-hard combinatorial optimization problem, and local search has been shown to be one of the most effective approaches to this problem. State-of-the-art MinVC local search algorithms employ edge weighting techniques and prefer to select vertices with higher weighted score. These algorithms are not robust and especially have poor performance on instances with structures which defeat greedy heuristics. In this paper, we propose a vertex weighting scheme to address this shortcoming, and combine it within the current best MinVC local search algorithm NuMVC, leading to a new algorithm called TwMVC. Our experiments show that TwMVC outperforms NuMVC on the standard benchmarks namely DIMACS and BHOSLIB. To the best of our knowledge, TwMVC is the first MinVC algorithm that attains the best known solution for all instances in both benchmarks. Further, TwMVC shows superiority on a benchmark of real-world networks.

PDF Details