Pip fails to install satisfiable requirements due to bug in backjumping optimization

[notatallshaw]

Description

On Python 3.9 Linux pip fails to install with the following requirements:

pandas>=1.3.5,<=1.4.0
pystac>=1.8.2,<=1.8.3
pystac-client>=0.3.2,<=0.3.3
sat-stac<=0.1.1

Expected behavior

Should install the satisfiable requirements:

pandas==1.3.5
pystac==1.8.3
pystac-client==0.3.3
sat-stac==0.1.1

pip version

23.2.1

Python version

3.9

OS

Linux

How to Reproduce

python3.9 -m venv .venv
source .venv/bin/activate
python -m pip install pip --upgrade
pip install "pandas>=1.3.5,<=1.4.0" "pystac>=1.8.2,<=1.8.3" "pystac-client>=0.3.2,<=0.3.3" "sat-stac<=0.1.1"

Output

INFO: pip is looking at multiple versions of pystac-client to determine which version is compatible with other requirements. This could take a while.
ERROR: Cannot install pystac-client==0.3.2 and pystac<=1.8.3 and >=1.8.2 because these package versions have conflicting dependencies.

The conflict is caused by:
    The user requested pystac<=1.8.3 and >=1.8.2
    pystac-client 0.3.2 depends on pystac~=1.2.0

To fix this you could try to:
1. loosen the range of package versions you've specified
2. remove package versions to allow pip attempt to solve the dependency conflict

ERROR: ResolutionImpossible: for help visit https://pip.pypa.io/en/latest/topics/dependency-resolution/#dealing-with-dependency-conflicts

Code of Conduct

• I agree to follow the PSF Code of Conduct.

Context

This is a regression since Pip 23.1 which vendored resolvelib which included this change to backtracking: sarugaku/resolvelib#113

There is already an issue on resolvelib side: sarugaku/resolvelib#134

But given this has a bigger impact because it causes Pip to fail to install requirements when there is a valid solution I feel there should be an issue on Pip side until it is resolved.