Replies: 3 comments 2 replies
-
|
Would you like to post the PyOptInterface implementation as a comparison? By the way, PyOptInterface uses the C API of HiGHS instead of highspy and the names are passed to HiGHS in |
Beta Was this translation helpful? Give feedback.
-
@metab0t Here's the PyOptInterface model constructor. def create_ip_baseline_model(model: Model, **kwargs) -> tuple[Model, dict]:
"""Node Weighted Steiner Forest problem.
- optimal solution baseline reference
- reverse cumulative multi-commodity iteger flow
Requires solution extractor for binary 'x_var' variables.
"""
import time
start_time = time.time()
logger.info("Creating IP Baseline model...")
G = kwargs.get("graph", None)
if not isinstance(G, rx.PyDiGraph):
raise TypeError("'graph' must be a rustworkx.PyDiGraph! Call '.to_directed' on a PyGraph if needed.")
terminal_sets = G.attrs.get("terminal_sets", {})
if not terminal_sets:
raise LookupError("Graph must have 'terminal_sets' attribute in attrs member!")
# Variables
# Node selection for each node in graph to determine if node is in forest.
x = {}
# Edge selection y^k_{ij} for each k in [K] and each {i,j}
y_k = {}
# Flow on edges f^k_{ij} for each k in [K] and each {i,j} (flow for root k on arc from i to j)
f_k = {}
for i in G.node_indices():
x[(i)] = model.add_variable(lb=0, ub=1, domain=poi.VariableDomain.Binary)
for k, terminal_set in terminal_sets.items():
f_ub = len(terminal_set)
for i, j in G.edge_list():
y_k[(k, i, j)] = model.add_variable(lb=0, ub=1, domain=poi.VariableDomain.Binary)
f_k[(k, i, j)] = model.add_variable(lb=0, ub=f_ub, domain=poi.VariableDomain.Integer)
# Objective: Minimize total node cost
model.set_objective(
poi.quicksum(G[i]["need_exploration_point"] * x[i] for i in G.node_indices()),
sense=poi.ObjectiveSense.Minimize,
)
# Constraints
# Node/flow based constraints
for i in G.node_indices():
predecessors = G.predecessor_indices(i)
successors = G.successor_indices(i)
for k, terminal_set in terminal_sets.items():
in_flow = poi.quicksum(f_k[k, j, i] for j in predecessors)
out_flow = poi.quicksum(f_k[k, i, j] for j in successors)
# Node selection
model.add_linear_constraint(in_flow <= len(terminal_set) * x[i])
model.add_linear_constraint(out_flow <= len(terminal_set) * x[i])
# Edge selection
for j in predecessors:
model.add_linear_constraint(f_k[(k, j, i)] <= len(terminal_set) * y_k[(k, j, i)])
for j in successors:
model.add_linear_constraint(f_k[(k, i, j)] <= len(terminal_set) * y_k[(k, i, j)])
# Flow
if i == k:
# Flow at root
model.add_linear_constraint(out_flow == 0)
model.add_linear_constraint(in_flow == len(terminal_set))
elif i in terminal_set:
# Flow at terminal
model.add_linear_constraint(out_flow - in_flow == 1)
# Maximum of a single outgoing arc
model.add_linear_constraint(poi.quicksum(y_k[(k, i, j)] for j in successors) <= 1)
else:
# Flow at intermediate node
model.add_linear_constraint(out_flow - in_flow == 0)
# Maximum of a single outgoing arc
model.add_linear_constraint(poi.quicksum(y_k[(k, i, j)] for j in successors) <= 1)
# No back and forth flow to same neighbor for root k
for j in predecessors:
if (k, j, i) in y_k and (k, i, j) in y_k:
model.add_linear_constraint(y_k[(k, i, j)] + y_k[(k, j, i)] <= 1)
end_time = time.time()
logger.warning(f" time to create model: {end_time - start_time} seconds")
vars = {"x": x, "y": y_k, "f": f_k}
return model, vars
```
I didn't add the variables in bulk in this model and I don't recall why not; if memory serves it was because I have a few other variants of the model (like with both node and edges weights) and iterating allows for a bit better debugging. |
Beta Was this translation helpful? Give feedback.
-
|
Your implementation is neat and easy to follow. Performance is the top priority of PyOptInterface to avoid unnecessary overhead compared with calling the C API directly. |
Beta Was this translation helpful? Give feedback.
-
|
Thanks for posting this study. I'm not surprised that something based on the C API rather than pybind11 is faster, and I can see that the difference is meaningful on MIPs that are so simple to solve. We've seen a similar situation when building problems with Pyomo: the time taken to communicate the problem to HiGHS is dominant (because it's done in Python, rather than via a data file) when the problem is easy to solve. However, the absolute times are small compared to the solve time for a non-trivial MIP, and the relative time difference is only a factor of 4-5. To re-write the HiGHS Python API so that it calls the C API rather than use pybind11 to achieve the efficiency of PyOptInterface isn't a worthwhile use of HiGHS team resources. Of course, if someone externally wants to contribute it, then let us know! |
Beta Was this translation helpful? Give feedback.
-
Agreed, whole heartedly! Having the HiGHSpy interface be on par with the other Python interfaces (Pulp, Pyomo, PyOptInterface, etc...) is great as-is. It was a joy to essentially only need to change the function names instead of the whole frame of thought for building and extracting. 👍 With the growth of automatic bind gen packages I wouldn't be surprised if it could be automated. Then, in those cases where construction speed is the priority there's always directly interfacing from a compiled language. :) |
Beta Was this translation helpful? Give feedback.
Uh oh!
There was an error while loading. Please reload this page.
-
I don't know if this is a 'discussion' or just a 'report' but here it is.
The short of it:
I hadn't tried HiGHSpy in a while and spotted some nice quality of life changes in the interface that made it virtually 1:1 with PyOptInterface and other front-ends so I gave it a shot...
I tried doing the model creation using the bulk addBinaries, addIntegers instead of iterating and it did not improve the situation presented below. I also tried directly using addVariable for each using Inter var types with lb and ub, no love from that either.
HiGHSpy v1.11.0
PyOptinterface using HiGHSpy v1.10.0
The long of it:
Here's the iterative variable addition version which matches the exact logic of the PyOptInterface version except the PyOptInterface version does include the variable names which, iirc, PyOptInterface handles instead of sending to HiGHS:
and just for completeness to show the model equivalency:
HiGHSpy v1.11.0
PyOptInterface
Beta Was this translation helpful? Give feedback.
All reactions