Opened 7 years ago

Last modified 3 months ago

## #18688 new task

# MixedIntegerLinearProgram should support basis status getting/setting

Reported by: | Matthias Köppe | Owned by: | |
---|---|---|---|

Priority: | minor | Milestone: | sage-9.8 |

Component: | numerical | Keywords: | lp |

Cc: | Yuan Zhou, Nathann Cohen | Merged in: | |

Authors: | Reviewers: | ||

Report Upstream: | N/A | Work issues: | |

Branch: | Commit: | ||

Dependencies: | #18685, #18763 | Stopgaps: |

### Description (last modified by )

When Sage's `MixedIntegerLinearProgram`

is used for solving an LP, one frequently needs to access further information about the current basis (often, the optimal basis after solving the LP), not just the numerical values of the solution; in particular, the combinatorial information: which variables are basic, nonbasic at-lower, nonbasic at-upper.

#18685 adds the necessary backend functions for the GLPK backend. #18763 adds the necessary backend functions for the COIN (CBC/CLP) backend. This kind of information is available in most (simplex method based) solvers. (Exceptions: ppl does not seem to have a public interface to anything simplex tableau related.)

The Sage interface should, of course, be designed to work consistently across all solvers. There are some subtleties here -- not all solvers mean the same thing with "at-lower" for cases such as ranged constraints. Best to look at a source that has already sorted it all out: In the COIN open solver interface, https://projects.coin-or.org/Osi/browser/trunk/Osi/src?order=name the function is called getBasisStatus

And then there's setBasisStatus, of course. One needs this function if one wants to implement LP-based branch and bound with warmstarting.

There are other important basis-related functions: getBInvARow, getBInvRow, getBInvACol, getBInvCol -- but that's for another ticket -- see #18733.

See also #18804 (LPBackendDictionary).

See also the methods `is_variable_basic`

, `is_slack_variable_basic`

, `is_variable_nonbasic_at_lower_bound`

, `is_slack_variable_nonbasic_at_lower_bound`

of `GenericBackend`

.

### Change History (12)

### comment:1 Changed 7 years ago by

Description: | modified (diff) |
---|

### comment:2 Changed 7 years ago by

Description: | modified (diff) |
---|

### comment:3 Changed 7 years ago by

Dependencies: | #18685 → #18685, #18763 |
---|---|

Description: | modified (diff) |

### comment:4 Changed 7 years ago by

Description: | modified (diff) |
---|

### comment:5 Changed 7 years ago by

Description: | modified (diff) |
---|

### comment:6 Changed 22 months ago by

Milestone: | sage-6.8 → sage-9.3 |
---|

### comment:7 Changed 22 months ago by

Description: | modified (diff) |
---|

### comment:8 Changed 22 months ago by

Milestone: | sage-9.3 → sage-9.4 |
---|

### comment:9 Changed 17 months ago by

Milestone: | sage-9.4 → sage-9.5 |
---|

### comment:10 Changed 12 months ago by

Milestone: | sage-9.5 → sage-9.6 |
---|

### comment:11 Changed 9 months ago by

Milestone: | sage-9.6 → sage-9.7 |
---|

### comment:12 Changed 3 months ago by

Milestone: | sage-9.7 → sage-9.8 |
---|

**Note:**See TracTickets for help on using tickets.

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.