Complexity and Algorithms in Graphs
1.5K papers on this topic
Multi-Task Learning for Routing Problem with Cross-Problem Zero-Shot Generalization
Vehicle routing problems (VRPs), which can be found in numerous real-world applications, have been an important research topic for several decades. Recently, the neural combinatorial optimization...
LinSATNet: The Positive Linear Satisfiability Neural Networks
Encoding constraints into neural networks is attractive. This paper studies how to introduce the popular positive linear satisfiability to neural networks. We propose the first differentiable...
On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective
Graph Neural Networks (GNNs) have become the standard approach for learning and reasoning over relational data, leveraging the message-passing mechanism that iteratively propagates node embeddings...
LLM-Guided Evolution of Symbolic Acceleration Inequality Families for MILP
Integer programming (IP) is central to many combinatorial optimization tasks but remains challenging due to its NP-hard nature. A practical way to improve IP solvers is to manually design...
MAC Advice for Facility Location Mechanism Design
Algorithms with predictions have attracted much attention in the last years across various domains, including variants of facility location, as a way to surpass traditional worst-case analyses. We...
Effective anytime algorithm for multiobjective combinatorial optimization problems
In multiobjective optimization, the result of an optimization algorithm is a set of efficient solutions from which the decision maker selects one. It is common that not all the efficient solutions...
Neural Solver Selection for Combinatorial Optimization
Machine learning has increasingly been employed to solve NP-hard combinatorial optimization problems, resulting in the emergence of neural solvers that demonstrate remarkable performance, even...
Improving Existing Optimization Algorithms with LLMs
The integration of Large Language Models (LLMs) into optimization has created a powerful synergy, opening exciting research opportunities. This paper investigates how LLMs can enhance existing...
Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer
Recently, Transformer has become a prevailing deep architecture for solving vehicle routing problems (VRPs). However, it is less effective in learning improvement models for VRP because its...
Learning to Stop Cut Generation for Efficient Mixed-Integer Linear Programming
Cutting planes (cuts) play an important role in solving mixed-integer linear programs (MILPs), as they significantly tighten the dual bounds and improve the solving performance. A key problem for...
Efficient $k$-Clique Listing: An Edge-Oriented Branching Strategy
$k$-clique listing is a vital graph mining operator with diverse applications in various networks. The state-of-the-art algorithms all adopt a branch-and-bound (BB) framework with a...
Demystifying Graph Sparsification Algorithms in Graph Properties Preservation
Graph sparsification is a technique that approximates a given graph by a sparse graph with a subset of vertices and/or edges. The goal of an effective sparsification algorithm is to maintain...
Solving Mixed Integer Programs Using Neural Networks
Mixed Integer Programming (MIP) solvers rely on an array of sophisticated heuristics developed with decades of research to solve large-scale MIP instances encountered in practice. Machine learning...
Learning to Compare Nodes in Branch and Bound with Graph Neural Networks
Branch-and-bound approaches in integer programming require ordering portions of the space to explore next, a problem known as node comparison. We propose a new siamese graph neural network model...
Reinforced Lin-Kernighan-Helsgaun Algorithms for the Traveling Salesman Problems
TSP is a classical NP-hard combinatorial optimization problem with many practical variants. LKH is one of the state-of-the-art local search algorithms for the TSP. LKH-3 is a powerful extension of...
Hierarchical Learning-based Graph Partition for Large-scale Vehicle Routing Problems
Neural solvers based on the divide-and-conquer approach for Vehicle Routing Problems (VRPs) in general, and capacitated VRP (CVRP) in particular, integrates the global partition of an instance...
Learning to Delegate for Large-scale Vehicle Routing
Vehicle routing problems (VRPs) form a class of combinatorial problems with wide practical applications. While previous heuristic or learning-based works achieve decent solutions on small problem...
A Fast Algorithm for Moderating Critical Nodes via Edge Removal
Critical nodes in networks are extremely vulnerable to malicious attacks to trigger negative cascading events such as the spread of misinformation and diseases. Therefore, effective moderation of...