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:  sage7.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 followup: ↓ 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 8 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:5 Changed 8 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:6 Changed 8 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:7 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:8 Changed 6 years ago by
 Description modified (diff)
 Milestone changed from sage6.4 to sage7.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 nonSage types

comment:15 Changed 6 years ago by
 Cc mkoeppe added
New commits:
ba7613b  Fix chained inequalities with nonSage types

comment:16 Changed 6 years ago by
 Status changed from needs_review to needs_work
It's not completely fixed. Example:
sage: p = MixedIntegerLinearProgram() sage: b = p.new_variable() 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 followup: ↓ 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 comparisonhack 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 ; followup: ↓ 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 ; followup: ↓ 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?