Opened 5 years ago
Closed 5 years ago
#20296 closed enhancement (fixed)
MixedIntegerLinearProgram: New backend using InteractiveLPProblem
Reported by: | mkoeppe | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-7.2 |
Component: | numerical | Keywords: | lp |
Cc: | dimpase, novoselt, ncohen, vdelecroix, chapoton | Merged in: | |
Authors: | Matthias Koeppe | Reviewers: | Andrey Novoseltsev, Dima Pasechnik |
Report Upstream: | N/A | Work issues: | |
Branch: | 8c1fd4a (Commits, GitHub, GitLab) | Commit: | 8c1fd4ac48dac291a2cd0af8668287254977977a |
Dependencies: | Stopgaps: |
Description (last modified by )
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.)
Change History (35)
comment:1 Changed 5 years ago by
- Branch set to u/mkoeppe/mixedintegerlinearprogram__new_backend_using_interactivelpproblem
comment:2 follow-up: ↓ 4 Changed 5 years ago by
- Cc dimpase novoselt ncohen vdelecroix chapoton added
- Commit set to 08d454882ce0a95b13f7d25c659c5cdde3b57090
- Description modified (diff)
- Status changed from new to needs_review
comment:3 Changed 5 years ago by
- Description modified (diff)
comment:4 in reply to: ↑ 2 Changed 5 years ago by
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))
orMixedIntegerLinearProgram(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).
comment:5 Changed 5 years ago by
- Commit changed from 08d454882ce0a95b13f7d25c659c5cdde3b57090 to bd77615a99408c3686ab763c1d5b7d3aac0a70bd
Branch pushed to git repo; I updated commit sha1. New commits:
bd77615 | InteractiveLPProblem: New accessors problem_type, is_negative etc.
|
comment:6 Changed 5 years ago by
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
InteractiveLPProblem
would support an additive constant in the objective function (seeobj_constant_term
in my code)
comment:7 follow-up: ↓ 9 Changed 5 years ago by
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.
comment:8 Changed 5 years ago by
- Commit changed from bd77615a99408c3686ab763c1d5b7d3aac0a70bd to 4ecc46b5d2d9a19ccb444be01461aead630ff429
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
|
comment:9 in reply to: ↑ 7 Changed 5 years ago by
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 justself._problem_type
as is and mention in documentation that there is alsois_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...
comment:10 Changed 5 years ago by
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.
comment:11 Changed 5 years ago by
- Commit changed from 4ecc46b5d2d9a19ccb444be01461aead630ff429 to ea99c1eb9a057eb5e2239a5f8f97288c6be9e9a7
Branch pushed to git repo; I updated commit sha1. New commits:
ea99c1e | InteractiveLPBackend, GenericBackend: Fix the variable_lower_bound, variable_upper_bound interfaces
|
comment:12 Changed 5 years ago by
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.)
comment:13 Changed 5 years ago by
- Commit changed from ea99c1eb9a057eb5e2239a5f8f97288c6be9e9a7 to e2319b5c5e172764a55622aac8651ca72f5fc30b
Branch pushed to git repo; I updated commit sha1. New commits:
e2319b5 | InteractiveLPBackend.get_variable_value: Guard against standard-form transformations
|
comment:14 Changed 5 years ago by
- Commit changed from e2319b5c5e172764a55622aac8651ca72f5fc30b to e27f2975ba27666c9dd42ac0e3e5a7779f45b2ee
Branch pushed to git repo; I updated commit sha1. New commits:
e27f297 | InteractiveLPBackend: Make base_ring an init argument
|
comment:15 Changed 5 years ago by
- Commit changed from e27f2975ba27666c9dd42ac0e3e5a7779f45b2ee to 5b0954f490d370c3dde5f02b0051991a42ad9912
Branch pushed to git repo; I updated commit sha1. New commits:
5b0954f | InteractiveLPBackend._variable_type_from_bounds: Add doctests
|
comment:16 Changed 5 years ago by
- Commit changed from 5b0954f490d370c3dde5f02b0051991a42ad9912 to c4b93aa570325967abd43f3509d284d3d5d1b0ce
Branch pushed to git repo; I updated commit sha1. New commits:
c4b93aa | InteractiveLPBackend: Fix old-style raise statements
|
comment:17 Changed 5 years ago by
I think everything and a little more but name clashes are implemented in #20311.
Regarding variable names, it is sort of by design that auxiliary variable can be one of the decision ones - that's how auxiliary problems are distinguished. It may not be the best choice but changing it should be done carefully. In all other cases name clashes should throw errors and users are responsible for either adjusting their choices or overriding defaults to avoid conflict.
comment:18 Changed 5 years ago by
- Commit changed from c4b93aa570325967abd43f3509d284d3d5d1b0ce to 184249db87c5db29fe51fa54230bcc2cea8c4308
Branch pushed to git repo; I updated commit sha1. New commits:
b0a3c1c | GenericBackend: Add a missing '# optional - Nonexistent_LP_solver'
|
3770be0 | default_mip_solver: Handle 'InteractiveLP'
|
d91c776 | default_mip_solver, get_solver: Mention InteractiveLP in the documentation
|
eaede28 | get_solver: Add optional base_ring argument
|
184249d | MixedIntegerLinearProgram: New base_ring init argument
|
comment:19 Changed 5 years ago by
- Commit changed from 184249db87c5db29fe51fa54230bcc2cea8c4308 to aa21bc6cc8cce0911d99278cb040542fafb7ad8d
comment:20 Changed 5 years ago by
- Commit changed from aa21bc6cc8cce0911d99278cb040542fafb7ad8d to 9cf5a75c62dfb8e56ea354724c156ae781af944f
comment:21 Changed 5 years ago by
- Commit changed from 9cf5a75c62dfb8e56ea354724c156ae781af944f to 806e6b62209a29c3f996f27be3b3ecbf8ea39599
Branch pushed to git repo; I updated commit sha1. New commits:
806e6b6 | InteractiveLPBackend: Add class docstring
|
comment:22 Changed 5 years ago by
- Commit changed from 806e6b62209a29c3f996f27be3b3ecbf8ea39599 to 00ab3502d494595f01ceaa1e9143fe4b14233360
comment:23 Changed 5 years ago by
there are long commented out blocks, like cpdef solver_parameter
, and ones for file output. Can you remove them?
comment:24 Changed 5 years ago by
- Commit changed from 00ab3502d494595f01ceaa1e9143fe4b14233360 to 2f8d672a72c4c38ec1e354b2413eb405b68d30fd
Branch pushed to git repo; I updated commit sha1. New commits:
2f8d672 | InteractiveLPBackend: Remove commented-out code
|
comment:25 Changed 5 years ago by
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?
comment:26 Changed 5 years ago by
#20311 implements going back from the standard form, so will allow to address this problem.
comment:27 Changed 5 years ago by
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.)
comment:28 Changed 5 years ago by
- Commit changed from 2f8d672a72c4c38ec1e354b2413eb405b68d30fd to 3a264531bcb29e585739edc0bd3222e9fd321b75
Branch pushed to git repo; I updated commit sha1. New commits:
3a26453 | InteractiveLPBackend: Expand example with algebraic numbers
|
comment:29 Changed 5 years ago by
- Commit changed from 3a264531bcb29e585739edc0bd3222e9fd321b75 to b7f1ed8c7e64dad808bf92edaec7d1cb100812b5
Branch pushed to git repo; I updated commit sha1. New commits:
b7f1ed8 | get_solver: Add another doctest
|
comment:30 Changed 5 years ago by
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
comment:31 Changed 5 years ago by
- Commit changed from b7f1ed8c7e64dad808bf92edaec7d1cb100812b5 to 8c1fd4ac48dac291a2cd0af8668287254977977a
Branch pushed to git repo; I updated commit sha1. New commits:
8c1fd4a | get_solver: Fix last doctest
|
comment:32 Changed 5 years ago by
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
.
comment:33 Changed 5 years ago by
- Reviewers set to Andrey Novoseltsev, Dima Pasechnik
- Status changed from needs_review to positive_review
OK, good.
comment:34 Changed 5 years ago by
Thanks for reviewing!
comment:35 Changed 5 years ago by
- Branch changed from u/mkoeppe/mixedintegerlinearprogram__new_backend_using_interactivelpproblem to 8c1fd4ac48dac291a2cd0af8668287254977977a
- Resolution set to fixed
- Status changed from positive_review to closed
Needs review.
Some remarks:
InteractiveLPProblem
(_constraint_types
,_variable_types
,_problem_type
,_is_negative
) because some accessor methods are missing. Should I be adding them?MixedIntegerLinearProgram(solver=('InteractiveLP', AA))
orMixedIntegerLinearProgram(solver='InteractiveLP', base_ring=AA
New commits:
Fix typo in documentation
New MIP backend: InteractiveLPBackend
Fix doctests (which never run)
Fix typo in docstring