2

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?

Víctor Martínez
  • 854
  • 2
  • 11
  • 29
  • 2
    No. The CP-SAT solver (as well as all the other solvers like CP and MILP) are *closed* as i would call it. They live in some (different for each solver) mathematical-structure and injecting some callback without guaranteeing it obeys the same core-structure won't work. Injecting something with the same structure is pretty much equal to modelling it in the problem in the first place (although one could argue about lazy and non-lazy approaches here). Long story short: You need to model the objective using the constraints / tools CP-SAT gives you. Some people would call these meta-constraints. – sascha Apr 22 '21 at 21:29

1 Answers1

0

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.

etov
  • 2,972
  • 2
  • 22
  • 36