Technical Details#

Note

The technical details page is in development.

1. A Deeper Walkthrough of OptFlow Dataflow Graph#

A main challenge of OptFlow is to design a “description language” for generic optimization problems. We aim to find a proper representation of optimization problems, which is expressive enough like natural language to describe nearly all kinds of problems, while still being highly analyzable to be solved by different optimization methodologies.

Languages to describe an optimization problem	Example	Expressibility	Analyzability	Coupling to actual optimization algorithms
Natural language	The following sentence: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?”	Very high (you can express almost any problem with natural language)	Very low (not formal or structured at all, can be ambiguous)	Not at all (no assumtion of solving technique from the description side, you are free to use any technique to solve it)
OptFlow Dataflow Graphs	Section 4 of the appendix	High (Turing-complete with the support of control flow)	High (graph structure is unambiguous, can be easily interpreted/analyzed by computer programs)	Moderately decoupled (some graph structures/operators may be coupled to specific solving techniques)
Mainstream modeling APIs (CVXPY, AMPL, Pyomo, Gurobi API, OR-Tools API for LP/MIP, etc.)	Gurobi modeling API to solve TSP	Moderately restrictive (with some significant restrictions like the linearity and no support of control flow)	Very high (as it is mathematically formalized)	Highly coupled (for the example, such a description is almost coupled to be solved by integer programming solvers)
APIs of algorithmic packages to solve specific types of problems (like OR-Tools)	OR-Tools to solve TSP	Very restrictive (only for a narrow type of problem. You may be able to customize some components by providing callback functions)	N/A (merely no analyze procedure is required as its form is already fixed)	Highly coupled (as it is only an interface to a specific algorithm)

1.1 Dataflow Graph Elements#

An OptFlow graph consists of nodes representing units of computation (operations), and direct edges representing the input/output relationship between vertices. Data will flow from source nodes (nodes with no incoming edges) to sink nodes (nodes with no outgoing edges), and perform specific computations when reaching intermediate nodes.

There are three main types of source nodes:

Constant: represents a fixed value in the graph, whose type can be scalar, tensor or more complex data structures such as list, set, and graph.
Input: similar to constant, but its value will only be fed into the dataflow graph when the graph is executed, allowing multiple problem instances to be executed from a single dataflow graph.
Variable: represents the decision variables that we want to optimize in an optimization problem, which can be a scalar or tensor. OptFlow graph support various type of variables including
- Binary: a boolean variable whose value can be 0 (false) or 1 (true).
- Categorical: an extension of binary variables, whose value can be \(\{0, \cdots, N-1\}\) given \(N\) categories.
- Continuous: an unbounded float number.
- Integer: a discrete version of continuous variables, whose value should be an integer.

And there are two main types of sink nodes:

Objective: a scalar node that we hope to minimize or maximize its value, by setting proper value for all the variable nodes in the dataflow graph.
Constraint: a boolean node whose value should be 1 (true) to be satisfied given the value of all variable nodes.

Also, there are a series of operation nodes between source and sink nodes to represent the computational process. For an operation node, the incoming edges represent the operands required by the operation, and the outgoing edges represent the destination of the result (as an operand of other operations). Customized operations are also supported by inheriting an operation class and rewriting the \texttt{run} method, which is useful for scenarios including black-box computation, such as the inclusion of game environments.

By assigning one objective node and an optional list of constraint nodes (for constrained problems) on an OptFlow dataflow graph, as well as the sense of objective (maximize or minimize), we can define an optimization problem in OptFlow.

1.2 Control Flow in OptFlow#

To allow Turing-complete descriptions of all computable objectives and constraints, OptFlow supports control flow within problem description. That is, OptFlow allows loops and conditions involving decision variables, which makes it closer to a “programming language” rather than restrictive “modeling APIs” such as CVXPY, OR-Tools and Gurobi API. Note that this is very different from the control flow in Python (or other host languages of modeling APIs), as the host language is not able to interact directly with variables or expressions to be optimized. More specifically, in OptFlow, control flows are supported by two special operators: flow.cond (flow.IfCond) and flow.for_loop (flow.ForLoop). For example, it is legal to describe an illustrative problem

maximize \(\sum_{i=0}^x f(i)\) w.r.t. \(x\), in which \(x \in \{0, 1, \cdots, 19\}\) and \(f(i) = \begin{cases}i, & i < 5 \\ 5 - i, & i > 5\end{cases}\)

in OptFlow as follows:

obj = flow.Constant(0)
x = flow.Variable(flow.integer, size=20)    # x = 0, 1, …, 19
with flow.ForLoop(x) as i:
    obj += flow.cond(i < 5, i, 5 - i)
prob = flow.Problem(obj, sense=flow.maximize)

However, it is not valid in OR-Tools (or other mainstream optimization frameworks like CVXPY) to write something equivlantly like

