GCSOPT

GCSOPT is a Python library for solving optimization problems over Graphs of Convex Sets (GCS). It provides a high-level interface for modeling GCS problems and automatically reformulates them as mixed-integer programs that can be solved with state-of-the-art optimization solvers.

For a detailed description of the algorithms implemented in this library see the paper A Unified and Scalable Method for Optimization over Graphs of Convex Sets.

Main features

• Uses the intuitive syntax of CVXPY to describe convex sets and functions.
• Simple interface for constructing graphs of convex sets.
• Seamless integration with state-of-the-art solvers via CVXPY.

Installation

You can install the latest release from PyPI:

pip install gcsopt

To install from source:

git clone https://github.com/TobiaMarcucci/gcsopt.git
cd gcsopt
pip install .

Mixed-integer solvers

GCSOPT reformulates a GCS problem as a mixed-integer program and solves it using one of the solvers available in CVXPY.

If the problem is a mixed-integer linear program, it can be solved with the open-source solvers that come with CVXPY. For other classes of mixed-integer programs, or for better performance, you can install the solvers Gurobi or MOSEK, which are free for academic use.

Installation of Gurobi

• Get a Gurobi license here or here for academic use.
• Install the Python package gurobipy using your favorite installation method as described here.
• Verify that CVXPY detects Gurobi by running:

import cvxpy
assert "GUROBI" in cvxpy.installed_solvers()

Installation of MOSEK

• Get a MOSEK license here or here for academic use.
• Install the Python package mosek using your favorite installation method as described here.
• Verify that CVXPY detects MOSEK by running:

import cvxpy
assert "MOSEK" in cvxpy.installed_solvers()

Example

Below is a minimal example of how to use GCSOPT for solving a shortest-path problem in GCS.

import cvxpy as cp
from gcsopt import GraphOfConvexSets

# Initialize directed graph.
directed = True
G = GraphOfConvexSets(directed)

# Add vertices to graph.
l = 3 # Side length of vertex grid.
r = .3 # Radius of vertex circles.
for i in range(l):
    for j in range(l):
        c = (i, j) # Center of the circle.
        v = G.add_vertex(c) # Vertex named after its center.
        x = v.add_variable(2) # Continuous variable.
        v.add_constraint(cp.norm2(x - c) <= r) # Constrain in circle.

# Add edges to graph.
for i in range(l):
    for j in range(l):
        cv = (i, j) # Name of vertex v.
        v = G.get_vertex(cv) # Retrieve vertex using its name.
        xv = v.variables[0] # Get first and only variable paired with vertex.

        # Add right and upward neighbors if not at grid boundary.
        neighbors = [(i + 1, j), (i, j + 1)] # Names of candidate neighbors.
        for cw in neighbors:
            if G.has_vertex(cw): # False if at grid boundary.
                w = G.get_vertex(cw) # Get neighbor vertex from its name.
                xw = w.variables[0] # Get neighbor variable.
                e = G.add_edge(v, w) # Connect vertices with edge.
                e.add_cost(cp.norm2(xw - xv)) # Add L2 cost to edge.

# Solve shortest-path problem.
s = G.get_vertex((0, 0)) # Source vertex.
t = G.get_vertex((l - 1, l - 1)) # Target vertex.
G.solve_shortest_path(s, t) # Solve problem and populate graph with result.

# Print solution statistics.
print("Problem status:", G.status)
print("Problem optimal value:", G.value)
for v in G.vertices:
    x = v.variables[0]
    print(f"Variable {v.name} optimal value:", x.value)

The output of this script is the following.

Problem status: optimal
Optimal value: 2.4561622509772887
Variable (0, 0) optimal value: [0.28768714 0.08506533]
Variable (0, 1) optimal value: None
Variable (0, 2) optimal value: None
Variable (1, 0) optimal value: [0.82565028 0.24413557]
Variable (1, 1) optimal value: [1.21213203 0.78786797]
Variable (1, 2) optimal value: None
Variable (2, 0) optimal value: None
Variable (2, 1) optimal value: [1.75586443 1.17434971]
Variable (2, 2) optimal value: [1.91493467 1.71231286]

The next script plots the problem optimal solution.

import matplotlib.pyplot as plt
plt.figure() # Initialize empty figure.
G.plot_2d() # Plot graph of convex sets.
G.plot_2d_solution() # Plot optimal subgraph.
plt.show() # Show figure.

Note

This example results in a mixed-integer second-order cone program, which requires a suitable solver (e.g., Gurobi or MOSEK). If such a solver is not available, replace any appearance of cp.norm2 with cp.norm1 or cp.norm_inf to obtain a mixed-integer linear program compatible with the open-source solvers that come with CVXPY.

Contributing

Contributions, bug reports, and feature requests are very welcome. To contribute, please open an issue or submit a pull request on GitHub.

Citation

If you use GCSOPT in your research, please consider citing the following paper.

@article{marcucci2025unified,
  title={A Unified and Scalable Method for Optimization over Graphs of Convex Sets},
  author={Marcucci, Tobia},
  journal={arXiv preprint arXiv:2510.20184},
  year={2025}
}

License

This project is licensed under the MIT License.

Author

Developed and maintained by Tobia Marcucci. For questions or feedback, please contact marcucci@ucsb.edu.