Introduction and Guidelines

This page provides a brief introduction to make you understand how machine learning practices on combinatorial optimization (CO) problems and some guidelines for using ml4co-kit.

Note

For more information on CO problems and technical details, please visit our curated repository awesome-ml4co.

Combinatorial Optimization Problems

  • Traveling Salesman Problem (TSP). The TSP problem requires finding the shortest tour that visits each vertex of the graph exactly once and returns to the starting node.

_images/tsp_problem.png _images/tsp_solution.png

  • Capacitated Vehicle Routing Problem (CVRP). The CVRP is a variant of the vehicle routing problem in which a fleet of vehicles must service a set of customers, subject to vehicle capacity constraints. The goal is to minimize the total route cost while ensuring that no vehicle exceeds its capacity.

_images/cvrp_problem.png _images/cvrp_solution.png

  • Maximum Clique (MCl). The MCl problem involves finding the largest subset of vertices in a graph such that every pair of vertices in the subset is connected by an edge.

_images/mcl_problem.png _images/mcl_solution.png

  • Maximum Cut (MCut). The MCut problem focuses on partitioning the vertices of a graph into two subsets such that the total weight of edges between the two subsets is maximized.

_images/mcut_problem.png _images/mcut_solution.png

  • Maximum Independent Set (MIS). The MIS problem aims to find the largest subset of a graph such that no two vertices in the subset are adjacent.

_images/mis_problem.png _images/mis_solution.png

  • Minimum Vertex Cover (MVC). The MVC problem aims to find the smallest subset of a graph such that every edge in the graph has at least one endpoint in this subset.

_images/mvc_problem.png _images/mvc_solution.png

When to use ML4CO-Kit

In the following situations, you might find the ML4CO-Kit useful:

  • When you need to obtain a baseline by solving CO problems with traditional solvers.

  • When you need to generate training datasets for your models.

  • When you require evaluating your models with open-source or public test datasets.

  • When you are building your models using the PyTorch Lightning architecture.

  • When you utilize wandb for monitoring your training process.

  • When you need visualization of CO problems.

  • When you need to read data from various formats such as tsplib, vrplib, txt, and gpickle.

  • When you need to save data in a portable txt file format.

What’s Next

Please read the How to use ML4CO-Kit guide.

And you can get the development status of each component in the