Opened 9 years ago
Closed 6 years ago
#14540 closed defect (fixed)
Fix chaining of MILP constraints
Reported by: | ncohen | Owned by: | ncohen |
---|---|---|---|
Priority: | major | Milestone: | sage-7.2 |
Component: | linear programming | Keywords: | |
Cc: | vbraun, dimpase, mkoeppe, vdelecroix, tscrim | Merged in: | |
Authors: | Jeroen Demeyer | Reviewers: | Matthias Koeppe, Travis Scrimshaw |
Report Upstream: | N/A | Work issues: | |
Branch: | 96e133e (Commits, GitHub, GitLab) | Commit: | 96e133e4b59bafdf0800de72bb280ae6462fd439 |
Dependencies: | #20478 | Stopgaps: |
Description (last modified by )
sage: p = MixedIntegerLinearProgram() sage: b = p.new_variable() sage: int(1) <= b[0] <= int(2) x_0 <= 2
sage: p = MixedIntegerLinearProgram() sage: b = p.new_variable() sage: float(0) <= b[0] <= int(1) <= b[1] <= float(2) 1 <= x_1 <= 2
sage: p = MixedIntegerLinearProgram() sage: b = p.new_variable() sage: b[0] <= 555*b[1] >= 2 2 <= x_0 <= 555*x_1
This can never work due to the way Python handles chained comparisons:
sage: p = MixedIntegerLinearProgram() sage: b = p.new_variable() sage: b[0] <= 3 <= 4 True
Change History (43)
comment:1 Changed 9 years ago by
comment:2 follow-up: ↓ 3 Changed 9 years ago by
Well, in any script that does not wrap integers with Integer()
. So a .py that you load with %runfile
is ok !
Nathann
comment:3 in reply to: ↑ 2 Changed 9 years ago by
Replying to ncohen:
Well, in any script that does not wrap integers with
Integer()
. So a .py that you load with%runfile
is ok !Nathann
and it's not only int
, but float
, too, that gives this problem.
comment:4 Changed 9 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:5 Changed 9 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:6 Changed 8 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:7 Changed 8 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:8 Changed 6 years ago by
- Description modified (diff)
- Milestone changed from sage-6.4 to sage-7.2
- Summary changed from MILP constraints are silently misunderstood to MILP constraints do no deal with Python ints properly
comment:9 Changed 6 years ago by
- Description modified (diff)
comment:10 Changed 6 years ago by
I'm investigating this.
comment:11 Changed 6 years ago by
- Description modified (diff)
- Summary changed from MILP constraints do no deal with Python ints properly to MILP constraints do no deal with Python types properly
comment:12 Changed 6 years ago by
comment:13 Changed 6 years ago by
- Branch set to u/jdemeyer/milp_constraints_do_no_deal_with_python_ints_properly
comment:14 Changed 6 years ago by
- Commit set to ba7613b12a717f7ca72137d9c91d7edca5f6cbbb
- Status changed from new to needs_review
New commits:
ba7613b | Fix chained inequalities with non-Sage types
|
comment:15 Changed 6 years ago by
- Cc mkoeppe added
New commits:
ba7613b | Fix chained inequalities with non-Sage types
|
comment:16 Changed 6 years ago by
- Status changed from needs_review to needs_work
It's not completely fixed. Example:
sage: float(0) <= b[0] <= int(1) <= b[1] <= float(2) 1 <= x_1 <= 2
comment:17 Changed 6 years ago by
- Description modified (diff)
- Summary changed from MILP constraints do no deal with Python types properly to Fix complicated MILP constraints
Allright, let's fix everything on this ticket...
comment:18 Changed 6 years ago by
- Dependencies set to #20478
comment:19 Changed 6 years ago by
- Commit changed from ba7613b12a717f7ca72137d9c91d7edca5f6cbbb to f41c195c520c10eede129873dd047fd6bc85ba95
Branch pushed to git repo; I updated commit sha1. New commits:
f41c195 | 14540 WIP
|
comment:20 Changed 6 years ago by
- Summary changed from Fix complicated MILP constraints to Fix chaining of MILP constraints
comment:21 Changed 6 years ago by
- Description modified (diff)
comment:22 Changed 6 years ago by
- Commit changed from f41c195c520c10eede129873dd047fd6bc85ba95 to 682ba3e7b8aaf84ba181ac16b8630aefb695c940
comment:23 Changed 6 years ago by
- Reviewers set to Matthias Köppe
- Status changed from needs_work to needs_review
comment:24 Changed 6 years ago by
In the end, I had to rewrite most of the comparison code but still using the ideas of the original code.
comment:25 follow-up: ↓ 26 Changed 6 years ago by
- Cc vdelecroix added
It seems to work, except for bizarre behavior if one does try to chain in comparisons between constants.
sage: p = MixedIntegerLinearProgram() sage: b = p.new_variable() sage: b[0] <= 2 <= 2 True sage: 0<=b[0]<=b[0]<=b[0]<=1 0 <= x_0 <= 2 <= x_0 <= x_0 <= 1
(The documentation should probably explain what is expected to work and what is not!)
I note that the unrelated comparison-hack code for SR silently throws away chained inequalities.
sage: var('x') x sage: x <= 2 <= 3 x <= 2 sage: x <= 2 <= x x <= 2
Also, should add_constraint
allow the user to add tautological constraints like this:
sage: p = MixedIntegerLinearProgram() sage: p.add_constraint(0<=0) ValueError: argument must be a linear function or constraint, got True
Someone should probably review your changes to Parent
before this ticket is set to positive_review.
comment:26 in reply to: ↑ 25 ; follow-up: ↓ 27 Changed 6 years ago by
Replying to mkoeppe:
It seems to work, except for bizarre behavior if one does try to chain in comparisons between constants.
sage: p = MixedIntegerLinearProgram() sage: b = p.new_variable() sage: b[0] <= 2 <= 2 True sage: 0<=b[0]<=b[0]<=b[0]<=1 0 <= x_0 <= 2 <= x_0 <= x_0 <= 1
There are theoretical limits to what can work without fundamentally changing Python (or the preparser if you want to go that way), that's why it is called a "hack".
I could add a bit of documentation, although a full explanation would probably be too technical.
comment:27 in reply to: ↑ 26 ; follow-up: ↓ 28 Changed 6 years ago by
Replying to jdemeyer:
I could add a bit of documentation, although a full explanation would probably be too technical.
It would suffice to explain that you can chain linear expressions with the same comparison, and also use constants at the very left hand side and the very right hand side. If the user tries anything beyond that, there's either an error or weirdness.
comment:28 in reply to: ↑ 27 Changed 6 years ago by
Replying to mkoeppe:
Replying to jdemeyer:
I could add a bit of documentation, although a full explanation would probably be too technical.
It would suffice to explain that you can chain linear expressions with the same comparison, and also use constants at the very left hand side and the very right hand side. If the user tries anything beyond that, there's either an error or weirdness.
Constants in the middle also work, just not two constants next to eachother. For example, b[0] <= 0 <= b[1]
works as expected.
comment:29 Changed 6 years ago by
I know, it was just a suggestion how you could simplify the story when you write that documentation.
comment:30 Changed 6 years ago by
- Reviewers changed from Matthias Köppe to Matthias Koeppe
comment:31 Changed 6 years ago by
- Commit changed from 682ba3e7b8aaf84ba181ac16b8630aefb695c940 to e8d8e67417cecfb4f026a43eb09793117d2fa769
Branch pushed to git repo; I updated commit sha1. New commits:
e8d8e67 | Improve documentation
|
comment:32 Changed 6 years ago by
- Commit changed from e8d8e67417cecfb4f026a43eb09793117d2fa769 to 6e107988d589bde3a8b8dd9ee113393608b2c17f
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
6e10798 | Improve documentation
|
comment:33 Changed 6 years ago by
Looks good to me, but the changes to Parent
still need independent review.
comment:34 Changed 6 years ago by
- Cc tscrim added
comment:35 Changed 6 years ago by
- Reviewers changed from Matthias Koeppe to Matthias Koeppe, Travis Scrimshaw
The changes in Parent
look good to me. If everything else is good, then this would be a positive review.
comment:36 Changed 6 years ago by
Thanks, Travis!
comment:37 Changed 6 years ago by
- Status changed from needs_review to positive_review
comment:38 Changed 6 years ago by
- Status changed from positive_review to needs_work
The patchbot complains about decreased coverage, though
comment:39 Changed 6 years ago by
- Commit changed from 6e107988d589bde3a8b8dd9ee113393608b2c17f to 96e133e4b59bafdf0800de72bb280ae6462fd439
Branch pushed to git repo; I updated commit sha1. New commits:
96e133e | Improve __cinit__ and add doctests
|
comment:40 Changed 6 years ago by
- Status changed from needs_work to needs_review
comment:41 Changed 6 years ago by
- Status changed from needs_review to positive_review
comment:42 Changed 6 years ago by
Thanks!
comment:43 Changed 6 years ago by
- Branch changed from u/jdemeyer/milp_constraints_do_no_deal_with_python_ints_properly to 96e133e4b59bafdf0800de72bb280ae6462fd439
- Resolution set to fixed
- Status changed from positive_review to closed
In a script
- do you mean a Python script, not Sage script, right?