Opened 6 years ago
Closed 5 years ago
#20296 closed enhancement (fixed)
MixedIntegerLinearProgram: New backend using InteractiveLPProblem
Reported by:  mkoeppe  Owned by:  

Priority:  major  Milestone:  sage7.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 6 years ago by
 Branch set to u/mkoeppe/mixedintegerlinearprogram__new_backend_using_interactivelpproblem
comment:2 followup: ↓ 4 Changed 6 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 6 years ago by
 Description modified (diff)
comment:4 in reply to: ↑ 2 Changed 6 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 6 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 6 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 followup: ↓ 9 Changed 6 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 nonstandard 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 6 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 6 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 standardform problem that is created while solving.
Passing through parameters to the constructor would make sense. And adding a constant to nonstandard 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 6 years ago by
By the way, the interactive_simplex_method
code should probably check for variablename clashes between autogenerated and usersupplied variable names. It gets quite confused, for example, when a variable named "x0" is introduced because it thinks it is the primalphase1 auxiliary variable.
comment:11 Changed 6 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 6 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 6 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 standardform transformations

comment:14 Changed 6 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 6 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 6 years ago by
 Commit changed from 5b0954f490d370c3dde5f02b0051991a42ad9912 to c4b93aa570325967abd43f3509d284d3d5d1b0ce
Branch pushed to git repo; I updated commit sha1. New commits:
c4b93aa  InteractiveLPBackend: Fix oldstyle raise statements

comment:17 Changed 6 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 6 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 commentedout 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) <ipythoninput21d8eb94d9ce26> 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 standardform transformation is not implemented") 703 return self.final_dictionary.basic_solution()[variable] 704 NotImplementedError: Undoing the standardform 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)]
(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