Opened 8 years ago

Closed 5 years ago

# Fix chaining of MILP constraints

Reported by: Owned by: ncohen ncohen major sage-7.2 linear programming vbraun, dimpase, mkoeppe, vdelecroix, tscrim Jeroen Demeyer Matthias Koeppe, Travis Scrimshaw N/A 96e133e 96e133e4b59bafdf0800de72bb280ae6462fd439 #20478

```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
```

### comment:1 Changed 8 years ago by dimpase

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

### comment:2 follow-up: ↓ 3 Changed 8 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 8 years ago by dimpase

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 jdemeyer

• Milestone changed from sage-5.11 to sage-5.12

### comment:5 Changed 7 years ago by vbraun_spam

• Milestone changed from sage-6.1 to sage-6.2

### comment:6 Changed 7 years ago by vbraun_spam

• Milestone changed from sage-6.2 to sage-6.3

### comment:7 Changed 7 years ago by vbraun_spam

• Milestone changed from sage-6.3 to sage-6.4

### comment:8 Changed 5 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 5 years ago by jdemeyer

• Description modified (diff)

### comment:10 Changed 5 years ago by jdemeyer

I'm investigating this.

### comment:11 Changed 5 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 5 years ago by jdemeyer

• Authors set to Jeroen Demeyer

### comment:13 Changed 5 years ago by jdemeyer

• Branch set to u/jdemeyer/milp_constraints_do_no_deal_with_python_ints_properly

### comment:14 Changed 5 years ago by jdemeyer

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

New commits:

 ​ba7613b `Fix chained inequalities with non-Sage types`

### comment:15 Changed 5 years ago by dimpase

• Cc mkoeppe added

New commits:

 ​ba7613b `Fix chained inequalities with non-Sage types`

### comment:16 Changed 5 years ago by mkoeppe

• 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
```
Last edited 5 years ago by jdemeyer (previous) (diff)

### comment:17 Changed 5 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 5 years ago by jdemeyer

• Dependencies set to #20478

### comment:19 Changed 5 years ago by git

• Commit changed from ba7613b12a717f7ca72137d9c91d7edca5f6cbbb to f41c195c520c10eede129873dd047fd6bc85ba95

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

 ​f41c195 `14540 WIP`

### comment:20 Changed 5 years ago by jdemeyer

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

### comment:21 Changed 5 years ago by jdemeyer

• Description modified (diff)

### comment:22 Changed 5 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:

 ​3782ec2 `Common base class for LinearFunction and LinearConstraint` ​682ba3e `Fix chaining of MILP constraints`

### comment:23 Changed 5 years ago by jdemeyer

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

### comment:24 Changed 5 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: ↓ 26 Changed 5 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()
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 5 years ago by jdemeyer

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

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

• Reviewers changed from Matthias Köppe to Matthias Koeppe

### comment:31 Changed 5 years ago by git

• Commit changed from 682ba3e7b8aaf84ba181ac16b8630aefb695c940 to e8d8e67417cecfb4f026a43eb09793117d2fa769

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

 ​e8d8e67 `Improve documentation`

### comment:32 Changed 5 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:

 ​6e10798 `Improve documentation`

### comment:33 Changed 5 years ago by mkoeppe

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

### comment:34 Changed 5 years ago by mkoeppe

• Cc tscrim added

### comment:35 Changed 5 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.

Thanks, Travis!

### comment:37 Changed 5 years ago by mkoeppe

• Status changed from needs_review to positive_review

### comment:38 Changed 5 years ago by mkoeppe

• Status changed from positive_review to needs_work

The patchbot complains about decreased coverage, though

### comment:39 Changed 5 years ago by git

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

• Status changed from needs_work to needs_review

### comment:41 Changed 5 years ago by mkoeppe

• Status changed from needs_review to positive_review

Thanks!

### comment:43 Changed 5 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.