| Name | xaddpy JSON |
| Version |
0.2.5
JSON |
| download |
| home_page | https://github.com/jihwan-jeong/xaddpy |
| Summary | XADD package in Python |
| upload_time | 2024-02-08 16:24:36 |
| maintainer | |
| docs_url | None |
| author | Jihwan Jeong |
| requires_python | >=3.8 |
| license | MIT License Copyright (c) 2022 jihwan-jeong Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
| keywords |
xadd
xadd python
symbolic diagram
|
| VCS |
 |
| bugtrack_url |
|
| requirements |
No requirements were recorded.
|
| Travis-CI |
No Travis.
|
| coveralls test coverage |
No coveralls.
|
# Python Implementation of XADD
This repository implements the Python version of XADD (eXtended Algebraic Decision Diagrams) which was first introduced in [Sanner et al. (2011)](https://arxiv.org/pdf/1202.3762.pdf); you can find the original Java implementation from [here](https://github.com/ssanner/xadd-inference).
Our Python XADD code uses [SymEngine](https://github.com/symengine/symengine.py) for symbolically maintaining all variables and related operations, and [PULP](https://github.com/coin-or/pulp) is used for pruning unreachable paths. Note that we only check linear conditionals. If you have Gurobi installed and configured in the conda environment, then PULP will use Gurobi for solving (MI)LPs; otherwise, the default solver ([CBC](https://github.com/coin-or/Cbc)) is going to be used. However, we do not actively support optimizers other than Gurobi for now.
Note that the implementation for [EMSPO](https://proceedings.mlr.press/v162/jeong22a/jeong22a.pdf) --- Exact symbolic reduction of linear Smart Predict+Optimize to MILP (Jeong et al., ICML-22) --- has been moved to the branch [emspo](https://github.com/jihwan-jeong/xaddpy/tree/emspo).
You can find the implementation for the [CPAIOR-23](https://ssanner.github.io/papers/cpaior23_dblpsve.pdf) work --- A Mixed-Integer Linear Programming Reduction of Disjoint Bilinear Programs via Symbolic
Variable Elimination --- in [examples/dblp](examples/dblp).
## Installation
**Load your Python virtual environment then type the following commands for package installation**
```shell
pip install xaddpy
# Optional: if you want to use Gurobi for the 'reduce_lp' method
# that prunes out unreachable partitions using LP solvers
pip install gurobipy # If you have a license
```
## Installing pygraphviz for visualization
With `pygraphviz`, you can visualize a given XADD in a graph format, which can be very useful. Here, we explain how to install the package.
To begin with, you need to install the following:
- graphviz
- pygraphviz
Make sure you have activated the right conda environment with `conda activate YOUR_CONDA_ENVIRONMENT`.
### Step 1: Installing graphviz
1. For Ubuntu/Debian users, run the following command.
```shell
sudo apt-get install graphviz graphviz-dev
```
2. For Fedora and Red Hat systems, you can do as follows.
```shell
sudo dnf install graphviz graphviz-devel
```
3. For Mac users, you can use `brew` to install `graphviz`.
```shell
brew install graphviz
```
Unfortunately, we do not provide support for Windows systems, though you can refer to the [pygraphviz documentation](https://pygraphviz.github.io/documentation/stable/install.html) for information.
### Step 2: Installing pygraphviz
1. Linux systems
```shell
pip install pygraphviz
```
2. MacOS
```shell
python -m pip install \
--global-option=build_ext \
--global-option="-I$(brew --prefix graphviz)/include/" \
--global-option="-L$(brew --prefix graphviz)/lib/" \
pygraphviz
```
Note that due to the default installation location by `brew`, you need to provide some additional options for `pip` installation.
## Using xaddpy
You can find useful XADD usecases in the [xaddpy/tests/test_bool_var.py](xaddpy/tests/test_bool_var.py) and [xaddpy/tests/test_xadd.py](xaddpy/tests/test_xadd.py) files. Here, we will first briefly discuss different ways to build an initial XADD that you want to work with.
### Loading from a file
If you know the entire structure of an initial XADD, then you can create a text file specifying the XADD and load it using the `XADD.import_xadd` method. It's important that, when you manually write down the XADD you have, you follow the same syntax rule as in the example file shown below.
Below is a part of the XADD written in [xaddpy/tests/ex/bool_cont_mixed.xadd](xaddpy/tests/ex/bool_cont_mixed.xadd):
```
...
( [x - y <= 0]
( [2 * x + y <= 0]
([x])
([y])
)
( [b3]
([2 * x])
([2 * y])
)
)
...
```
Here, `[x-y <= 0]` defines a decision expression; its true branch is another node with the decision `[2 * x + y <= 0]`, while the decision of the false branch is a Boolean variable `b3`. Similarly, if `[2 * x + y <= 0]` holds true, then we get the leaf value `[x]`; otherwise, we get `[y]`. _All expressions should be wrapped with brackets, including Boolean variables._ A SymEngine `Symbol` object will be created for each unique variable.
To load this XADD, you can do the following:
```python
from xaddpy import XADD
context = XADD()
fname = 'xaddpy/tests/ex/bool_cont_mixed.xadd'
orig_xadd = context.import_xadd(fname)
```
Following the Java implementation, we call the instantiated XADD object `context`. This object maintains and manages all existing/new nodes and decision expressions. For example, `context._id_to_node` is a Python dictionary that stores mappings from node IDs (`int`) to the corresponding `Node` objects. For more information, please refer to the [constructor of the `XADD` class](xaddpy/xadd/xadd.py#L57).
To check whether you've got the right XADD imported, you can print it out.
```python
print(f"Imported XADD: \n{context.get_repr(orig_xadd)}")
```
The `XADD.get_repr` method will return `repr(node)` and the string representation of each XADD node is implemented in [xaddpy/xadd/node.py](xaddpy/xadd/node.py). Beware that the printing method can be slow for a large XADD.
### Recursively building an XADD
Another way of creating an initial XADD node is by recursively building it with the `apply` method. A very simple example would be something like this:
```python
from xaddpy import XADD
import symengine.lib.symengine_wrapper as core
context = XADD()
x_id = context.convert_to_xadd(core.Symbol('x'))
y_id = context.convert_to_xadd(core.Symbol('y'))
sum_node_id = context.apply(x_id, y_id, op='add')
comp_node_id = context.apply(sum_node_id, y_id, op='min')
print(f"Sum node:\n{context.get_repr(sum_node_id)}\n")
print(f"Comparison node:\n{context.get_repr(comp_node_id)}")
```
You can check that the print output shows
```
Sum node:
( [x + y] ) node_id: 9
Comparison node:
( [x <= 0] (dec, id): 10001, 10
( [x + y] ) node_id: 9
( [y] ) node_id: 8
)
```
which is the expected outcome!
Check out a much more comprehensive example demonstrating the recursive construction of a nontrivial XADD from here: [pyRDDLGym/XADD/RDDLModelXADD.py](https://github.com/ataitler/pyRDDLGym/blob/01955ee7bca2861124709c116f419f2927c04a89/pyRDDLGym/XADD/RDDLModelXADD.py#L124).
### Directly creating an XADD node
Finally, you might want to build a constant node, an arbitrary decision expression, and a Boolean decision directly. To this end, let's consider building the following XADD:
```
([b]
([1])
([x + y <= 0]
([0])
([2])
)
)
```
To do this, we will first create an internal node whose decision is `[x + y <= 0]`, the low and the high branches are `[0]` and `[2]` (respectively). Using `SymEngine`'s `S` function (or you can use `sympify`), you can turn an algebraic expression involving variables and numerics into a symbolic expression. Given this decision expression, you can get its unique index using `XADD.get_dec_expr_index` method. You can use the decision ID along with the ID of the low and high nodes connected to the decision to create the corresponding decision node, using `XADD.get_internal_node`.
```python
import symengine.lib.symengine_wrapper as core
from xaddpy import XADD
context = XADD()
# Get the unique ID of the decision expression
dec_expr: core.Basic = core.S('x + y <= 0')
dec_id, is_reversed = context.get_dec_expr_index(dec_expr, create=True)
# Get the IDs of the high and low branches: [0] and [2], respectively
high: int = context.get_leaf_node(core.S(0))
low: int = context.get_leaf_node(core.S(2))
if is_reversed:
low, high = high, low
# Create the decision node with the IDs
dec_node_id: int = context.get_internal_node(dec_id, low=low, high=high)
print(f"Node created:\n{context.get_repr(dec_node_id)}")
```
Note that `XADD.get_dec_expr_index` returns a boolean variable `is_reversed` which is `False` if the canonical decision expression of the given decision has the same inequality direction. If the direction has changed, then `is_reversed=True`; in this case, low and high branches should be swapped.
Another way of creating this node is to use the `XADD.get_dec_node` method. This method can only be used when the low and high nodes are terminal nodes containing leaf expressions.
```python
dec_node_id = context.get_dec_node(dec_expr, low_val=core.S(2), high_val=core.S(0))
```
Note also that you need to wrap constants with the `core.S` function to turn them into `core.Basic` objects.
Now, it remains to create a decision node with the Boolean variable `b` and connect it to its low and high branches.
```python
from xaddpy.utils.symengine import BooleanVar
b = BooleanVar(core.Symbol('b'))
dec_b_id, _ = context.get_dec_expr_index(b, create=True)
```
First of all, you need to import and instantiate a `BooleanVar` object for a Boolean variable. Otherwise, the variable won't be recognized as a Boolean variable in XADD operations!
Once you have the decision ID, we can finally link this decision node with the node created earlier.
```python
high: int = context.get_leaf_node(core.S(1))
node_id: int = context.get_internal_node(dec_b_id, low=dec_node_id, high=high)
print(f"Node created:\n{context.get_repr(node_id)}")
```
And we get the following print outputs.
```
Output:
Node created:
( [b] (dec, id): 2, 9
( [1] ) node_id: 1
( [x + y <= 0] (dec, id): 10001, 8
( [0] ) node_id: 0
( [2] ) node_id: 7
)
)
```
### XADD Operations
#### XADD.apply(id1: int, id2: int, op: str)
You can perform the `apply` operation to two XADD nodes with IDs `id1` and `id2`. Below is the list of the supported operators (`op`):
**Non-Boolean operations**
- 'max', 'min'
- 'add', 'subtract'
- 'prod', 'div'
**Boolean operations**
- 'and'
- 'or'
**Relational operations**
- '!=', '=='
- '>', '>='
- '<', '<='
#### XADD.unary_op(node_id: int, op: str) (unary operations)
You can also apply the following unary operators to a single XADD node recursively (also check `UNARY_OP` in [xaddpy/utils/global_vars.py](xaddpy/utils/global_vars.py)). In this case, an operator will be applied to each and every leaf value of a given node. Hence, the decision expressions will remain unchanged.
- 'sin, 'cos', 'tan'
- 'sinh', 'cosh', 'tanh'
- 'exp', 'log', 'log2', 'log10', 'log1p'
- 'floor', 'ceil'
- 'sqrt', 'pow'
- '-', '+'
- 'sgn' (sign function... sgn(x) = 1 if x > 0; 0 if x == 0; -1 otherwise)
- 'abs'
- 'float', 'int'
- '~' (negation)
The `pow` operation requires an additional argument specifying the exponent.
#### XADD.evaluate(node_id: int, bool_assign: dict, cont_assign: bool, primitive_type: bool)
When you want to assign concrete values to Boolean and continuous variables, you can use this method. An example is provided in the `test_mixed_eval` function defined in [xaddpy/tests/test_bool_var.py](xaddpy/tests/test_bool_var.py).
As another example, let's say we want to evaluate the XADD node defined a few lines above.
```python
x, y = core.symbols('x y')
bool_assign = {b: True}
cont_assign = {x: 2, y: -1}
res = context.evaluate(node_id, bool_assign=bool_assign, cont_assign=cont_assign)
print(f"Result: {res}")
```
In this case, `b=True` will directly leads to the leaf value of `1` regardless of the assignment given to `x` and `y` variables.
```python
bool_assign = {b: False}
res = context.evaluate(node_id, bool_assign=bool_assign, cont_assign=cont_assign)
print(f"Result: {res}")
```
If we change the value of `b`, we can see that we get `2`. Note that you have to make sure that all symbolic variables get assigned specific values; otherwise, the function will return `None`.
#### XADD.substitute(node_id: int, subst_dict: dict)
If instead you want to assign values to a subset of symbolic variables while leaving the other variables as-is, you can use the `substitute` method. Similar to `evaluate`, you need to pass in a dictionary mapping SymEngine `Symbol`s to their concrete values.
For example,
```python
subst_dict = {x: 1}
node_id_after_subs = context.substitute(node_id, subst_dict)
print(f"Result:\n{context.get_repr(node_id_after_subs)}")
```
which outputs
```
Result:
( [b] (dec, id): 2, 16
( [1] ) node_id: 1
( [y + 1 <= 0] (dec, id): 10003, 12
( [0] ) node_id: 0
( [2] ) node_id: 7
)
)
```
as expected.
#### XADD.collect_vars(node_id: int)
If you want to extract all Boolean and continuous symbols existing in an XADD node, you can use this method.
```python
var_set = context.collect_vars(node_id)
print(f"var_set: {var_set}")
```
```
Output:
var_set: {y, b, x}
```
This method can be useful to figure out which variables need to have values assigned in order to evaluate a given XADD node.
#### XADD.make_canonical(node_id: int)
This method gives a canonical order to an XADD that is potentially unordered. Note that the `apply` method already calls `make_canonical` when the `op` is one of `('min', 'max', '!=', '==', '>', '>=', '<', '<=', 'or', 'and')`.
#### Variable Elimination
1. Sum out: `XADD.op_out(node_id: int, dec_id: int, op: str = 'add')`
Let's say we have a joint probability distribution function over Boolean variables `b1, b2`, i.e., `P(b1, b2)` as in the following example. `P(b1, b2)=`
```
( [b1]
( [b2]
( [0.25] )
( [0.3] )
)
( [b2]
( [0.1] )
( [0.35] )
)
)
```
Notice that the values are non-negative and sum up to one, making this a valid probability distribution. Now, one may be interested in marginalizing out a variable `b2` to get `P(b1) = \sum_{b2} P(b1, b2)`. This can be done in XADD by using the `op_out` method.
Let's directly dive into an example:
```python
# Load the joint probability as XADD
p_b1b2 = context.import_xadd('xaddpy/tests/ex/bool_prob.xadd')
# Get the decision index of `b2`
b2 = BooleanVar(core.Symbol('b2'))
b2_dec_id, _ = context.get_dec_expr_index(b2, create=False)
# Marginalize out `b2`
p_b1 = context.op_out(node_id=p_b1b2, dec_id=b2_dec_id, op='add')
print(f"P(b1): \n{context.get_repr(p_b1)}")
```
```
Output:
P(b1):
( [b1] (dec, id): 1, 26
( [0.55] ) node_id: 25
( [0.45] ) node_id: 24
)
```
As expected, the obtained `P(b1)` is a function of only `b1` variable, and the probabilities sum up to `1`.
2. Prod out
Similarly, if we specify `op='prod'`, we can 'prod out' a Boolean variable from a given XADD.
3. Max out (or min out) continuous variables: `XADD.min_or_max_var(node_id: int, var: VAR_TYPE, is_min: bool)`
One of the most interesting and useful applications of symbolic variable elimination is 'maxing out' or 'minning out' **continuous** variable(s) from a symbolic function. See [Jeong et al. (2023)](https://ssanner.github.io/papers/cpaior23_dblpsve.pdf) and [Jeong et al. (2022)](https://proceedings.mlr.press/v162/jeong22a/jeong22a.pdf) for more detailed discussions. Look up the `min_or_max_var` method in the xadd.py file. For now, we only support optimizing a linear or disjointly bilinear expressions at the leaf values and decision expressions.
As a concrete toy example, imagine the problem of inventory management. There is a Boolean variable `d` which denotes the level of demand (i.e., `d=True` if demand is high; otherwise `d=False`). Let's say the current inventory level of a product of interest is `x \in [-1000, 1000]`. Suppose we can place an order of amount `a \in [0, 500]` for this product. And we will have the following reward based on the current demand, inventory level, and the new order:
```
( [d]
( [x >= 150]
( [150 - 0.1 * a - 0.05 * x ] )
( [(x - 150) - 0.1 * a - 0.05 * x] )
)
( [x >= 50]
( [50 - 0.1 * a - 0.05 * x] )
( [(x - 50) - 0.1 * a - 0.05 * x] )
)
)
```
Though it is natural to consider multi-step decisions for this kind of problem, let's only focus on optimizing this reward for a single step, for the sake of simplicity and illustration.
So, given this reward, what we might be interested in is the maximum reward we can obtain, subject to the demand level and the current inventory level. That is, we want to compute `max_a reward(a, x, d)`.
```python
# Load the reward function as XADD
reward_dd = context.import_xadd('xaddpy/tests/ex/inventory.xadd')
# Update the bound information over variables of interest
a, x = core.Symbol('a'), core.Symbol('x')
context.update_bounds({a: (0, 500), x: (-1000, 1000)})
# Max out the order quantity
max_reward_d_x = context.min_or_max_var(reward_dd, a, is_min=False, annotate=True)
print(f"Maximize over a: \n{context.get_repr(max_reward_d_x)}")
```
```
Output:
Maximize over a:
( [d] (dec, id): 1, 82
( [-150 + x <= 0] (dec, id): 10002, 81
( [-150 + 0.95*x] ) node_id: 72 anno: 0
( [150 - 0.05*x] ) node_id: 58 anno: 0
)
( [-50 + x <= 0] (dec, id): 10003, 51
( [-50 + 0.95*x] ) node_id: 42 anno: 0
( [50 - 0.05*x] ) node_id: 29 anno: 0
)
)
```
To obtain this result, note that we should provide the bound information over the continuous variables. If not, then `(-oo, oo)` will be used as the bounds.
If we want to know which values of `a` will yield the optimal outcomes, we can apply the argmax operation. Specifically,
```python
argmax_a_id = context.reduced_arg_min_or_max(max_reward_d_x, a)
print(f"Argmax over a: \n{context.get_repr(argmax_a_id)}")
```
```
Output:
Argmax over a:
( [0] ) node_id: 0
```
Trivially in this case, not ordering any new products will maximize the one-step reward, which makes sense. A more interesting case would, of course, be when we have to make sequential decisions taking into account stochastic demands and the product level that changes according to the order amount and the demand. For this kind of problems, we suggest you take a look at [Symbolic Dynamic Programming (SDP)](https://github.com/ataitler/pyRDDLGym/blob/sdp-symengine/run_examples/run_vi.py).
Now, if we further optimize the `max_reward_d_x` over `x` variable, we get the following:
```python
# Max out the inventory level
max_reward_d = context.min_or_max_var(max_reward_d_x, x, is_min=False, annotate=True)
print(f"Maximize over x: \n{context.get_repr(max_reward_d)}")
# Get the argmax over x
argmax_x_id = context.reduced_arg_min_or_max(max_reward_d, x)
print(f"Argmax over x: \n{context.get_repr(argmax_x_id)}")
```
```
Output:
Maximize over x:
( [d] (dec, id): 1, 105
( [142.5] ) node_id: 102 anno: 99
( [47.5] ) node_id: 89 anno: 85
)
Argmax over x:
( [d] (dec, id): 1, 115
( [150] ) node_id: 99
( [50] ) node_id: 85
)
```
The results tells us that the maximum achievable reward is 142.5 when `d=True, x=150` or 47.5 when `d=False, x=50`.
4. Max (min) out Boolean variables with `XADD.min_or_max_var`
Eliminating Boolean variables with max or min operations can be easily done by using the previously discussed `min_or_max_var` method. You just need to pass the Boolean variable to the method.
#### Definite Integral
Given an XADD node and a symbolic variable, you can integrate out the variable from the node. See [test_def_int.py](xaddpy/tests/test_def_int.py) which provides examples of this operation.
## Citation
Please use the following bibtex for citations:
```
@InProceedings{pmlr-v162-jeong22a,
title = {An Exact Symbolic Reduction of Linear Smart {P}redict+{O}ptimize to Mixed Integer Linear Programming},
author = {Jeong, Jihwan and Jaggi, Parth and Butler, Andrew and Sanner, Scott},
booktitle = {Proceedings of the 39th International Conference on Machine Learning},
pages = {10053--10067},
year = {2022},
volume = {162},
series = {Proceedings of Machine Learning Research},
month = {17--23 Jul},
publisher = {PMLR},
}
```
Raw data
{
"_id": null,
"home_page": "https://github.com/jihwan-jeong/xaddpy",
"name": "xaddpy",
"maintainer": "",
"docs_url": null,
"requires_python": ">=3.8",
"maintainer_email": "",
"keywords": "xadd,xadd python,symbolic diagram",
"author": "Jihwan Jeong",
"author_email": "Jihwan Jeong <jiihwan.jeong@gmail.com>",
"download_url": "https://files.pythonhosted.org/packages/ea/46/aa21e21df0d4f13ee3bb60e21b0025ad3ae8d5a8657f6cc5f9ab8ed5330b/xaddpy-0.2.5.tar.gz",
"platform": null,
"description": "# Python Implementation of XADD\n\nThis repository implements the Python version of XADD (eXtended Algebraic Decision Diagrams) which was first introduced in [Sanner et al. (2011)](https://arxiv.org/pdf/1202.3762.pdf); you can find the original Java implementation from [here](https://github.com/ssanner/xadd-inference). \n\nOur Python XADD code uses [SymEngine](https://github.com/symengine/symengine.py) for symbolically maintaining all variables and related operations, and [PULP](https://github.com/coin-or/pulp) is used for pruning unreachable paths. Note that we only check linear conditionals. If you have Gurobi installed and configured in the conda environment, then PULP will use Gurobi for solving (MI)LPs; otherwise, the default solver ([CBC](https://github.com/coin-or/Cbc)) is going to be used. However, we do not actively support optimizers other than Gurobi for now.\n\nNote that the implementation for [EMSPO](https://proceedings.mlr.press/v162/jeong22a/jeong22a.pdf) --- Exact symbolic reduction of linear Smart Predict+Optimize to MILP (Jeong et al., ICML-22) --- has been moved to the branch [emspo](https://github.com/jihwan-jeong/xaddpy/tree/emspo).\n\nYou can find the implementation for the [CPAIOR-23](https://ssanner.github.io/papers/cpaior23_dblpsve.pdf) work --- A Mixed-Integer Linear Programming Reduction of Disjoint Bilinear Programs via Symbolic\nVariable Elimination --- in [examples/dblp](examples/dblp).\n\n## Installation\n\n**Load your Python virtual environment then type the following commands for package installation**\n\n```shell\npip install xaddpy\n\n# Optional: if you want to use Gurobi for the 'reduce_lp' method\n# that prunes out unreachable partitions using LP solvers\npip install gurobipy # If you have a license\n```\n\n## Installing pygraphviz for visualization\nWith `pygraphviz`, you can visualize a given XADD in a graph format, which can be very useful. Here, we explain how to install the package.\n\nTo begin with, you need to install the following:\n\n- graphviz\n- pygraphviz\n\nMake sure you have activated the right conda environment with `conda activate YOUR_CONDA_ENVIRONMENT`.\n\n### Step 1: Installing graphviz\n\n1. For Ubuntu/Debian users, run the following command.\n\n```shell\nsudo apt-get install graphviz graphviz-dev\n```\n\n2. For Fedora and Red Hat systems, you can do as follows.\n\n```shell\nsudo dnf install graphviz graphviz-devel\n```\n\n3. For Mac users, you can use `brew` to install `graphviz`.\n\n```shell\nbrew install graphviz\n```\n\nUnfortunately, we do not provide support for Windows systems, though you can refer to the [pygraphviz documentation](https://pygraphviz.github.io/documentation/stable/install.html) for information.\n\n### Step 2: Installing pygraphviz\n\n1. Linux systems\n\n```shell\npip install pygraphviz\n```\n\n2. MacOS\n\n```shell\npython -m pip install \\\n --global-option=build_ext \\\n --global-option=\"-I$(brew --prefix graphviz)/include/\" \\\n --global-option=\"-L$(brew --prefix graphviz)/lib/\" \\\n pygraphviz\n```\n\nNote that due to the default installation location by `brew`, you need to provide some additional options for `pip` installation.\n\n## Using xaddpy\n\nYou can find useful XADD usecases in the [xaddpy/tests/test_bool_var.py](xaddpy/tests/test_bool_var.py) and [xaddpy/tests/test_xadd.py](xaddpy/tests/test_xadd.py) files. Here, we will first briefly discuss different ways to build an initial XADD that you want to work with. \n\n### Loading from a file\n\nIf you know the entire structure of an initial XADD, then you can create a text file specifying the XADD and load it using the `XADD.import_xadd` method. It's important that, when you manually write down the XADD you have, you follow the same syntax rule as in the example file shown below.\n\nBelow is a part of the XADD written in [xaddpy/tests/ex/bool_cont_mixed.xadd](xaddpy/tests/ex/bool_cont_mixed.xadd):\n```\n...\n ( [x - y <= 0]\n ( [2 * x + y <= 0]\n ([x])\n ([y])\n )\n ( [b3]\n ([2 * x])\n ([2 * y])\n )\n )\n...\n```\nHere, `[x-y <= 0]` defines a decision expression; its true branch is another node with the decision `[2 * x + y <= 0]`, while the decision of the false branch is a Boolean variable `b3`. Similarly, if `[2 * x + y <= 0]` holds true, then we get the leaf value `[x]`; otherwise, we get `[y]`. _All expressions should be wrapped with brackets, including Boolean variables._ A SymEngine `Symbol` object will be created for each unique variable.\n\nTo load this XADD, you can do the following:\n```python\nfrom xaddpy import XADD\ncontext = XADD()\nfname = 'xaddpy/tests/ex/bool_cont_mixed.xadd'\n\norig_xadd = context.import_xadd(fname)\n```\nFollowing the Java implementation, we call the instantiated XADD object `context`. This object maintains and manages all existing/new nodes and decision expressions. For example, `context._id_to_node` is a Python dictionary that stores mappings from node IDs (`int`) to the corresponding `Node` objects. For more information, please refer to the [constructor of the `XADD` class](xaddpy/xadd/xadd.py#L57).\n\nTo check whether you've got the right XADD imported, you can print it out.\n```python\nprint(f\"Imported XADD: \\n{context.get_repr(orig_xadd)}\")\n```\nThe `XADD.get_repr` method will return `repr(node)` and the string representation of each XADD node is implemented in [xaddpy/xadd/node.py](xaddpy/xadd/node.py). Beware that the printing method can be slow for a large XADD.\n\n### Recursively building an XADD\nAnother way of creating an initial XADD node is by recursively building it with the `apply` method. A very simple example would be something like this:\n\n```python\nfrom xaddpy import XADD\nimport symengine.lib.symengine_wrapper as core\n\ncontext = XADD()\n\nx_id = context.convert_to_xadd(core.Symbol('x'))\ny_id = context.convert_to_xadd(core.Symbol('y'))\n\nsum_node_id = context.apply(x_id, y_id, op='add')\ncomp_node_id = context.apply(sum_node_id, y_id, op='min')\n\nprint(f\"Sum node:\\n{context.get_repr(sum_node_id)}\\n\")\nprint(f\"Comparison node:\\n{context.get_repr(comp_node_id)}\")\n```\nYou can check that the print output shows\n```\nSum node:\n( [x + y] ) node_id: 9\n\nComparison node:\n( [x <= 0] (dec, id): 10001, 10\n ( [x + y] ) node_id: 9 \n ( [y] ) node_id: 8 \n)\n```\nwhich is the expected outcome!\n\nCheck out a much more comprehensive example demonstrating the recursive construction of a nontrivial XADD from here: [pyRDDLGym/XADD/RDDLModelXADD.py](https://github.com/ataitler/pyRDDLGym/blob/01955ee7bca2861124709c116f419f2927c04a89/pyRDDLGym/XADD/RDDLModelXADD.py#L124).\n\n### Directly creating an XADD node\nFinally, you might want to build a constant node, an arbitrary decision expression, and a Boolean decision directly. To this end, let's consider building the following XADD: \n\n```\n([b]\n ([1])\n ([x + y <= 0]\n ([0])\n ([2])\n )\n)\n```\n\nTo do this, we will first create an internal node whose decision is `[x + y <= 0]`, the low and the high branches are `[0]` and `[2]` (respectively). Using `SymEngine`'s `S` function (or you can use `sympify`), you can turn an algebraic expression involving variables and numerics into a symbolic expression. Given this decision expression, you can get its unique index using `XADD.get_dec_expr_index` method. You can use the decision ID along with the ID of the low and high nodes connected to the decision to create the corresponding decision node, using `XADD.get_internal_node`.\n\n```python\nimport symengine.lib.symengine_wrapper as core\nfrom xaddpy import XADD\n\ncontext = XADD()\n\n# Get the unique ID of the decision expression\ndec_expr: core.Basic = core.S('x + y <= 0')\ndec_id, is_reversed = context.get_dec_expr_index(dec_expr, create=True)\n\n# Get the IDs of the high and low branches: [0] and [2], respectively\nhigh: int = context.get_leaf_node(core.S(0))\nlow: int = context.get_leaf_node(core.S(2))\nif is_reversed:\n low, high = high, low\n\n# Create the decision node with the IDs\ndec_node_id: int = context.get_internal_node(dec_id, low=low, high=high)\nprint(f\"Node created:\\n{context.get_repr(dec_node_id)}\")\n```\n\nNote that `XADD.get_dec_expr_index` returns a boolean variable `is_reversed` which is `False` if the canonical decision expression of the given decision has the same inequality direction. If the direction has changed, then `is_reversed=True`; in this case, low and high branches should be swapped.\n\nAnother way of creating this node is to use the `XADD.get_dec_node` method. This method can only be used when the low and high nodes are terminal nodes containing leaf expressions.\n\n```python\ndec_node_id = context.get_dec_node(dec_expr, low_val=core.S(2), high_val=core.S(0))\n```\n\nNote also that you need to wrap constants with the `core.S` function to turn them into `core.Basic` objects.\n\nNow, it remains to create a decision node with the Boolean variable `b` and connect it to its low and high branches. \n\n```python\nfrom xaddpy.utils.symengine import BooleanVar\n\nb = BooleanVar(core.Symbol('b'))\ndec_b_id, _ = context.get_dec_expr_index(b, create=True)\n```\n\nFirst of all, you need to import and instantiate a `BooleanVar` object for a Boolean variable. Otherwise, the variable won't be recognized as a Boolean variable in XADD operations!\n\nOnce you have the decision ID, we can finally link this decision node with the node created earlier. \n\n```python\nhigh: int = context.get_leaf_node(core.S(1))\nnode_id: int = context.get_internal_node(dec_b_id, low=dec_node_id, high=high)\nprint(f\"Node created:\\n{context.get_repr(node_id)}\")\n```\nAnd we get the following print outputs.\n```\nOutput:\nNode created:\n( [b] (dec, id): 2, 9\n ( [1] ) node_id: 1 \n ( [x + y <= 0] (dec, id): 10001, 8\n ( [0] ) node_id: 0 \n ( [2] ) node_id: 7 \n ) \n) \n```\n\n### XADD Operations\n\n#### XADD.apply(id1: int, id2: int, op: str)\nYou can perform the `apply` operation to two XADD nodes with IDs `id1` and `id2`. Below is the list of the supported operators (`op`):\n\n**Non-Boolean operations**\n- 'max', 'min'\n- 'add', 'subtract'\n- 'prod', 'div'\n\n**Boolean operations**\n- 'and'\n- 'or'\n\n**Relational operations**\n- '!=', '=='\n- '>', '>='\n- '<', '<='\n\n#### XADD.unary_op(node_id: int, op: str) (unary operations)\nYou can also apply the following unary operators to a single XADD node recursively (also check `UNARY_OP` in [xaddpy/utils/global_vars.py](xaddpy/utils/global_vars.py)). In this case, an operator will be applied to each and every leaf value of a given node. Hence, the decision expressions will remain unchanged.\n\n- 'sin, 'cos', 'tan'\n- 'sinh', 'cosh', 'tanh'\n- 'exp', 'log', 'log2', 'log10', 'log1p'\n- 'floor', 'ceil'\n- 'sqrt', 'pow'\n- '-', '+'\n- 'sgn' (sign function... sgn(x) = 1 if x > 0; 0 if x == 0; -1 otherwise)\n- 'abs'\n- 'float', 'int'\n- '~' (negation)\n\nThe `pow` operation requires an additional argument specifying the exponent.\n\n#### XADD.evaluate(node_id: int, bool_assign: dict, cont_assign: bool, primitive_type: bool)\nWhen you want to assign concrete values to Boolean and continuous variables, you can use this method. An example is provided in the `test_mixed_eval` function defined in [xaddpy/tests/test_bool_var.py](xaddpy/tests/test_bool_var.py).\n\nAs another example, let's say we want to evaluate the XADD node defined a few lines above.\n```python\nx, y = core.symbols('x y')\n\nbool_assign = {b: True}\ncont_assign = {x: 2, y: -1}\n\nres = context.evaluate(node_id, bool_assign=bool_assign, cont_assign=cont_assign)\nprint(f\"Result: {res}\")\n```\n\nIn this case, `b=True` will directly leads to the leaf value of `1` regardless of the assignment given to `x` and `y` variables. \n\n```python\nbool_assign = {b: False}\nres = context.evaluate(node_id, bool_assign=bool_assign, cont_assign=cont_assign)\nprint(f\"Result: {res}\")\n```\n\nIf we change the value of `b`, we can see that we get `2`. Note that you have to make sure that all symbolic variables get assigned specific values; otherwise, the function will return `None`. \n\n#### XADD.substitute(node_id: int, subst_dict: dict)\nIf instead you want to assign values to a subset of symbolic variables while leaving the other variables as-is, you can use the `substitute` method. Similar to `evaluate`, you need to pass in a dictionary mapping SymEngine `Symbol`s to their concrete values.\n\nFor example,\n\n```python\nsubst_dict = {x: 1}\nnode_id_after_subs = context.substitute(node_id, subst_dict)\nprint(f\"Result:\\n{context.get_repr(node_id_after_subs)}\")\n```\nwhich outputs\n```\nResult:\n( [b] (dec, id): 2, 16\n ( [1] ) node_id: 1 \n ( [y + 1 <= 0] (dec, id): 10003, 12\n ( [0] ) node_id: 0 \n ( [2] ) node_id: 7 \n ) \n) \n```\nas expected.\n\n#### XADD.collect_vars(node_id: int)\nIf you want to extract all Boolean and continuous symbols existing in an XADD node, you can use this method.\n\n```python\nvar_set = context.collect_vars(node_id)\nprint(f\"var_set: {var_set}\")\n```\n```\nOutput:\nvar_set: {y, b, x}\n```\n\nThis method can be useful to figure out which variables need to have values assigned in order to evaluate a given XADD node.\n\n#### XADD.make_canonical(node_id: int)\nThis method gives a canonical order to an XADD that is potentially unordered. Note that the `apply` method already calls `make_canonical` when the `op` is one of `('min', 'max', '!=', '==', '>', '>=', '<', '<=', 'or', 'and')`.\n\n\n#### Variable Elimination\n\n1. Sum out: `XADD.op_out(node_id: int, dec_id: int, op: str = 'add')`\n\nLet's say we have a joint probability distribution function over Boolean variables `b1, b2`, i.e., `P(b1, b2)` as in the following example. `P(b1, b2)=`\n\n```\n( [b1]\n ( [b2] \n ( [0.25] )\n ( [0.3] )\n )\n ( [b2]\n ( [0.1] )\n ( [0.35] )\n )\n)\n```\nNotice that the values are non-negative and sum up to one, making this a valid probability distribution. Now, one may be interested in marginalizing out a variable `b2` to get `P(b1) = \\sum_{b2} P(b1, b2)`. This can be done in XADD by using the `op_out` method.\n\nLet's directly dive into an example:\n\n```python\n# Load the joint probability as XADD\np_b1b2 = context.import_xadd('xaddpy/tests/ex/bool_prob.xadd')\n\n# Get the decision index of `b2`\nb2 = BooleanVar(core.Symbol('b2'))\nb2_dec_id, _ = context.get_dec_expr_index(b2, create=False)\n\n# Marginalize out `b2`\np_b1 = context.op_out(node_id=p_b1b2, dec_id=b2_dec_id, op='add')\nprint(f\"P(b1): \\n{context.get_repr(p_b1)}\")\n```\n```\nOutput: \nP(b1): \n( [b1] (dec, id): 1, 26\n ( [0.55] ) node_id: 25 \n ( [0.45] ) node_id: 24 \n)\n```\n\nAs expected, the obtained `P(b1)` is a function of only `b1` variable, and the probabilities sum up to `1`.\n\n\n2. Prod out\n\nSimilarly, if we specify `op='prod'`, we can 'prod out' a Boolean variable from a given XADD.\n\n3. Max out (or min out) continuous variables: `XADD.min_or_max_var(node_id: int, var: VAR_TYPE, is_min: bool)`\n\nOne of the most interesting and useful applications of symbolic variable elimination is 'maxing out' or 'minning out' **continuous** variable(s) from a symbolic function. See [Jeong et al. (2023)](https://ssanner.github.io/papers/cpaior23_dblpsve.pdf) and [Jeong et al. (2022)](https://proceedings.mlr.press/v162/jeong22a/jeong22a.pdf) for more detailed discussions. Look up the `min_or_max_var` method in the xadd.py file. For now, we only support optimizing a linear or disjointly bilinear expressions at the leaf values and decision expressions.\n\nAs a concrete toy example, imagine the problem of inventory management. There is a Boolean variable `d` which denotes the level of demand (i.e., `d=True` if demand is high; otherwise `d=False`). Let's say the current inventory level of a product of interest is `x \\in [-1000, 1000]`. Suppose we can place an order of amount `a \\in [0, 500]` for this product. And we will have the following reward based on the current demand, inventory level, and the new order:\n```\n( [d]\n ( [x >= 150]\n ( [150 - 0.1 * a - 0.05 * x ] )\n ( [(x - 150) - 0.1 * a - 0.05 * x] )\n )\n ( [x >= 50]\n ( [50 - 0.1 * a - 0.05 * x] )\n ( [(x - 50) - 0.1 * a - 0.05 * x] )\n )\n)\n```\nThough it is natural to consider multi-step decisions for this kind of problem, let's only focus on optimizing this reward for a single step, for the sake of simplicity and illustration.\n\nSo, given this reward, what we might be interested in is the maximum reward we can obtain, subject to the demand level and the current inventory level. That is, we want to compute `max_a reward(a, x, d)`.\n\n```python\n# Load the reward function as XADD\nreward_dd = context.import_xadd('xaddpy/tests/ex/inventory.xadd')\n\n# Update the bound information over variables of interest\na, x = core.Symbol('a'), core.Symbol('x')\ncontext.update_bounds({a: (0, 500), x: (-1000, 1000)}) \n\n# Max out the order quantity\nmax_reward_d_x = context.min_or_max_var(reward_dd, a, is_min=False, annotate=True)\nprint(f\"Maximize over a: \\n{context.get_repr(max_reward_d_x)}\")\n```\n```\nOutput:\nMaximize over a: \n( [d] (dec, id): 1, 82\n ( [-150 + x <= 0] (dec, id): 10002, 81\n ( [-150 + 0.95*x] ) node_id: 72 anno: 0 \n ( [150 - 0.05*x] ) node_id: 58 anno: 0 \n ) \n ( [-50 + x <= 0] (dec, id): 10003, 51\n ( [-50 + 0.95*x] ) node_id: 42 anno: 0 \n ( [50 - 0.05*x] ) node_id: 29 anno: 0 \n ) \n)\n```\nTo obtain this result, note that we should provide the bound information over the continuous variables. If not, then `(-oo, oo)` will be used as the bounds.\n\nIf we want to know which values of `a` will yield the optimal outcomes, we can apply the argmax operation. Specifically,\n\n```python\nargmax_a_id = context.reduced_arg_min_or_max(max_reward_d_x, a)\nprint(f\"Argmax over a: \\n{context.get_repr(argmax_a_id)}\")\n```\n```\nOutput:\nArgmax over a: \n( [0] ) node_id: 0\n```\nTrivially in this case, not ordering any new products will maximize the one-step reward, which makes sense. A more interesting case would, of course, be when we have to make sequential decisions taking into account stochastic demands and the product level that changes according to the order amount and the demand. For this kind of problems, we suggest you take a look at [Symbolic Dynamic Programming (SDP)](https://github.com/ataitler/pyRDDLGym/blob/sdp-symengine/run_examples/run_vi.py).\n\nNow, if we further optimize the `max_reward_d_x` over `x` variable, we get the following:\n```python\n# Max out the inventory level\nmax_reward_d = context.min_or_max_var(max_reward_d_x, x, is_min=False, annotate=True)\nprint(f\"Maximize over x: \\n{context.get_repr(max_reward_d)}\")\n\n# Get the argmax over x\nargmax_x_id = context.reduced_arg_min_or_max(max_reward_d, x)\nprint(f\"Argmax over x: \\n{context.get_repr(argmax_x_id)}\")\n```\n\n```\nOutput:\nMaximize over x: \n( [d] (dec, id): 1, 105\n ( [142.5] ) node_id: 102 anno: 99 \n ( [47.5] ) node_id: 89 anno: 85 \n)\nArgmax over x: \n( [d] (dec, id): 1, 115\n ( [150] ) node_id: 99 \n ( [50] ) node_id: 85 \n)\n```\nThe results tells us that the maximum achievable reward is 142.5 when `d=True, x=150` or 47.5 when `d=False, x=50`.\n\n4. Max (min) out Boolean variables with `XADD.min_or_max_var`\n\nEliminating Boolean variables with max or min operations can be easily done by using the previously discussed `min_or_max_var` method. You just need to pass the Boolean variable to the method.\n\n#### Definite Integral\n\nGiven an XADD node and a symbolic variable, you can integrate out the variable from the node. See [test_def_int.py](xaddpy/tests/test_def_int.py) which provides examples of this operation.\n\n## Citation\n\nPlease use the following bibtex for citations:\n\n```\n@InProceedings{pmlr-v162-jeong22a,\n title = \t {An Exact Symbolic Reduction of Linear Smart {P}redict+{O}ptimize to Mixed Integer Linear Programming},\n author = {Jeong, Jihwan and Jaggi, Parth and Butler, Andrew and Sanner, Scott},\n booktitle = \t {Proceedings of the 39th International Conference on Machine Learning},\n pages = \t {10053--10067},\n year = \t {2022},\n volume = \t {162},\n series = \t {Proceedings of Machine Learning Research},\n month = \t {17--23 Jul},\n publisher = {PMLR},\n}\n```\n",
"bugtrack_url": null,
"license": "MIT License Copyright (c) 2022 jihwan-jeong Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the \"Software\"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED \"AS IS\", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. ",
"summary": "XADD package in Python",
"version": "0.2.5",
"project_urls": {
"Bug Tracker": "https://github.com/jihwan-jeong/xaddpy/issues",
"Download": "https://github.com/jihwan-jeong/xaddpy/archive/refs/tags/0.2.5.tar.gz",
"Homepage": "https://github.com/jihwan-jeong/xaddpy"
},
"split_keywords": [
"xadd",
"xadd python",
"symbolic diagram"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "e385d83f85b24919e2b21beee4d8efc396709baa07b5db786a87ebbcd024f71b",
"md5": "626e9ff625973bbcf9fe0e44b7148284",
"sha256": "6fffa0d50eb3c3bf86805d92ff294b17efdc8b6a30ebe485ea2cb2c9249d023a"
},
"downloads": -1,
"filename": "xaddpy-0.2.5-py3-none-any.whl",
"has_sig": false,
"md5_digest": "626e9ff625973bbcf9fe0e44b7148284",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.8",
"size": 57576,
"upload_time": "2024-02-08T16:24:33",
"upload_time_iso_8601": "2024-02-08T16:24:33.587194Z",
"url": "https://files.pythonhosted.org/packages/e3/85/d83f85b24919e2b21beee4d8efc396709baa07b5db786a87ebbcd024f71b/xaddpy-0.2.5-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "ea46aa21e21df0d4f13ee3bb60e21b0025ad3ae8d5a8657f6cc5f9ab8ed5330b",
"md5": "1a7a54f6b76ed1041fbaff5ac42ef6c4",
"sha256": "2a15f082ac8cf4487c96c58e5fca50521468f573ed00997a29340c3e8896ce3a"
},
"downloads": -1,
"filename": "xaddpy-0.2.5.tar.gz",
"has_sig": false,
"md5_digest": "1a7a54f6b76ed1041fbaff5ac42ef6c4",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.8",
"size": 60427,
"upload_time": "2024-02-08T16:24:36",
"upload_time_iso_8601": "2024-02-08T16:24:36.245221Z",
"url": "https://files.pythonhosted.org/packages/ea/46/aa21e21df0d4f13ee3bb60e21b0025ad3ae8d5a8657f6cc5f9ab8ed5330b/xaddpy-0.2.5.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-02-08 16:24:36",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "jihwan-jeong",
"github_project": "xaddpy",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"lcname": "xaddpy"
}
