MixedIntegerLinearProgram: New backend using InteractiveLPProblem #20296

mkoeppe · 2016-03-26T02:40:10Z

If one has to solve a small LP with irrational (say, AA) data (and needs access to the exact solution), the only available tool is the didactical implementation of the simplex method in InteractiveLPProblem (but see #18735). This ticket implements a MixedIntegerLinearProgram backend using InteractiveLPProblem.

Example:

            sage: poly = polytopes.dodecahedron(base_ring=AA)
            sage: lp = poly.to_linear_program(solver='InteractiveLP')
            sage: b = lp.get_backend()
            sage: b.set_objective([1, 1, 1])
            sage: lp.solve()
            2.291796067500631?

(This example uses backend functions because of #20301; and the base_ring=AA is there because of #13041.)

CC: @dimpase @novoselt @nathanncohen @videlec @fchapoton

Component: numerical

Author: Matthias Koeppe

Branch/Commit: 8c1fd4a

Reviewer: Andrey Novoseltsev, Dima Pasechnik

Issue created by migration from https://trac.sagemath.org/ticket/20296

The text was updated successfully, but these errors were encountered:

mkoeppe · 2016-03-27T00:22:06Z

Branch: u/mkoeppe/mixedintegerlinearprogram__new_backend_using_interactivelpproblem

mkoeppe · 2016-03-27T00:36:26Z

Author: Matthias Koeppe

mkoeppe · 2016-03-27T00:36:26Z

comment:2

Needs review.

Some remarks:

I'm using some _internals of InteractiveLPProblem (_constraint_types, _variable_types, _problem_type, _is_negative) because some accessor methods are missing. Should I be adding them?
There's should be a way to choose the base ring for the solver (right now I'm using AA -- but ultimately I'd like to use an embedded number field), but I'm not sure about the interface... perhaps MixedIntegerLinearProgram(solver=('InteractiveLP', AA)) or MixedIntegerLinearProgram(solver='InteractiveLP', base_ring=AA

New commits:

`c39dd7d`	`Fix typo in documentation`
`4596534`	`New MIP backend: InteractiveLPBackend`
`78039be`	`Fix doctests (which never run)`
`08d4548`	`Fix typo in docstring`

mkoeppe · 2016-03-27T00:36:26Z

Commit: 08d4548

novoselt · 2016-03-27T05:11:10Z

comment:4

Replying to @mkoeppe:

Some remarks:

I'm using some _internals of InteractiveLPProblem (_constraint_types, _variable_types, _problem_type, _is_negative) because some accessor methods are missing. Should I be adding them?

I think so - the reason they are missing is that they were never needed before. Using guts directly makes sense inside of ILLP itself, but now that you have a dependent module there has to be documented and tested way to access them.

There's should be a way to choose the base ring for the solver (right now I'm using AA -- but ultimately I'd like to use an embedded number field), but I'm not sure about the interface... perhaps MixedIntegerLinearProgram(solver=('InteractiveLP', AA)) or MixedIntegerLinearProgram(solver='InteractiveLP', base_ring=AA

base_ring=AA seems to be more common (and I think it is common to use ring even when only field would really make sense).

sagetrac-git · 2016-03-27T05:57:50Z

Changed commit from 08d4548 to bd77615

sagetrac-git · 2016-03-27T05:57:50Z

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

`bd77615`	`InteractiveLPProblem: New accessors problem_type, is_negative etc.`

mkoeppe · 2016-03-27T06:17:55Z

comment:6

I've added these accessor methods and changed my code to use them.
Two more things regarding InteractiveLPProblem:

I think InteractiveLPProblem.standard_form should allow the user to pass names for the slack variables
It would be nice if InteractiveLPProblemwould support an additive constant in the objective function (see obj_constant_term in my code)

novoselt · 2016-03-27T17:11:52Z

comment:7

Regarding problem_type method - why do you add minus there? It seems to me that your old code was not adding it so either it was wrong or it is wrong now. And for the method itself I think it makes more sense to return just self._problem_type as is and mention in documentation that there is also is_negative method and they need to be used together.

Passing through parameters to the constructor would make sense. And adding a constant to non-standard form would be handy. Let me work on it today actually and take a break from digging in JavaScript!

Also, it would be nice if someone closer to LP backends did the full review of this ticket.

sagetrac-git · 2016-03-27T18:56:12Z

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

`4ecc46b`	`InteractiveLPProblem.problem_type: Don't put minus sign in front for is_negative=True`

sagetrac-git · 2016-03-27T18:56:12Z

Changed commit from bd77615 to 4ecc46b

mkoeppe · 2016-03-27T18:59:25Z

comment:9

Replying to @novoselt:

Regarding problem_type method - why do you add minus there? It seems to me that your old code was not adding it so either it was wrong or it is wrong now. And for the method itself I think it makes more sense to return just self._problem_type as is and mention in documentation that there is also is_negative method and they need to be used together.

OK, I've changed it.
For my code, it does not make any difference because I don't construct "-max" or "-min" problems.
I only have to deal with is_negative once, for the standard-form problem that is created while solving.

Passing through parameters to the constructor would make sense. And adding a constant to non-standard form would be handy. Let me work on it today actually and take a break from digging in JavaScript!

Thanks!

Also, it would be nice if someone closer to LP backends did the full review of this ticket.

Yes, I'm hoping that someone on the Cc list could take a look...

mkoeppe · 2016-03-27T19:04:36Z

comment:10

By the way, the interactive_simplex_method code should probably check for variable-name clashes between auto-generated and user-supplied variable names. It gets quite confused, for example, when a variable named "x0" is introduced because it thinks it is the primal-phase-1 auxiliary variable.

sagetrac-git · 2016-03-27T19:30:56Z

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

`ea99c1e`	`InteractiveLPBackend, GenericBackend: Fix the variable_lower_bound, variable_upper_bound interfaces`

sagetrac-git · 2016-03-27T19:30:56Z

Changed commit from 4ecc46b to ea99c1e

mkoeppe · 2016-03-27T19:51:56Z

comment:12

Another wishlist item for interactive_simplex_method: standard_form should provide a linear map that transforms a solution back to the original variables. (If InteractiveLPProblem wants to support arbitrary variable bounds in the future, it would have to be an affine linear map.)

sagetrac-git · 2016-03-27T20:16:22Z

Changed commit from ea99c1e to e2319b5

sagetrac-git · 2016-03-27T20:16:22Z

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

`e2319b5`	`InteractiveLPBackend.get_variable_value: Guard against standard-form transformations`

sagetrac-git · 2016-03-27T21:44:39Z

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

`e27f297`	`InteractiveLPBackend: Make base_ring an init argument`

sagetrac-git · 2016-03-27T21:44:39Z

Changed commit from e2319b5 to e27f297

sagetrac-git · 2016-03-27T21:47:23Z

Changed commit from e27f297 to 5b0954f

sagetrac-git · 2016-03-27T21:47:23Z

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

`5b0954f`	`InteractiveLPBackend._variable_type_from_bounds: Add doctests`

sagetrac-git · 2016-03-30T03:08:16Z

Changed commit from 184249d to aa21bc6

sagetrac-git · 2016-03-31T18:27:05Z

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

`28ffdb2`	`Merge tag '7.2.beta1' into t/20296/mixedintegerlinearprogram__new_backend_using_interactivelpproblem`
`9cf5a75`	`LinearFunction._coeff_formatter: Handle general base_rings`

sagetrac-git · 2016-03-31T18:27:05Z

Changed commit from aa21bc6 to 9cf5a75

sagetrac-git · 2016-03-31T20:47:12Z

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

`806e6b6`	`InteractiveLPBackend: Add class docstring`

sagetrac-git · 2016-03-31T20:47:12Z

Changed commit from 9cf5a75 to 806e6b6

sagetrac-git · 2016-04-03T19:21:59Z

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

`eb4b73f`	`InteractiveLPBackend: Add another doctest`
`33b3f52`	`Merge tag '7.2.beta2' into t/20296/mixedintegerlinearprogram__new_backend_using_interactivelpproblem`
`00ab350`	`InteractiveLPBackend: Add final doctest`

sagetrac-git · 2016-04-03T19:21:59Z

Changed commit from 806e6b6 to 00ab350

dimpase · 2016-04-05T15:00:25Z

comment:23

there are long commented out blocks, like cpdef solver_parameter, and ones for file output. Can you remove them?

sagetrac-git · 2016-04-05T15:08:22Z

Changed commit from 00ab350 to 2f8d672

sagetrac-git · 2016-04-05T15:08:22Z

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

`2f8d672`	`InteractiveLPBackend: Remove commented-out code`

dimpase · 2016-04-05T15:28:36Z

comment:25

Can we have a real example of solving an LP over algebraic numbers?
I tried to create one by using #20301, but it does not quite fly:

sage: d=polytopes.dodecahedron()
sage: p,x=d.to_linear_program(solver='InteractiveLP',return_variable=True)
sage: p.set_objective(x[0]+x[1]+x[2])
sage: p.solve()
2.291796067500631?
sage: p.get_values()
[]
sage: p.get_values(x)
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
<ipython-input-21-d8eb94d9ce26> in <module>()
----> 1 p.get_values(x)

/home/dima/software/sage/src/sage/numerical/mip.pyx in sage.numerical.mip.MixedIntegerLinearProgram.get_values (build/cythonized/sage/numerical/mip.c:9812)()
   1366                 c = {}
   1367                 for (k,v) in l.items():
-> 1368                     c[k] = self._backend.get_variable_value(self._variables[v])
   1369                 val.append(c)
   1370             elif isinstance(l, list):

/home/dima/software/sage/src/sage/numerical/backends/interactivelp_backend.pyx in sage.numerical.backends.interactivelp_backend.InteractiveLPBackend.get_variable_value (build/cythonized/sage/numerical/backends/interactivelp_backend.c:8385)()
    700         """
    701         if str(self.lp.decision_variables()[variable]) != str(self.lp_std_form.decision_variables()[variable]):
--> 702             raise NotImplementedError("Undoing the standard-form transformation is not implemented")
    703         return self.final_dictionary.basic_solution()[variable]
    704 

NotImplementedError: Undoing the standard-form transformation is not implemented

anyway, that p.get_values(x) ought to be fixed, perhaps on another ticket. By now you can still make this ticket depend on #20301, and give the above (without p.get_values(x)) as a doctest.
Or perhaps you know a workaround to get the values regardless?

novoselt · 2016-04-05T15:32:52Z

comment:26

#20311 implements going back from the standard form, so will allow to address this problem.

mkoeppe · 2016-04-05T15:49:42Z

comment:27

Until #20301 and #20311 are merged into develop, I will modify the test with algebraic numbers as follows so you can see the solution vector, using backend methods:

            sage: poly = polytopes.dodecahedron(base_ring=AA)
            sage: lp = poly.to_linear_program(solver='InteractiveLP')
            sage: b = lp.get_backend()
            sage: for k in range(3): b.variable_lower_bound(k, 0)
            sage: b.set_objective([1, 1, 1])
            sage: lp.solve()
            2.291796067500631?
            sage: [b.get_variable_value(k) for k in range(3)]
            [0.763932022500211?, 0.763932022500211?, 0.763932022500211?]

(I already have a patch on a branch that uses these tickets and has a prettier version of this example.)

sagetrac-git · 2016-04-05T16:06:50Z

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

`3a26453`	`InteractiveLPBackend: Expand example with algebraic numbers`

sagetrac-git · 2016-04-05T16:06:50Z

Changed commit from 2f8d672 to 3a26453

sagetrac-git · 2016-04-05T16:29:59Z

Changed commit from 3a26453 to b7f1ed8

sagetrac-git · 2016-04-05T16:29:59Z

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

`b7f1ed8`	`get_solver: Add another doctest`

dimpase · 2016-04-05T22:57:51Z

comment:30

in the last commit, the line

sage: p = get_solver('InteractiveLP', base_ring=QQ)

should be

sage: p = get_solver('InteractiveLP', base_ring=QQ); p

otherwise the doctest fails

sagetrac-git · 2016-04-05T23:21:12Z

Changed commit from b7f1ed8 to 8c1fd4a

sagetrac-git · 2016-04-05T23:21:12Z

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

`8c1fd4a`	`get_solver: Fix last doctest`

mkoeppe · 2016-04-05T23:22:43Z

comment:32

Thanks.
Another thing was wrong with this simple line. Annoyingly, the first argument to get_solver is not the solver name but rather the obscure argument constraint_generation.

dimpase · 2016-04-05T23:23:31Z

Reviewer: Andrey Novoseltsev, Dima Pasechnik

dimpase · 2016-04-05T23:23:31Z

comment:33

OK, good.

mkoeppe · 2016-04-05T23:24:20Z

comment:34

Thanks for reviewing!

vbraun · 2016-04-06T23:03:29Z

Changed branch from u/mkoeppe/mixedintegerlinearprogram__new_backend_using_interactivelpproblem to 8c1fd4a

mkoeppe added this to the sage-7.2 milestone Mar 26, 2016

mkoeppe added c: numerical labels Mar 26, 2016

This comment has been minimized.

Sign in to view

mkoeppe added the s: needs review label Mar 27, 2016

This comment has been minimized.

Sign in to view

dimpase added s: positive review and removed s: needs review labels Apr 5, 2016

vbraun removed the s: positive review label Apr 6, 2016

vbraun closed this as completed in 9ddd231 Apr 6, 2016

jdemeyer mentioned this issue Dec 29, 2022

Raise an error when constraints are added to the wrong MILP #19523

Open

MixedIntegerLinearProgram: New backend using InteractiveLPProblem #20296

MixedIntegerLinearProgram: New backend using InteractiveLPProblem #20296

Comments

mkoeppe commented Mar 26, 2016

mkoeppe commented Mar 27, 2016

mkoeppe commented Mar 27, 2016

mkoeppe commented Mar 27, 2016

mkoeppe commented Mar 27, 2016

This comment has been minimized.

This comment has been minimized.

novoselt commented Mar 27, 2016

sagetrac-git mannequin commented Mar 27, 2016

sagetrac-git mannequin commented Mar 27, 2016

mkoeppe commented Mar 27, 2016

novoselt commented Mar 27, 2016

sagetrac-git mannequin commented Mar 27, 2016

sagetrac-git mannequin commented Mar 27, 2016

mkoeppe commented Mar 27, 2016

mkoeppe commented Mar 27, 2016

sagetrac-git mannequin commented Mar 27, 2016

sagetrac-git mannequin commented Mar 27, 2016

mkoeppe commented Mar 27, 2016

sagetrac-git mannequin commented Mar 27, 2016

sagetrac-git mannequin commented Mar 27, 2016

sagetrac-git mannequin commented Mar 27, 2016

sagetrac-git mannequin commented Mar 27, 2016

sagetrac-git mannequin commented Mar 27, 2016

sagetrac-git mannequin commented Mar 27, 2016

sagetrac-git mannequin commented Mar 30, 2016

sagetrac-git mannequin commented Mar 31, 2016

sagetrac-git mannequin commented Mar 31, 2016

sagetrac-git mannequin commented Mar 31, 2016

sagetrac-git mannequin commented Mar 31, 2016

sagetrac-git mannequin commented Apr 3, 2016

sagetrac-git mannequin commented Apr 3, 2016

dimpase commented Apr 5, 2016

sagetrac-git mannequin commented Apr 5, 2016

sagetrac-git mannequin commented Apr 5, 2016

dimpase commented Apr 5, 2016

novoselt commented Apr 5, 2016

mkoeppe commented Apr 5, 2016

sagetrac-git mannequin commented Apr 5, 2016

sagetrac-git mannequin commented Apr 5, 2016

sagetrac-git mannequin commented Apr 5, 2016

sagetrac-git mannequin commented Apr 5, 2016

dimpase commented Apr 5, 2016

sagetrac-git mannequin commented Apr 5, 2016

sagetrac-git mannequin commented Apr 5, 2016

mkoeppe commented Apr 5, 2016

dimpase commented Apr 5, 2016

dimpase commented Apr 5, 2016

mkoeppe commented Apr 5, 2016

vbraun commented Apr 6, 2016