MIPVariable: Better names for backend variables

[mkoeppe]

(from #31742)

The current variable names for the backend, constructed in MIPVariable.__getitem__:

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)]'

Such variable names are 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).
They are also not compatible with the rules for Python identifiers - which becomes relevant when we want to use SR variables with the same name, as is done by InteractiveLPBackend.

So changing this to something that has a chance to work with these file formats and is a valid Python identifier, such as x_1_2, would be an improvement.

CC: @yuan-zhou

Component: linear programming

Branch/Commit: u/mkoeppe/mipvariable__better_names_for_backend_variable_names @ 637f609

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

[mkoeppe]

comment:1

Ideally, every variable name should pass the test sage.symbolic.ring.is_identifier

[mkoeppe]

Branch: u/mkoeppe/mipvariable__better_names_for_backend_variable_names

[mkoeppe]

Commit: 637f609

[mkoeppe]

comment:3

Here's a rough version

---

New commits:

637f609

MIPVariable.__getitem__: Try to make backend variable names proper identifiers

[yuan-zhou]

comment:4

Bug example:

sage: p.<x,y,z> = MixedIntegerLinearProgram(solver="GLPK")
p.add_constraint( p['b']+z[0]+2*y[1]+3*z[3]+x['1']+x[1]+p['a'] >=0, name='A' )
p.show()
Maximization:
  

Constraints:
  A: - x_0 - z_0 - 2.0 y_1 - 3.0 z_3 - x_1 - x_1 - x_6 <= 0.0
Variables:
  x_0 is a continuous variable (min=-oo, max=+oo)
  z_0 = x_1 is a continuous variable (min=-oo, max=+oo)
  y_1 = x_2 is a continuous variable (min=-oo, max=+oo)
  z_3 = x_3 is a continuous variable (min=-oo, max=+oo)
  x_1 = x_4 is a continuous variable (min=-oo, max=+oo)
  x_1 = x_5 is a continuous variable (min=-oo, max=+oo)
  x_6 is a continuous variable (min=-oo, max=+oo)
sage: p.write_lp("something3")                                                  
Writing problem data to 'something3'...
18 lines were written
\* Problem: Unknown *\

Maximize
 obj: 0 x_1

Subject To
 A: - x_7 - x_1 - x_1 - 3 z_3 - 2 y_1 - z_0 - x_1 <= 0

Bounds
 x_1 free
 z_0 free
 y_1 free
 z_3 free
 x_1 free
 x_1 free
 x_7 free

End

In mip.pyx:

• L823: name = self._first_variable_names.pop(0).
  I would remember the variable names in the MIP instance, and expose them to the user, to enable the reconstruction of variables of the MIP later. Maybe maintain a list self._variable_names
• L843: self._default_mipvariable = self.new_variable()
  I would give a name such as mipvar to default mipvariable, so that write_lp does not confuse variable x_1 of LinearFunction with variable x_1 of MIP.
• L876: return tuple(self.new_variable() for i in range(n))
  I would pass name from self._variable_names to the new variable constructor.
• L1255: default_name = str(self.linear_functions_parent()({i: 1}))
  This doesn't make sense to me. It displays x_i (string of sage.numerical.linear_functions.LinearFunction).
• L1258: varid_explainer[i] = '{0} = {1}'.format(s, default_name)... else...
  I would like to change the Variables section of p.show() above to ...[namified variable if name is given or mipvar_index otherwise]... = i-th column var is a continuous variable....
• L2657: sage: p = MixedIntegerLinearProgram(names=['m'], solver="GLPK").
  It is confusing to provide name m, and then to use new variable x as m.
• I notice that write_lp is properly implemented in coin backend (or perhaps I didn't install the package properly), as variable names are not passed to the backend.

[yuan-zhou]

comment:5

Regarding <MIPVariable xxx>._namify(multi_indices), I would trust the users to provide meaningful names, such that

• the final name of a MIP variable is xxx__iii, which consists of two parts connected by the double underscores: the variable sequence name xxx and the index iii.
• the variable sequence name 'xxx' (provided to mip.<'xxx'> = MixedIntegerLinearProgram(...), mip = MixedIntegerLinearProgram(names = ['xxx'], ...) or something_like_xxx = mip.new_variable(name='xxx')) should be a string that satisfies the rules of Python identifiers. In addition, it cannot start or end by an underscore, neither can it contain double underscores __. The default is mipvar.
• the index iii is the return of xxx._namify(multi_indices), where multi_indices is an integer, a string, a tuple or a list. Each element in multi_indices is either a integer or a string satisfying the rules of Python identifiers. (So a['1'] is not allowed, but a[1] is good.) In addition, when naming a new variable, the index element cannot contain _, nor space.

In mip.__getitem__(v), if v contains __, then it is understood as the composition of the sequence name xxx and the index iii; otherwise, it is understood as mipvar__v.

Caveats:

• The example a[4, 'string', QQ] in L142 of mip.pyx will no longer be allowed, since the last index QQ is not an integer nor a string. (We won't do str(QQ) to get Rational Field which contains a space.)
• variable sequence names w, z should be avoided if the user would like to use the interactive simplex method (These are slack variables in the "Vanderbei" style).

Examples: _namify(4, 'string', 'QQ') = '_4_string_QQ' and it will be possible to map a string back to a mip variable.

sage: p.<p_var> = MixedIntegerLinearProgram(solver='GLPK')                    
sage: p_var[4, 'string', 'QQ']                                                
x_0 # the return has type <class 'sage.numerical.linear_functions.LinearFunction'>
sage: p.get_backend().col_name(0)                                               
'p_var__4_string_QQ'
sage: p['p_var__4_string_QQ']
x_0
sage: p[4, 'string', 'QQ']
x_1
sage: p.get_backend().col_name(1)
'mipvar__4_string_QQ'
sage: p['mipvar__4_string_QQ']
x_1
sage: p['4_string_QQ']
x_1