The knapsack problem is a problem in combinatoral optimization: given a knapsack that can contain a maximum weight and a set of items with a certain weight and value, determine the combination of items to include in the knapsack that maximizes the value of the contents without exceeding the knapsack weight limit.
(image source: https://commons.wikimedia.org/wiki/File:Knapsack.svg , license: https://creativecommons.org/licenses/by-sa/2.5/deed.en)
In this example, we have ingots of different weights and values that we want to put in our knapsack. OptaPlanner will select the combination of ingots that won't exceed the knapsack's maximum weight but will provide the highest value possible.
OptaPlanner is an A.I. constraint satisfaction solver that provides a highly scalable platform to find optimal solutions to NP-complete and NP-hard problems. OptaPlanner enables us to write these solutions in plain Java, which makes this technology available to a large group of software developers. Furthermore, the OptaPlanner Quarkus extension lets us write our OptaPlanner application as a cloud-native micro-service.
In this scenario, we've learned how to implement the knapsack problem using OptaPlanner on Quarkus. We've seen how the Quarkus hot-reload feature enables us to keep our application running while developing our code. We've turned our OptaPlanner Quarkus application into a runnable JAR file that runs on a standard JVM. And finally, we've shown how we can deploy this application to OpenShift, scale the application, and fire requests to it.
If you’re interested in helping continue to improve OptaPlanner, use OptaPlanner to develop applications, or if you’re just curious about it, please check out these links:
OptaPlanner and Quarkus
In this step, we will create the OptaPlanner Quarkus application skeleton.
We start with a basic Maven-based Quarkus application which has been generated from the Quarkus Maven Plugin.
The Application You Will Build
In this scenario, we will build an OptaPlanner application on Quarkus that will solve the knapsack problem. The knapsack problem is a problem in which we need to put ingots with a certain weight and a certain value into a knapsack in such a way that we maximize the value without exceeding the maximum knapsack weight. The knapsack problem is an NP-complete problem, which means it's not solvable in polynomial time. In other words, when the size of the problem grows, the time needed to solve the problem grows exponentially. For even relatively small problems, this means that finding the best solution can take billions of years.
OptaPlanner is an A.I. constraint satisfaction solver that enables us to find the optimal solution to these kinds of problems in the limited time at our disposal. In this scenario, we will build an OptaPlanner application that runs on Quarkus to solve this problem.
Creating a basic project
The easiest way to create a new Quarkus project is to click the following Maven command:
mvn io.quarkus:quarkus-maven-plugin:1.7.0.Final:create \
This command uses the Quarkus Maven plugin and generates a basic Quarkus application that includes the OptaPlanner extension in the
Click the following command to remove the automatically generated unit-test classes:
rm -rf /root/projects/kogito/knapsack-optaplanner-quarkus/src/test/java/com`
Running the Application
Click the following command to change directory to the
Click the next command to run the OptaPlanner application in Quarkus development mode. This enables us to keep the application running while we implement our application logic. OptaPlanner and Quarkus will hot reload the application (update changes while the application is running) when it is accessed and changes have been detected:
mvn clean compile quarkus:dev
The application starts in development mode, but returns an error that it can't find any classes annotated with
@PlanningSolution. This is expected! We will implement these classes later.
We've seen how to create the skeleton of a basic OptaPlanner on Quarkus application, and start the application in Quarkus development mode.
In the next step we'll add the domain model of our application.