Opened 6 years ago

Closed 3 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) Commit: 96e133e4b59bafdf0800de72bb280ae6462fd439
Dependencies: #20478 Stopgaps:

Description (last modified by jdemeyer)

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 6 years ago by dimpase

In a script - do you mean a Python script, not Sage script, right?

comment:2 follow-up: Changed 6 years ago by ncohen

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 6 years ago by dimpase

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 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:5 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:6 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:7 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:8 Changed 3 years ago by jdemeyer

  • 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 3 years ago by jdemeyer

  • Description modified (diff)

comment:10 Changed 3 years ago by jdemeyer

I'm investigating this.

comment:11 Changed 3 years ago by jdemeyer

  • 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 3 years ago by jdemeyer

  • Authors set to Jeroen Demeyer

comment:13 Changed 3 years ago by jdemeyer

  • Branch set to u/jdemeyer/milp_constraints_do_no_deal_with_python_ints_properly

comment:14 Changed 3 years ago by jdemeyer

  • Commit set to ba7613b12a717f7ca72137d9c91d7edca5f6cbbb
  • Status changed from new to needs_review

New commits:

ba7613bFix chained inequalities with non-Sage types

comment:15 Changed 3 years ago by dimpase

  • Cc mkoeppe added

New commits:

ba7613bFix chained inequalities with non-Sage types

comment:16 Changed 3 years ago by mkoeppe

  • 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
Version 0, edited 3 years ago by mkoeppe (next)

comment:17 Changed 3 years ago by jdemeyer

  • 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 3 years ago by jdemeyer

  • Dependencies set to #20478

comment:19 Changed 3 years ago by git

  • Commit changed from ba7613b12a717f7ca72137d9c91d7edca5f6cbbb to f41c195c520c10eede129873dd047fd6bc85ba95

Branch pushed to git repo; I updated commit sha1. New commits:

f41c19514540 WIP

comment:20 Changed 3 years ago by jdemeyer

  • Summary changed from Fix complicated MILP constraints to Fix chaining of MILP constraints

comment:21 Changed 3 years ago by jdemeyer

  • Description modified (diff)

comment:22 Changed 3 years ago by git

  • Commit changed from f41c195c520c10eede129873dd047fd6bc85ba95 to 682ba3e7b8aaf84ba181ac16b8630aefb695c940

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

3782ec2Common base class for LinearFunction and LinearConstraint
682ba3eFix chaining of MILP constraints

comment:23 Changed 3 years ago by jdemeyer

  • Reviewers set to Matthias Köppe
  • Status changed from needs_work to needs_review

comment:24 Changed 3 years ago by jdemeyer

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: Changed 3 years ago by mkoeppe

  • 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: Changed 3 years ago by jdemeyer

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: Changed 3 years ago by 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.

comment:28 in reply to: ↑ 27 Changed 3 years ago by jdemeyer

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 3 years ago by mkoeppe

I know, it was just a suggestion how you could simplify the story when you write that documentation.

comment:30 Changed 3 years ago by jdemeyer

  • Reviewers changed from Matthias Köppe to Matthias Koeppe

comment:31 Changed 3 years ago by git

  • Commit changed from 682ba3e7b8aaf84ba181ac16b8630aefb695c940 to e8d8e67417cecfb4f026a43eb09793117d2fa769

Branch pushed to git repo; I updated commit sha1. New commits:

e8d8e67Improve documentation

comment:32 Changed 3 years ago by git

  • Commit changed from e8d8e67417cecfb4f026a43eb09793117d2fa769 to 6e107988d589bde3a8b8dd9ee113393608b2c17f

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

6e10798Improve documentation

comment:33 Changed 3 years ago by mkoeppe

Looks good to me, but the changes to Parent still need independent review.

comment:34 Changed 3 years ago by mkoeppe

  • Cc tscrim added

comment:35 Changed 3 years ago by tscrim

  • 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 3 years ago by mkoeppe

Thanks, Travis!

comment:37 Changed 3 years ago by mkoeppe

  • Status changed from needs_review to positive_review

comment:38 Changed 3 years ago by mkoeppe

  • Status changed from positive_review to needs_work

The patchbot complains about decreased coverage, though

comment:39 Changed 3 years ago by git

  • Commit changed from 6e107988d589bde3a8b8dd9ee113393608b2c17f to 96e133e4b59bafdf0800de72bb280ae6462fd439

Branch pushed to git repo; I updated commit sha1. New commits:

96e133eImprove __cinit__ and add doctests

comment:40 Changed 3 years ago by jdemeyer

  • Status changed from needs_work to needs_review

comment:41 Changed 3 years ago by mkoeppe

  • Status changed from needs_review to positive_review

comment:42 Changed 3 years ago by jdemeyer

Thanks!

comment:43 Changed 3 years ago by vbraun

  • 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
Note: See TracTickets for help on using tickets.