MixedIntegerLinearProgram.ambient_space, feasible_set, optimal_set

[mkoeppe]

We define some convenience methods that make it easy to construct sets and manifold objects corresponding to linear and mixed-integer linear optimization problems.

The ambient space is just a CombinatorialFreeModule or a ConditionSet or a EuclideanSpace, using the (formatted) variable names of the frontend as indices (CombinatorialFreeModule) / variable names.

The feasible set is also a ConditionSet or a manifold subset.

We extend the method get_values so that it can return elements of the ambient space (or its projections).

Followups:

• Define a backend chart using the variable names that the MILP backend uses
• Adding variables to the MILP will define a ContinuousMap that injects the previous MILP into the new one.

Depends on #21405 Depends on #31750

CC: @egourgoulhon @mjungmath @tscrim @yuan-zhou

Component: manifolds

Branch/Commit: u/mkoeppe/mixedintegerlinearprogram_ambient_manifold__feasible_subsetobjective_scalar_fieldoptimal_subset @ 3bad25c

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

[mkoeppe]

Branch: u/mkoeppe/mixedintegerlinearprogram_ambient_manifold__feasible_subsetobjective_scalar_fieldoptimal_subset

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Commit: 616dc06

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

3270098	MixedIntegerLinearProgram: New init arg 'name'
a001f20	MixedIntegerLinearProgram.interactive_lp_problem: Factor out helper functions _backend_variable_names etc
616dc06	MixedIntegerLinearProgram.ambient_manifold: New

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

b1b29a5

MixedIntegerLinearProgram.ambient_manifold: New

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 616dc06 to b1b29a5

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from b1b29a5 to 1c7a697

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

1c7a697

MixedIntegerLinearProgram.ambient_manifold: Add docstring

[mkoeppe]

comment:5

Perhaps the strange variable names for the backend, constructed in MIPVariable.__getitem__, should be changed to the format that _format_backend_variable_name uses.

sage: M2.<x> = MixedIntegerLinearProgram()                                                                                                               
sage: x[1,2]                                                                                                                                             
x_0
sage: x[3,4]                                                                                                                                             
x_1
sage: M2.get_backend().col_name(0)                                                                                                                       
'x[(1, 2)]'

This variable name is not compatible with LP (http://lpsolve.sourceforge.net/5.0/CPLEX-format.htm) or MPS file format (https://www.gurobi.com/documentation/9.1/refman/mps_format.html). So changing this to something that has a chance to work with these file formats, such as x_1_2, would be an improvement.

[mkoeppe]

comment:6

opened #31791 (MIPVariable: Better names for backend variable names)

[mkoeppe]

Description changed:

--- 
+++ 
@@ -1,9 +1,11 @@
-We define some convenience methods that make it easy to construct manifold objects corresponding to linear and mixed-integer linear optimization problems.
+We define some convenience methods that make it easy to construct sets and manifold objects corresponding to linear and mixed-integer linear optimization problems.

-The ambient manifold is just a Euclidean space, using the (formatted) variable names of the frontend.  We also define a backend chart using the variable names that the MILP backend uses.
+The ambient space is just a `ConditionSet` or a `EuclideanSpace`, using the (formatted) variable names of the frontend.

-Adding variables to the MILP will define a `ContinuousMap` that injects the previous MILP into the new one.
+The feasible set is also a `ConditionSet` or a manifold subset.

-Adding constraints to the MILP will set up a subset.
+Followups:
+- Define a backend chart using the variable names that the MILP backend uses
+- Adding variables to the MILP will define a `ContinuousMap` that injects the previous MILP into the new one.

[mkoeppe]

Dependencies: #21405

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 1c7a697 to dc3d974

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

a55d0a9	MixedIntegerLinearProgram.ambient_manifold: Add docstring
b46d482	src/sage/numerical/mip.pyx: WIP
1da89f6	Initial version of introducing coercion of base rings.
7f69146	review
69d5605	CombinatorialFreeModule.change_ring: New
bc88a0b	CombinatorialFreeModule._coerce_map_from_: Tighten test using base_extend
e82d44f	src/sage/combinat/free_module.py: Add doctest
083c680	src/sage/modules/with_basis/indexed_element.pyx: Revert changes to doctests
a475397	Merge #21405
dc3d974	WIP

[mkoeppe]

Description changed:

--- 
+++ 
@@ -1,8 +1,10 @@
 We define some convenience methods that make it easy to construct sets and manifold objects corresponding to linear and mixed-integer linear optimization problems.

-The ambient space is just a `ConditionSet` or a `EuclideanSpace`, using the (formatted) variable names of the frontend.
+The ambient space is just a `CombinatorialFreeModule` or a `ConditionSet` or a `EuclideanSpace`, using the (formatted) variable names of the frontend as indices (`CombinatorialFreeModule`) / variable names.

 The feasible set is also a `ConditionSet` or a manifold subset.
+
+We extend the method `get_values` so that it can return elements of the ambient space (or its projections).

 Followups:
 - Define a backend chart using the variable names that the MILP backend uses

[mkoeppe]

Changed dependencies from #21405 to #21405, #31750

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

8b2ada9	Merge #34839
98bd774	Merge #31750
2e2596a	MIPVariable.name: New
d8e70df	MixedIntegerLinearProgram: New init arg 'name'
fb935fb	MixedIntegerLinearProgram.interactive_lp_problem: Factor out helper functions _backend_variable_names etc
988b855	MixedIntegerLinearProgram.ambient_manifold: New
2ecd50d	MixedIntegerLinearProgram.ambient_manifold: Add docstring
f9b0cd7	src/sage/numerical/mip.pyx: WIP
89c733c	WIP
a1d1ca4	WIP

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from dc3d974 to a1d1ca4

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

3bad25c

WIP

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from a1d1ca4 to 3bad25c