from ortools.linear_solver import pywraplp
solver = pywraplp.Solver.CreateSolver('SAT')
obj = 0
x = solver.IntVar(0, 20, 'x')
for i in range(x):
    obj += i if i < 5 else 5 - i
solver.Maximize(obj)

as variable x defined in OR-Tools as an IntVar cannot be directly processed by Python.

1.2.1 Condition Operator#

For condition operator flow.cond(c, a, b), it accepts three nodes as operands: the condition node c (a boolean value), the output node a when the condition satisfied, and the output node b when it is not satisfied. When interpreted, the interpreter will first compute the value of the condition node, and then return the value of node a or b depending on the condition value. In OptFlow’s Python binding, it is sometimes more natural to use a context manager flow.IfCond to create a condition operator. That is, the following code, assuming we already have two nodes x, y and a boolean node c, then

with flow.IfCond(c):
    x = a
    y = b

is equal to

x = flow.cond(c, a, x)
y = flow.cond(c, b, y)

Thus a single flow.IfCond context manager can generate multiple flow.cond operators in the dataflow graphs, which explains why there are two flow.cond operators in Figure 3 (b) while only one flow.IfCond context manager appears in Figure 3 (a). To allow this happen, we applied some inspectation techniques to track the change within the flow.IfCond context, and rewrite the changed node accordingly. Please check its implementation in operator.py for more details. (to access the code, please install the .whl package and locate to the installation directory)

1.2.2 Loop Operator#

The loop operator flow.for_loop(orig_nodes, updated_nodes, T, break_cond, loop_var) is more complicated. It accepts five operands as follows

orig_nodes and updated_nodes: two lists of nodes with the same length, in which orig_nodes[i] will be updated to updated_nodes[i] by the loop body.
T: an integer node indicating the maximum number of iterations of this loop operator, which could be set to flow.infinite if break_cond is set.
break_cond: an optional boolean node indicating whether to jump out of the loop for the current iteration.
**loop_var: a special “loop variable node” which only works in the loop body indicating the current number of iteration, and will be added by one in each iteration.** Thus the last element of orig_nodes and updated_nodes are always loop_var and flow.add(loop_var, 1) respectively.

