OR-Tools Performance: High-Dimensional vs. Multiple Low-Dimensional Variables

[beneo...@gmail.com]

HI,

I'm working on a Mixed-Integer Programming (MIP) problem where I have a choice between two modeling approaches:

1. Multiple Low-Dimensional Variables: Each decision is represented by its own set of variables (e.g., separate variables for time, location, resource, etc.). This leads to many variables but with lower dimensionality.
2. High-Dimensional Variable: All decisions are combined into a single, high-dimensional variable (e.g., a variable indexed by time, location, resource, etc.). This reduces the total variable count but increases complexity.

I'm interested in understanding the trade-offs in OR-Tools, specifically:

• Solve Time: In general, does OR-Tools tend to perform better with multiple low-dimensional variables or a single high-dimensional variable? Are there specific problem characteristics that would favor one approach over the other?
• Sparsity: My problem has a sparse structure (many zero values in the constraint matrix). Does the sparsity handling in OR-Tools differ depending on the variable representation? Are there any tips for optimizing performance in sparse problems?

Any insights or recommendations based on your experience would be greatly appreciated.

Thank you
N. Vance

[Priidik Vilumaa]

Hi,

I've had more luck with more, but simpler variables. For example, I used to use a fair amount of element constraint, since it's a trick I learned at school to lower your number of variables. But as I've understood from this forum, AddElement is just a convenience function in CP-SAT, and should/could usually be avoided.

On the other hand, you never really know what works well for your problem before you try it.

Best,

Priidik