integer linear programming

Solving TSPs to Optimality with Integer Linear Programming in Python

Posted on 28. August 202428. August 2024 by Fabian Leuthold

In this post we will learn how to optimally solve the TSP problem using integer linear programming using Google OR-Tools for mathmatical modelling in Python. In previous posts I have already presented two ways of solving the TSP using heuristic approaches: Construct solutions using the Nearest Neighbor construction heuristic and improve solutions using the 2-opt… Read more Solving TSPs to Optimality with Integer Linear Programming in Python

How to Develop a Sudoku Solver Using Mixed Integer Linear Programming

Posted on 8. December 20238. December 2023 by Fabian Leuthold

In today’s blog post, let’s dive into the fascinating realm of solving Sudoku puzzles using Mixed Integer Linear Programming (MILP). Check this previous post to see how a sudoku solver can be developed in python using dynamic programming and backtracking. Sudoku, a classic logic-based number placement puzzle, has long captivated minds around the globe with… Read more How to Develop a Sudoku Solver Using Mixed Integer Linear Programming

Vertex Coloring using ILP

Posted on 7. August 20237. August 2023 by Fabian Leuthold

In this post I’ll show you how to solve the vertex coloring problem to optimality using linear programming. Since the problem is NP-complete, there is no algorithm which can solve any problem instance in deterministic polynomial time. In a former post, I used constraint programming to find an optimal (minimal) vertex coloring. A popular greedy… Read more Vertex Coloring using ILP