When formalizing LP problems, one often has to deal with multi-index variables. When working with problems of large dimension, this is, frankly, a common thing.
The interrelationships of such multi-index variables in the objective function (linear form is also a linear optimization criterion) and constraints (in the form of linear equalities and inequalities) should be generated programmatically. When working with PuLP (LP library port for Python), two main approaches to such generation are used:
- Generating matrix A (constraint matrix) with Python list generators explicitly. For example, like this: Sudoku problem
- Generation of symbolic variables with binding to indices through dictionaries in an implicit form. This can be done manually via a dict or using a PuLP plugin
The classical LP problem of almost any dimension can be easily formalized in any of these ways, but when developing new structures of constraints (especially when the logic of interrelationships of variables becomes more complicated, new in meaning variables appear, some indices are abandoned or new indices are introduced) aggregation / decomposition of groups of variables, etc.) requires easy tracking of multi-index variables in the Python code itself, which is directly absent in the above approaches.
To solve this problem, it is proposed to use the PuLP-MiA add -on (link to the repository with a brief description of the functionality).
The author is far from thinking that this is a solution to all the problems arising in the formalization and solution of LP problems with a complex structure of restrictions, however, in many years of practice (especially when the modification occurs with long time intervals), the approach has proven itself well, mainly due to the following amenities:
- Creation / binding to existing variables happens automatically
- Explicit association of a variable name and its indices
- Variable name - arbitrary string
- Indexes - numeric values
- The number of indexes is conditionally unlimited (there may be no indexes at all)
- The results of solving the LP problem are displayed in the form of a dictionary, where the keys are nonzero multi - index variables (the behavior can be changed)
Perhaps the add-on will be very useful for someone in a long-term research of operations. MIT license. It is installed traditionally via pip .
PS For those who have finished reading, it will still be small
example of forming a series of restrictions))
from itertools import product
from pulp_mia import Task, Constraint
i_set = list(range(5))
j_set = list(range(5))
m_set = list(range(2))
g_set = list(range(4))
s_set = list(range(5))
k_set = list(range(5))
task = Task(debug=True)
for i, m, g, s, k in product(i_set, m_set, g_set, s_set, k_set):
a_new = Constraint('<=')
for j in j_set:
a_new.setCoeff(('x', i, j, m, g, s, k), 1)
a_new.setBValue(1)
task.addConstraint(a_new)
print(task)
#TASK info:
# NAME: test-task
# SIZE: 5000 x 1000
(for the rest, see the brief description of the addon )
PPS yes, somewhere deep under the hood lives an ordinary dictionary.