google / google/or-tools

Allow Dual ray extraction for infeasible LPs when solved using primal simplex in GLOP (via Mathopt)

Open
#5,310 3 comments 0 reactions 1 assignee Claimed by @soppera View on GitHub
Lang: Python Solver: GLOP
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?**
I tried doing this in C++ and python. In both cases, I used Mathopt with GLOP solver.

**Describe the problem you are trying to solve.**
I wanted to test Farkas pricing method for initialization in column generation. I tried to use GLOP, but it only gives me dual ray for infeasible LPs if I use dual simplex method. I would prefer to use primal simplex to solve the master LP when using column generation. With primal simplex, I can extract dual values when the LP is feasible, but not dual rays when LP is infeasible.

**Describe the solution you'd like**
Allow dual ray extraction when the LP is infeasible and solved using primal simplex.

**Describe alternatives you've considered**
Alternative is for me to use dual simplex, which makes the column generation process quite slow.

**Additional context**
Sample test python files to reproduce the issue.

[test_dual_ray.py](https://github.com/user-attachments/files/31484604/test_dual_ray.py)
[test_dual_values.py](https://github.com/user-attachments/files/31484605/test_dual_values.py)

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.