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 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 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
In this post I’ll demonstrate the results of my most recent fun project on the micro:bit: An app to solve Happy Cubes®, a set of puzzles created in 1986 by the Belgian toy inventor Dirk Laureyssens. My kids were playing with these cubes and I was wondering, if the micro:bit could solve these cubes in… Read more Solving Happy Cubes® on A micro:bit
This is a similar post as the one on Graph Coloring. However, this in this post I show an application of the graph coloring problem, allowing us to answer practical questions using graph theory. In this post we’ll first tackle a map coloring problem manually, then we’ll use a MiniZinc constraint programming script to validate the solution found.