google / google/or-tools

Support for `objective_lb_search` in interleaved search

Open
#4,946 0 comments 0 reactions 1 assignee Claimed by @lperron View on GitHub
Feature Request Solver: CP-SAT Solver
Dominant language
C++
Stars
14.1k
Forks
2.5k
Avg merge
8h 39m
Merged PRs (30d)
72

Description

**What language and solver does this apply to?**
CP-SAT

**Describe the problem you are trying to solve.**

I work on scheduling problems embedded within compilers. Because this is a compiler application, determinism is a hard requirement, which requires me to use interleaved search when I enable multiple workers.

I have found that `objective_lb_search` is highly effective at proving lower bounds for my makespan minimization problems.

**Describe the solution you'd like**

Can you please expose `objective_lb_search` as a supported subsolver within interleaved search?

**Describe alternatives you've considered**

I have experimented with various supported solvers within interleaved search, including adding various subsolvers I configure on my own. While CP-SAT often finds the optimal solution, it frequently struggles to prove optimality within a reasonable (deterministic) time without `objective_lb_search`, which is critical for our compilation times.

**Additional context**

If it's possible at all, I would also appreciate support for remaining solvers as well, though at this point they are not as critical as `objective_lb_search` for me at this point:
- lb_tree_search
- probing_search
- objective_shaving_search

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.