For example, in the illustrative example above, the two lists orig_nodes and updated_nodes are [obj, i] and [flow.add(obj, flow.cond(i < 5, i, 5 - i), flow.add(i, 1)] respectively, indicating that

obj is updated to flow.add(obj, flow.cond(i < 5, i, 5 - i) in iteration i
i is updated to flow.add(i, 1) in iteration i

T is set to x, break_cond is set to None (as there is no flow.break_loop() in the loop body), and loop_var is set to i.

When interpreted, the interpreter will first compute the values of nodes in orig_nodes (denoted as orig_nodes_value, in the example it is [0, 0]) as their initial value. Then, the interpreter do the following steps iteratively:

Check whether the number of iterations is greater or equal than the value of T. Break the iterarion if so (or skip the check if T = flow.infinite)
Compute the value of node break_cond given orig_nodes_value. Break the iteration if the value is true.
Compute the value of nodes in updated_nodes (denoted as updated_nodes_value) given orig_nodes_value.
Replace orig_nodes_value with updated_nodes_value.

After the iteration, the flow.for_loop operator will return the final values of updated_nodes_value except the loop variable node which only works in the loop body. Following these steps, in the example, the value of [obj, i] will be updated to [1, 1], [3, 2], [6, 3], … until i >= x. The loop operator will return [15,] when x = 5.

To be more user-friendly, the loop operator is wrapped in a a context manager flow.ForLoop in OptFlow Python binding. T should be provided as the parameter of the context manager, and the manager will create a loop_var (in the illustrative example, it is i) and return it, so that it can be used in the loop body. Similar to flow.IfCond, context manager flow.ForLoop will track the change within its context, fill in the operands orig_nodes and updated_nodes automatically, and rewrite the changed node accordingly. For example, in the illustrative example at the start of this section, flow.ForLoop will track the change of obj in its context, adding it to orig_nodes and updated_nodes, and rewrite it to the 1st output of the flow.for_loop operator (using a flow.unpack(list, index) operator to specify the item within a list) when leaving the context.

1.3 Representing Multi-step Optimization Problems in OptFlow#

Multi-step (or “sequential”) structures widely exist in optimization problems, in which the value of decision variables should be decided following the step order. Many types of optimization methods are designed to exploit the multi-step structure to accelerate the solving procedure, such as rolling horizon, search, and reinforcement learning. OptFlow fully supports the representation of such multi-step structures in optimization problems, which not only compacts the dataflow graph, but also makes such structures exploitable to different types of optimization methods.

To represent a multi-step optimization problem, one needs to wrap the problem in a ForLoop operator specifying the number of steps, whose loop body represents a single step in the multi-step process, i.e., how to update the nodes in one iteration. Constraints can also be specified in the for loop, which will be applied on all the steps in a single iteration. An example is shown in Figure 3 of the paper representing the same knapsack problem, but with a multi-step structure assigning the order of decision for each box. Note that this is a more compact representation compared with Figure 2 in the paper since the size of the dataflow graph will not grow with the number of boxes. Such representation also enables additional optimization methods to engage in exploiting the multi-step structure

1.4 Constraints with Control Flow#

To allow constraints to be natually described in the control flow, we have some special design as follows

1.4.1 Constraints within Condition Operators#

Sometimes a constraint could have an attached condition. For example, in the knapsack problem shown in Figure 3, it is vaild to define the following constraint:

with flow.IfCond(x[i]):  # if item i is selected to be put into the knapsack
    # the total weight should not exceed the maximal weight after adding item i's weight
    constraints.append(total_weight + weight[i] <= max_weight)

In such a scenario, the constraint is only active when the condition holds. If the condition does not hold (e.g., item i is not selected in this example), then the constraints in the condition context should be ignored. To allow such a conditional constraint, OptFlow automatically rewrites a constraint constraint within a condition context cond as flow.logical_or(flow.logical_not(cond), constraint), in which flow.logical_or and flow.logical_not are logical OR and NOT operators in dataflow graphs. In this way, the constraint is always true (deactivated) when cond = False, and works as required when cond = True. For example, the actural constraint appended to the constraint list is

flow.logical_or(flow.logical_not(x[i]), total_weight + weight[i] <= max_weight)

which is only activated when x[i] = True. This explains why there is an OR node in Figure 3 (b) while it does not explicitly appear in Figure 3 (a). To allow this to happen, OptFlow needs to know whether a boolean node should be treated as a constraint to be rewritten. Thus, in OptFlow, the name constraints is a reversed keyword which should only be used as a list to append constraint nodes (this may change in the future). Once OptFlow detects that a node is added to a list named constraints, this node will be automatically recognized as a constraint and be rewritten as above.

1.4.2 Constraints within Loop Operators#

Constraints within loop operators are more restricted in OptFlow. Until now, it only works in a sequential setting introduced in Sec 3.3 (Sec 3.2 in the paper), which mainly serves as a filter to mask out invalid value selection of decision variables in the current step. For example, in the knapsack problem shown in Figure 3, it is vaild to define the following constraint:

with flow.ForLoop(3) as i:  # a 3-step sequential decision, represented as a for loop
    with flow.IfCond(x[i]):
        constraints.append(total_weight + weight[i] <= max_weight)

Then, when constraints is provided to an sequential optimization problem, the constraint in constraints will be checked in every single step. For example, in the above problem,

When i = 0, constraint total_weight + weight[0] <= max_weight will be checked if x[0] = True
When i = 1, constraint total_weight + weight[1] <= max_weight will be checked if x[1] = True
When i = 2, constraint total_weight + weight[2] <= max_weight will be checked if x[2] = True

2. Technical Details of Auto-Modeling#

2.1 Mathematical Programming#

To translate an OptFlow dataflow graph to a linear/integer programming model, OptFlow will traverse through the graph structure of the objective and all the constraints, in a recuisive manner. During the traversal,

# Input: `node` -- the node to be linearized
#        `coef` -- the coefficient of the expression
# Output: `var_and_coef` -- a dictionary recording the linearized expression
#         including the variable (key) with its coefficient (value)
def linearize(node: Node, coef: float, var_and_coef: dict):
    if node is an operator:
        if node is the multiple operator:  # (ax）
            # raise error if not linear (coefficient * variable)
            assert node.operands[0] is a constant or input node
            assert node.operands[1] is a variable node
            var_and_coef[node.operands[1]] += coef * node.operands[0].value
        elif node is the add operator:     # (x + y)
            for operand in node.operands:
                linearize(operand, coef, var_and_coef)
        elif node is the negate operator   # (-x)
            linearize(operand, -coef, var_and_coef)
        elif node is "get_array_item"      # (get an element from an array, x[i] or x[i, j])
            # linear techniques only applys to vectors or matrices
            assert len(node.operands[1].shape) <= 2
            linearize the operator as in the main paper
        elif
            ... # other operators that can be linearized
        else:
            raise Exception("operator cannot be linearized")
    elif node is a variable:
        var_and_coef[node] += coef
    elif node is a constant or input:
        var_and_coef['constant'] += coef * node.value
    else:
        raise Exception("graph node not supported")

Technical Details#

1. A Deeper Walkthrough of OptFlow Dataflow Graph#

1.1 Dataflow Graph Elements#

1.2 Control Flow in OptFlow#

1.2.1 Condition Operator#

1.2.2 Loop Operator#

1.3 Representing Multi-step Optimization Problems in OptFlow#

1.4 Constraints with Control Flow#

1.4.1 Constraints within Condition Operators#

1.4.2 Constraints within Loop Operators#

2. Technical Details of Auto-Modeling#

2.1 Mathematical Programming#

2.2 Reinforcement Learning and Dynamic Programming#