What is CP?
CP is Constraint Programming. It is not exactly a technology in itself, although there are implementations that are based on CP, nor a programming language. It is rather a paradigm where the relationships between the variables are expressed in terms of constraints (equations). It is a way of approaching the solution of very specific, although very common problems in various aspects of real life, of which we will see some examples.
It has points of contact with operational research, artificial intelligence, and computational calculation.
The focus is on the problem and the restrictions that a proposed solution must overcome in order to be considered, over the explicit declaration of solutions to the problems that are intended to be addressed. A finite set of constraints is defined and it moves towards the best candidate solution to the problem from a very broad set of possible solutions (feasibility).
Within the architecture of the solution that is designed for a specific problem, not all the components are necessarily solved with CP. Usually, there will be at least components that transfer what is required to the CP Solver, the data of the problem to be solved, and other components that present the solution or solutions that it proposes. The created model will not necessarily tackle the whole problem. A good practice we found to be very effective in our projects is to create an abstraction layer that will interact with it. This allows us to keep the model lean and simple, making the iterative development fast and precise.
What kind of projects does it apply to?
Solvable projects with CP or even more combinatorial optimization in the operational and business fields are those where we have a large and complex number of restrictions and a limited number of resources to use.
Let’s see some examples to get a better understanding:
Route calculation: Search for the best routes for freight vehicles to pick up and deliver packages following certain rules and limitations (ex: “the truck cannot carry more than 1 ton of cargo”, or “all deliveries must be completed in less than 2 hours”).
Planning: Find the best plan for a complex set of tasks, which must be performed in a certain order of priority, on a limited set of machines or other resources.
Packaging in containers: Pack as many objects of various sizes as possible into a limited number of containers with limited capacities.
Let’s go in a little more detail…
Employee schedule planning
Let’s take as an example a factory that operates 24×7 and needs to implement weekly planning for its employees:
- It has a scheme of 3 shifts of 8 hours each
- 4 employees to assign
- 3 employees are assigned per day, at different daily shifts
- the 4th employee has the day off
Even in a reduced scheme like this, the possible combinations for very large planning are as follows: there are 24 possible assignments per day (4!) so the number of assignments of the week is 247 combinations (> 4.5 billion)
Actually, there are many restrictions that limit the number of possible solutions, for example:
- each employee works a limited number of days of the week
- an employee cannot work more than 8 hours in a row
CP allows the possible solutions to be sustained as restrictions are added to the problem, which makes CP a powerful tool to solve this type of problem, meaning real-life problems.
Calculating the best route
The problem to be solved is to build routes to cover a set of N-defined “nodes”, minimizing the total cost of the route (which is calculated as the sum of all the distances of each segment of the route). To do so, some restrictions must be respected, both on the route, at the nodes, or even for the vehicles themselves.
We name a specific location “node” (city, local / branch, building, etc.) and “path” to the route that connects nodes, starting and ending at predefined nodes.
Some cases to which it applies are:
- package delivery companies, looking for the best route for their conductors
- cable/telephone companies, looking for the best planning for the visit of their technicians to the customers
- transport companies, looking for the best route to pick up and drop off their passengers (ex. Uber)
A very well-known case is the TSP (Travel Salesman Problem), in which you must find the best route for a seller to visit a list of clients in different geographical points, and return to the origin.
This problem is represented by a graph, where the nodes are the locations, and the lines are the path or routes between each one. Taking as an example a TSP of 4 locations, this would be the graphic representation:
In this case, calculating the distance between nodes (indicated next to each “route”) we see that the best route is A-C-D-B-A with a total cost of 90 (35 + 30 + 15 + 10).
As locations are added the problem becomes more complex: In the case of 4 locations, there are 6 possible routes, but in the case of 10 locations, there would be 362,880 possible routes.
For a small number of locations or nodes, the problem can be solved on a complete tour of all possible routes. As the number of locations increases, problem complexity increases, so an optimization technique becomes necessary, and applying constraints is the answer.
A generalization of TSP is VRP (Vehicle Routing Problem) in which an unlimited number of vehicles can be added. In these scenarios, VRP is usually added with some specific restrictions to the problem:
- TSP — A single vehicle to visit a list of locations
- VRP- A number of N vehicles are added to complete the routes
- VRP with load restriction — Limit of payload for each vehicle
- VRP with time limit — Time restrictions (time window) are added to meet each trip (journey)
- VRP with resource limit — Resource restrictions added to meet each journey (ex: resources to load / download the vehicles)
- VRP with loss of nodes — The possibility of “skipping” locations is added, but with the consequent penalty
What is the benefit of using CP? When to use and when not to use CP?
At Arion, we believe that choosing the right technology/technique is crucial when solving any problem with the software. The wrong choice can lead to the design of disastrous architectures and solutions that do not meet your requirements or that make maintenance almost impossible.
The above-described problems could be solved with imperative or object-oriented programming, but it would be very difficult as well as hard to maintain in terms of the code. Even understanding the code would become more and more confusing when adding new restrictions. You can drown into a cascade of multiple “IF’s” and “ELSE IF’s” impossible to understand/maintain, debug, and so on.
Something similar happens with the data, the relationship between restrictions, resources, and their possible combinations: it leads to the generation of — in some cases — hundreds of thousands of combinations, which in the best-case scenario will be handled in the main memory (if you’re lucky), but depending on the proposed solutions, it may end up in records of a table in a database. Retrieval of these records, the processing of such information, and subsequent calculations could result in excessive or inadmissible processing time and resources load for the problem being addressed.
What advantages do we have for having chosen OR-Tools? What experience did we have with the OR Tools community?
In our experience at Arion, we have always chosen to work on the OR-Tools optimization suite (Google Optimization Tools), in its “flavors” of Constraint Programming and Vehicle Routing.
Depending on the particular project, the use of CP allows us to make savings in both processing time, development time, and obviously maintenance. It is still difficult to quantify, but it is certainly something to consider when addressing this type of project.
One more tip…
It is essential to keep the model as simple as possible: Let the CP Solver do what the CP solver does best, and don’t burden it with decisions that are simple to solve outside of your model logic.
That is why at the design level we like to consider a processing stage prior to the CP Solver, which we call “pruning”, where we eliminate prior complexity that does require complex restrictions solving. The main idea is to let the CP Solver work only in what is crucial for it, and the largest number of trivial decisions not requiring the CP to be processed in advance. For example, in the case of package delivery, initially discard vehicles that cannot manage certain packages or vehicles that due to their current location are out of the range of action, etc.