search

google / or-tools

Google's Operations Research tools:
https://developers.google.com/optimization/
Apache License 2.0
11.11k stars 2.11k forks source link

CP-SAT: Parameter documentation NoOverlap2D, Cumulative #3106

Closed ktnr closed 2 years ago

ktnr commented 2 years ago

I was looking for information on the use_cumulative_in_no_overlap_2d parameter. After some searching I found https://github.com/google/or-tools/blob/2cb85b4eead4c38e1c54b48044f92087cf165bce/ortools/sat/sat_parameters.proto#L618-L623

Great thanks! From the documentation it is not entirely clear to me if this parameter

So I did a small test run with

  1. AddNoOverlap2D
  2. AddNoOverlap2D, set_use_cumulative_in_no_overlap_2d(true)
  3. AddNoOverlap2D, AddCumulative
  4. AddNoOverlap2D, AddCumulative, set_use_cumulative_in_no_overlap_2d(true)

Case 1 is the base case and cases 2-4 could reduce the variable domains in presolve compared to case 1 but yielded the exact same reduced domains. Also, work/time (#branches, #propagations etc...) done steadily decreased with each added option.

It seems that set_use_cumulative_in_no_overlap_2d(true) does similar things as AddCumulative(). Do options 2-4 differ substantially or do they have mostly the same effect? As runtime increases with each option, can you recommend anything regarding the use of these specific options?

I guess my question is: must I settle for a tradeoff along the lines "This always result in better propagation, but it is usually slow" or can you recommend anything else?

I like the new python documentation. Is there a chance to add the parameter documentation to that for easier access and discoverability?

lperron commented 2 years ago

it adds two cumulative constraints (in both directions) by using the interval on one axis, and the duration of the other interval on the other axis. The capacity of the cumulative is the max span of all intervals on the other axis. It is not equivalent as AddCumulative on the model as with option 2, there is not linear relaxation of the cumulative constraint added to the solver.

About doc, I depend on the tools that generate the python tags, the doc... So far, I have not found something that works.