Examples
Here are some classic examples of optimization problems that can be solved using ROOC.
Diet Problem
The diet problem is a classic optimization problem where the goal is to find the optimal diet that meets the nutritional requirements at the lowest cost.
Dominating Set Problem
In the dominating set problem, the goal is to find the smallest set of nodes in a graph such that every node in the graph is either in the set or adjacent to a node in the set, as in, the nodes are either dominant or adjacent to a dominant node (dominated).
Dominating Set Problem, in logic form
The same dominating set problem as above, but written with logic operators instead of arithmetic: rather than requiring a sum of 0/1 variables to be at least 1, each node asserts that it is dominant or that any of its neighbours is. The compiler turns each assertion into the same linear constraint.
Knapsack Problem
In the knapsack problem, you are given a set of items, each with a weight and a value, and a knapsack with a maximum capacity. The goal is to maximize the total value of the items in the knapsack without exceeding the capacity.
Knapsack Problem
The same knapsack problem as before, but creating variables for the weight and cost, together with a named constraint to see the final weight of the bag.
Simple machining problem
Imagine you run a small factory that makes two types of products: A and B. Each product requires time on two machines, Machine 1 and Machine 2. Your goal is to maximize profit, but you’re limited by how many hours each machine is available each day.
Maximum satisfiability (MAX-SAT)
A logic formula used inside arithmetic counts as 1 when true and 0 when false, so the objective can count how many clauses are satisfied. A constraint written as a bare formula is an assertion that must always hold. Here at most 3 of the 4 clauses can be satisfied at once.
Project selection with dependencies
A mixed model: a linear budget constraint sits next to logic constraints that express dependencies between the same Boolean decisions, such as one project requiring another, two projects being mutually exclusive, and at least one flagship project being mandatory.