iiasa / iiasa/message_ix

Align with Dantzig's (1963) original transport problem

Open
#968 1 comment 0 reactions 0 assignees View on GitHub
discuss
Dominant language
Jupyter Notebook
Stars
150
Forks
178
Avg merge
17h 32m
Merged PRs (30d)
2

Description

In both message_ix and ixmp, we use a linear programming (LP) problem from Dantzig (1963) for a simple test case. In the course of working on https://github.com/iiasa/message_ix/pull/451#issuecomment-3178149485, I found that our implementation is not faithful to the original.

Specifically:
- The original report is available at https://www.rand.org/pubs/reports/R366.html. See Chapter 3 "Formulating a Linear Programming Model", Section 3-3 "A Transportation Problem", pp.35–41 (PDF pages 50–56).
- The text reads, in part:
> Cases available: 350 at Cannery I, 650 at Cannery II = 1000 total available
>
> Cases demanded: 300 at Warehouse A, 300 at Warehouse B, 300 at Warehouse C = 900 total required
>
> The excess production (100 cases) should be stored without shipment.
- We have the following numbers which do not match: https://github.com/iiasa/message_ix/blob/9fb0b97867f9234d98b4e43e158d7af9b30c42f4/message_ix/testing/__init__.py#L410-L426
and https://github.com/iiasa/message_ix/blob/9fb0b97867f9234d98b4e43e158d7af9b30c42f4/message_ix/tests/test_feature_bound_activity_shares.py#L46-L53

One consequence of this—as described in the linked comment—is that the problem does not have a unique solution. In #451 (possibly other PRs that change the GAMS code) this causes difficulty because the solver chooses a different solution with the same objective function value.

IMO there is no reason we can't adjust `make_dantzig()` to (a) align with the original statement of the problem and (b) have a single, unique solution. However, to do this may also require adjustments to expectations wherever this is used across our test suite (many places). #451 will contain adjustments narrowly focused on that PR, but I open this issue towards a general fix.

Contributor guide

Open the contributing guide

Research direction

Read the Dantzig report's Chapter 3, Section 3-3, then inspect make_dantzig() in message_ix/testing/__init__.py and the expectations in message_ix/tests/test_feature_bound_activity_shares.py. Search the test suite for other uses of this fixture and run the affected tests. Done means the fixture matches the original transport problem, has a unique solution, and all affected expectations pass.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
testing-qa
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.