yet another source of inspiration…
In this post, we’re developing a Happy Cube solver using a mixed integer linear program (MILP). Previously, we tackled this problem on a micro:bit using dynamic programming and backtracking. Now, we’re trying a different approach by creating a mathematical model to solve this combinatorial challenge. The idea is to structure the MILP so that it… Read more A MILP based Happy Cube©® Solver
A common problem in production scheduling involves distributing jobs of varying durations across multiple identical machines to minimize the time when the last job finishes. In other words, the goal is to minimize the makespan. Production Planning Problem Instances The following list presents some instances of the makespan minimization problem. It involves a set number… Read more How to Construct Solutions to the Production Planning Problem
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
In this post, we’ll learn how to improve TSP tours using a well known and approved local search improvement heuristic approach. These improvement heuristics start with an initial solution and iteratively improve it until no further improvement is possible, then return the best solution found. Previously, we discussed how to generate initial solutions for TSP… Read more How to Improve TSP-Tours Applying the 2-opt Neighborhood
The bin packing problem is a combinatorial optimization problem in which items of different sizes must be packed into a number of containers with a fixed capacity in such a way that the number of containers used is minimized. This website of the lamarr-institute provides a nice and clear explanation of the bin-packing problem and… Read more How to construct Solutions to the Bin Packing Problem
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
In this post, we’ll develop a construction heuristic to build reasonable (start) solutions for the knapsack problem. Why use Construction Heuristics? Construction heuristics offer the advantage of quickly leading to acceptable solutions. Unlike more complex optimization algorithms, they are easy to implement and require less computational power. These heuristics are particularly well-suited for handling large… Read more The use of Construction Heuristics
In the world of Operations Research and Optimization, solving complex problems efficiently is a constant pursuit. One such problem that has intrigued researchers and practitioners alike is the Knapsack Problem. In this blog post, we’ll delve into the fascinating realm of metaheuristics and guide you through the step-by-step process of applying these technique to tackle… Read more A Metaheuristic Approach to Solving The Knapsack Problem
In the dynamic world of Python scripting, efficiency is key. Today, let’s delve into the transformative realm of parallelization using Numba’s JIT (Just-In-Time) compiler. Brace yourselves as we explore how this powerful tool not only compiles your code on the fly but also paves the way for parallel execution. Join us on a journey to harness the full potential of your Python scripts through the magic of Numba’s parallelization capabilities.
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