Opened 3 years ago

Closed 3 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) Commit: 8c1fd4ac48dac291a2cd0af8668287254977977a
Dependencies: Stopgaps:

Description (last modified by mkoeppe)

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

  • Branch set to u/mkoeppe/mixedintegerlinearprogram__new_backend_using_interactivelpproblem

comment:2 follow-up: Changed 3 years ago by mkoeppe

  • Authors set to Matthias Koeppe
  • Cc dimpase novoselt ncohen vdelecroix chapoton added
  • Commit set to 08d454882ce0a95b13f7d25c659c5cdde3b57090
  • Description modified (diff)
  • Status changed from new to needs_review

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:

c39dd7dFix typo in documentation
4596534New MIP backend: InteractiveLPBackend
78039beFix doctests (which never run)
08d4548Fix typo in docstring

comment:3 Changed 3 years ago by mkoeppe

  • Description modified (diff)

comment:4 in reply to: ↑ 2 Changed 3 years ago by novoselt

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).

comment:5 Changed 3 years ago by git

  • Commit changed from 08d454882ce0a95b13f7d25c659c5cdde3b57090 to bd77615a99408c3686ab763c1d5b7d3aac0a70bd

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

bd77615InteractiveLPProblem: New accessors problem_type, is_negative etc.

comment:6 Changed 3 years ago by mkoeppe

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)

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

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

  • Commit changed from bd77615a99408c3686ab763c1d5b7d3aac0a70bd to 4ecc46b5d2d9a19ccb444be01461aead630ff429

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

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

comment:9 in reply to: ↑ 7 Changed 3 years ago by mkoeppe

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

Last edited 3 years ago by mkoeppe (previous) (diff)

comment:10 Changed 3 years ago by mkoeppe

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

  • Commit changed from 4ecc46b5d2d9a19ccb444be01461aead630ff429 to ea99c1eb9a057eb5e2239a5f8f97288c6be9e9a7

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

ea99c1eInteractiveLPBackend, GenericBackend: Fix the variable_lower_bound, variable_upper_bound interfaces

comment:12 Changed 3 years ago by mkoeppe

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.)

Last edited 3 years ago by mkoeppe (previous) (diff)

comment:13 Changed 3 years ago by git

  • Commit changed from ea99c1eb9a057eb5e2239a5f8f97288c6be9e9a7 to e2319b5c5e172764a55622aac8651ca72f5fc30b

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

e2319b5InteractiveLPBackend.get_variable_value: Guard against standard-form transformations

comment:14 Changed 3 years ago by git

  • Commit changed from e2319b5c5e172764a55622aac8651ca72f5fc30b to e27f2975ba27666c9dd42ac0e3e5a7779f45b2ee

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

e27f297InteractiveLPBackend: Make base_ring an init argument

comment:15 Changed 3 years ago by git

  • Commit changed from e27f2975ba27666c9dd42ac0e3e5a7779f45b2ee to 5b0954f490d370c3dde5f02b0051991a42ad9912

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

5b0954fInteractiveLPBackend._variable_type_from_bounds: Add doctests

comment:16 Changed 3 years ago by git

  • Commit changed from 5b0954f490d370c3dde5f02b0051991a42ad9912 to c4b93aa570325967abd43f3509d284d3d5d1b0ce

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

c4b93aaInteractiveLPBackend: Fix old-style raise statements

comment:17 Changed 3 years ago by novoselt

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

  • Commit changed from c4b93aa570325967abd43f3509d284d3d5d1b0ce to 184249db87c5db29fe51fa54230bcc2cea8c4308

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

b0a3c1cGenericBackend: Add a missing '# optional - Nonexistent_LP_solver'
3770be0default_mip_solver: Handle 'InteractiveLP'
d91c776default_mip_solver, get_solver: Mention InteractiveLP in the documentation
eaede28get_solver: Add optional base_ring argument
184249dMixedIntegerLinearProgram: New base_ring init argument

comment:19 Changed 3 years ago by git

  • Commit changed from 184249db87c5db29fe51fa54230bcc2cea8c4308 to aa21bc6cc8cce0911d99278cb040542fafb7ad8d

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

95aa6d8InteractiveLPBackend.problem_name: Remove unreachable line
aa21bc6InteractiveLPBackend.dictionary, .interactive_lp_problem: Add docstrings and tests

comment:20 Changed 3 years ago by git

  • Commit changed from aa21bc6cc8cce0911d99278cb040542fafb7ad8d to 9cf5a75c62dfb8e56ea354724c156ae781af944f

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

28ffdb2Merge tag '7.2.beta1' into t/20296/mixedintegerlinearprogram__new_backend_using_interactivelpproblem
9cf5a75LinearFunction._coeff_formatter: Handle general base_rings

comment:21 Changed 3 years ago by git

  • Commit changed from 9cf5a75c62dfb8e56ea354724c156ae781af944f to 806e6b62209a29c3f996f27be3b3ecbf8ea39599

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

806e6b6InteractiveLPBackend: Add class docstring

comment:22 Changed 3 years ago by git

  • Commit changed from 806e6b62209a29c3f996f27be3b3ecbf8ea39599 to 00ab3502d494595f01ceaa1e9143fe4b14233360

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

eb4b73fInteractiveLPBackend: Add another doctest
33b3f52Merge tag '7.2.beta2' into t/20296/mixedintegerlinearprogram__new_backend_using_interactivelpproblem
00ab350InteractiveLPBackend: Add final doctest

comment:23 Changed 3 years ago by dimpase

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

comment:24 Changed 3 years ago by git

  • Commit changed from 00ab3502d494595f01ceaa1e9143fe4b14233360 to 2f8d672a72c4c38ec1e354b2413eb405b68d30fd

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

2f8d672InteractiveLPBackend: Remove commented-out code

comment:25 Changed 3 years ago by dimpase

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

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

comment:27 Changed 3 years ago by mkoeppe

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.)

Last edited 3 years ago by mkoeppe (previous) (diff)

comment:28 Changed 3 years ago by git

  • Commit changed from 2f8d672a72c4c38ec1e354b2413eb405b68d30fd to 3a264531bcb29e585739edc0bd3222e9fd321b75

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

3a26453InteractiveLPBackend: Expand example with algebraic numbers

comment:29 Changed 3 years ago by git

  • Commit changed from 3a264531bcb29e585739edc0bd3222e9fd321b75 to b7f1ed8c7e64dad808bf92edaec7d1cb100812b5

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

b7f1ed8get_solver: Add another doctest

comment:30 Changed 3 years ago by dimpase

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

  • Commit changed from b7f1ed8c7e64dad808bf92edaec7d1cb100812b5 to 8c1fd4ac48dac291a2cd0af8668287254977977a

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

8c1fd4aget_solver: Fix last doctest

comment:32 Changed 3 years ago by mkoeppe

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

  • Reviewers set to Andrey Novoseltsev, Dima Pasechnik
  • Status changed from needs_review to positive_review

OK, good.

comment:34 Changed 3 years ago by mkoeppe

Thanks for reviewing!

comment:35 Changed 3 years ago by vbraun

  • Branch changed from u/mkoeppe/mixedintegerlinearprogram__new_backend_using_interactivelpproblem to 8c1fd4ac48dac291a2cd0af8668287254977977a
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.