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 develop a construction heuristic to generate a first solution to the Traveling Salesman Problem (TSP). This is a simple heuristic which starts from an arbitrarily chosen location and then visits the nearest neighbor until all nodes have been visited. Finally, the tour is completed by returning to the starting node. Problem… Read more Construct TSP Solutions with the Nearest Neighbor Heuristic
When developing software prototypes to optimize linear problems, it is sometimes desirable to provide the customer with an app to avoid the need for them to install a full python environment with all dependencies. In python, there is a tool called PyInstaller for this purpose. However, there are a few hurdles that need to be… Read more Generate EXEs solving MILPs using PyInstaller in Python
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