MixedIntegerLinearProgram: New backend using InteractiveLPProblem

[Matthias Köppe]

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

[Matthias Köppe]

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

[Andrey Novoseltsev]

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

[git]

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

​bd77615

InteractiveLPProblem: New accessors problem_type, is_negative etc.

[Matthias Köppe]

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)

[Andrey Novoseltsev]

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.

[git]

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

[Matthias Köppe]

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

[Matthias Köppe]

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.

[git]

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

​ea99c1e

InteractiveLPBackend, GenericBackend: Fix the variable_lower_bound, variable_upper_bound interfaces

[Matthias Köppe]

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

[git]

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

​e2319b5

InteractiveLPBackend.get_variable_value: Guard against standard-form transformations

[git]

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

​e27f297

InteractiveLPBackend: Make base_ring an init argument

[git]

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

​5b0954f

InteractiveLPBackend._variable_type_from_bounds: Add doctests

[git]

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

​c4b93aa

InteractiveLPBackend: Fix old-style raise statements

[Andrey Novoseltsev]

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.

[git]

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

[git]

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

​95aa6d8	InteractiveLPBackend.problem_name: Remove unreachable line
​aa21bc6	InteractiveLPBackend.dictionary, .interactive_lp_problem: Add docstrings and tests

[git]

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

[git]

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

​806e6b6

InteractiveLPBackend: Add class docstring

[git]

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

[Dima Pasechnik]

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

[git]

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

​2f8d672

InteractiveLPBackend: Remove commented-out code

[Dima Pasechnik]

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?

[Andrey Novoseltsev]

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

[Matthias Köppe]

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

[git]

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

​3a26453

InteractiveLPBackend: Expand example with algebraic numbers

[git]

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

​b7f1ed8

get_solver: Add another doctest

[Dima Pasechnik]

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

[git]

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

​8c1fd4a

get_solver: Fix last doctest

[Matthias Köppe]

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.

[Dima Pasechnik]

OK, good.

[Matthias Köppe]

Thanks for reviewing!