Evaluating a custom function when a solution is proposed by ORTOOLS

user_3305822 0
Viewed 183

I am pretty new to OR-TOOLS in Python. I have made several tutorial examples, but I am facing issues trying to model my problem.

Let's see we have a bin packing problem, in which I need to find the fewest bins that will hold all the items in function of their weight. In this typical problem we would want to minimize the number of bins used. But let's say we have an additional objective: to maximize the "quality" of the bin. Here's the problem: to evaluate the quality of that bin, we need to call a non-linear function that takes the items in that bin and returns a quality. I guess I cannot use a multi-objective approach with CP/SAT, so we could model it weighting both objectives.

The problem I am facing is thus the following:

I cannot set the 'quality' as variable because it depends on the current solution (the items associated to a bin)

How can I do that? assigning a callback? is it possible?

cp-sat-solver or-tools optimization python
1 Answers

Depending on the "current" solution is not a problem. You could add a "quality" variable, which depends on the values of the variables representing the bins and their contents, and uses the solver's primitives to calculate the desired quantity.

This might not be possible for just any function, but the solver's primitives do allow some forms of non-linear calculations (just as an example, you can calculate abs(x), or x^2, (ref)).

So, for instance, you could have a quality variable which calculates the (number of bins used)^2.

Once you get to a form of quality calculation which works within the solver, you can go back to use one of the approaches for solving for more than a single objective, like weighted sum.

user_5188040
Related