# Integrating Aggregated Electric Vehicle Flexibilities in Unit Commitment Models using Submodular Optimization

Hélène Arvis, Olivier Beaude, Nicolas Gast, Stéphane Gaubert, Bruno Gaujal

► To cite this version:

Hélène Arvis, Olivier Beaude, Nicolas Gast, Stéphane Gaubert, Bruno Gaujal. Integrating Aggregated Electric Vehicle Flexibilities in Unit Commitment Models using Submodular Optimization. 2025. hal-05399441

HAL Id: hal-05399441

https://inria.hal.science/hal-05399441v1

Preprint submitted on 4 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Integrating Aggregated Electric Vehicle Flexibilities in Unit Commitment Models using Submodular Optimization

Hélène Arvis<fnref n="1" />,<fnref n="2" />,<fnref n="3" />, Olivier Beaude<fnref n="1" />, Nicolas Gast<fnref n="2" />, Stéphane Gaubert<fnref n="3" /> and Bruno Gaujal<fnref n="2" />

**Abstract**— The Unit Commitment (UC) problem consists in controlling a large fleet of heterogeneous electricity production units in order to minimize the total production cost while satisfying consumer demand. Electric Vehicles (EVs) are used as a source of flexibility and are often aggregated for problem tractability. We develop a new approach to integrate EV flexibilities in the UC problem and exploit the generalized polymatroid structure of aggregated flexibilities of a large population of users to develop an exact optimization algorithm, combining a cutting-plane approach and submodular optimization. We show in particular that the UC can be solved exactly in a time which scales linearly, up to a logarithmic factor, in the number of EV users when each production unit is subject to convex constraints. We illustrate our approach by solving a real instance of a long-term UC problem, combining open-source data of the European grid (European Resource Adequacy Assessment project) and data originating from a survey of user behavior of the French EV fleet.

## I. INTRODUCTION

### A. Context

As the installed capacity for renewable energy sources increases around the world, so does the need for flexibility of the electric power system to absorb their fluctuations. In particular, these flexibilities, including hydropower or Electric Vehicles (EVs), must be correctly modeled in long-term optimization problems to evaluate their contribution to the system. Unit Commitment (UC) problems are a focus of study in this context and consist in dispatching electricity to balance demand and production while respecting the constraints of large number of heterogeneous productions units, generally including nuclear power plants (subject to specific dynamic constraints), thermal plants, hydroelectric plants, and other renewable energy sources.

The UC problem has been studied since the 1940s and progressively enriched by resolution techniques, as well as by the appearance of new production means, as demonstrated by the literature review of Abdou and Tkiouat [1]. We focus on the deterministic version of the UC, though it can also be studied in the context of uncertainties [2].

Typically, the UC is a very large Mixed-Integer Linear Program (MILP), modeling dispatch decisions over hundreds of time steps with thousands of power plants in a country. A common approach to solving these problems is through

aggregation, i.e., replacing a group of similar units by a class representative in order to reduce problem size and compute solutions in reasonable time. The clustering of similar units has been explored by Meus et al. [3], who demonstrate the benefits of aggregation in terms of tractability. However, aggregation generally leads to approximate solutions.

In this paper, we consider the specific case of EV charging profiles, in particular the dispatch of power through smart charging by a centralized operator. The correct integration of EVs in long-term, thus high-level, UC problems has an impact on realism of solutions. In France in 2035, there will be an estimated 15.6 million light-duty EVs [4]; if all vehicles charge simultaneously at 6kW, this amounts to a national demand of 93.6 GW. In comparison, the French installed production capacity is estimated to reach around 210GW (with 90GW of controllable means) in 2035 [5], thus would be heavily impacted by uncoordinated charging. Hence, our goal is to integrate an accurate and tractable model of EV flexibilities in global UC formulations.

Aggregating a large number of flexibilities boils down to computing, or approximating, the Minkowski sum of a large number of polytopes, where each summand represents the flexibility set of an individual user or group of similar users. This Minkowski sum generally has exponentially many inequalities; moreover, calculating the Minkowski sum of a family of polytopes defined by their facets is generally NP-hard [6]. Therefore, techniques must be explored to avoid an explicit computation of this Minkowski sum. The traditional, “direct”, aggregation method consists in summing the characteristics of individual users so as to have a “super-user” that represents the whole population. This generally leads to an aggregation error. Special cases in which an exact and tractable aggregation is possible have been identified, by Beaude et al. [7] where each local constraint set has the structure of a (bipartite) network flow polytope, and recently by Mukhi et al. [8], where each local constraint set is shown to have a generalized polymatroid structure.

### B. Contribution

We study a general UC model, including both power production units and a detailed model of EV flexibilities. This model captures charging constraint sets over a one week horizon, with multiple charging slots and specific energy consumption constraints (arising for instance from daily commuting). We leverage the generalized-polymatroid structure of the EV-component of the UC problem to develop an exact algorithm, combining a cutting-plane approach with submodular optimization. We show in particular that, when

<footnote>*This work was supported by the Défi Inria-EDF</footnote>

<footnote n="1">¹EDF Lab Paris-Saclay, OSIRIS department, {Firstname.Name}@edf.fr</footnote>

<footnote n="2">²Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, {Firstname.Name}@inria.fr</footnote>

<footnote n="3">³Inria, and CMAP, École polytechnique, IP Paris, CNRS, {Firstname.Name}@inria.fr</footnote>
the constraint sets of the power plants are convex, the UC problem can be solved to optimality in a time which scales as $N \log N$, where N is the number of EV user profiles (see Corollary 6). We also present a practical cutting-plane algorithm (Algorithm 1) and demonstrate its efficiency on a realistic case study, solving a long-term UC problem with European grid data (European Resource Adequacy Assessment project [9]) and EV data taken from a survey of French driver behavior [10]. In particular, the algorithm scales well relative to the number of iterations and computed cutting planes.

### C. Related work

The specific case of EV aggregation has already been studied, though not always in the context of a large UC problem. A local use case is the resource allocation problem in which an aggregator must optimize a global cost under given EV constraints and a global power bound. Müller et al. [11] offered an alternative to direct aggregation with an inner approximation of the Minkowski sum relying on zonotopes, themselves stable by Minkowski sum. Jacquot et al. [12], [7] studied a similar EV resource allocation problem with the additional constraint of preserving the privacy of individuals. To do so, they developed an exact aggregation method exploiting the combinatorial properties of the model (Hoffman cuts for bipartite network flows).

More recently, the aggregated power allocation problem in the context of smart charging (no Vehicle-to-Grid (V2G)) was found to have the structure of a generalized permutahedron by Mukhi and Abate [13], ensuring an exact aggregation of EV constraint sets. Panda and Tindemans [14] derived a different approach on a more restrictive use case of homogeneous charging slots based on a concept of UL-flexibility elaborated by the authors. This notion exploits the permutability of charging patterns to allow for stability by Minkowski sum, thus giving an efficient and scalable approximation.

Mukhi et al. [8] observed that EV flexibility sets have the structure of generalized polymatroids, a fundamental class of polyhedra studied extensively by Frank and Tardos [15]. They are also special cases of the polyhedra associated to unimodular systems, studied in the broader setting of discrete convexity by Danilov and Koshevoy [16]. Mukhi et al. developed an exact desaggregation method based on generalized polymatroid properties. Independently (before the appearance of [8]) Koshevoy pointed out to us [17] that polyhedra associated to the discrete convexity theory of the root system $A_n$, i.e., generalized polymatroids, can be used to describe EV constraint sets, leading us to a similar approach. A more recent work [18] extends the work of [8] to model network constraints.

However, the models of [8], [18] only deal with EV charging. In this case, the optimization problem reduces to minimizing a linear cost over a generalized polymatroid, which can be done exactly by the greedy algorithm. Here, we consider the full UC problem, of which EVs are only a component. We show that this problem remains tractable,

albeit by more complex methods (practical cutting-plane approaches), using submodular optimization to obtain separation oracles.

Finally, Angeli et al. [19] undertook the aggregation of EV flexibilities in the UC problem in the case of unique charging sessions per vehicle by a constraint-selecting mechanism which can be approximated by a greedy algorithm.

### D. Organisation of the paper

In Section II, we present the UC problem and the EV constraint set. In Section III, we recall basic results of generalized polymatroids and their applications to EVs, along the lines of [17] and [8]. In Section IV, we present theoretical results on the complexity of solving the UC problem with an exact aggregation of EVs, as well as present a practical cutting-plane algorithm for this optimization. Numerical results are presented and discussed in Section V. Finally, we offer some concluding remarks in Section VI.

## II. THE UC PROBLEM AND EV FLEXIBILITIES

We consider a Unit Commitment problem on a discrete time horizon $T = \{1, ..., T\}$ with time steps of duration $\tau$. In practice, the horizon is often one week, while the time step is equal to an hour.

### A. Modeling the Unit Commitment problem

Consider a set $\mathcal{M}$ of production units. Each element $m \in \mathcal{M}$ represents a single unit, which may be a nuclear or thermal (gas, coal, etc.) power plant, as well as a hydro-electric plant. The production of unit $m$ is represented by a vector $z^m = (z_t^m)_{t \in T} \in \mathbb{R}^T$, where $z_t^m$ represents the production at time $t$.

We require the vector $z^m$ to belong to a constraint set $\mathcal{K}^m$, which can differ according to the type of production unit. This constraint set generally includes upper and lower bounds on production at each instant, i.e., $k_t^m \le z_t^m \le \bar{k}_t^m$ for given bounds $(k_t^m)_{t \in T}, (\bar{k}_t^m)_{t \in T} \in \mathbb{R}^T$. For instance, nuclear units are subject to ramping constraints, as well as to minimal on/off duration constraints. The latter lead to MILP formulations, rendering the corresponding set $\mathcal{K}^m$ non-convex.

Variable (uncontrollable) renewable energy sources (solar, wind) are integrated via a residual demand $D \in \mathbb{R}^T$, obtained by subtracting the renewable production to the the power consumption, at every instant $t$. Finally, we consider an aggregate of EV flexibilities with constraint set $\mathcal{P}$, which aggregates the behavior of a large heterogeneous population of users. We will elaborate on this set in the next section.

The UC problem is of the form

$$ \min_{z,p} \sum_{m \in \mathcal{M}, t \in T} c_t^m z_t^m \quad (1a) $$

$$ \text{s.t.} \quad \sum_{m} z_{t}^{m} = D_{t} + p_{t}, \quad \forall t \in T \quad (1b) $$

$$ z^m \in \mathcal{K}^m, \quad \forall m \in \mathcal{M} \quad (1c) $$

$$ p \in \mathcal{P}. \quad (1d) $$
Here, $c_t^m$ denotes the unitary production cost at time $t$ for the production plant $m$ so that the total production cost is linear in the dispatching production variables $z^m$. The variable $p \in \mathbb{R}^T$ represents the charging power (positive or negative, in the case of V2G) of the fleet of EVs. Finally, the relation (1b) expresses the balance between production and demand at every time step.

## B. Modeling EV flexibilities

We consider EV constraints over the whole time horizon. For an individual, this requires the knowledge of charging availability slots, maximal charging power, and energy need at the end of each slot. Consider an EV $n \in \mathcal{N}$ and its charging profile $p^n$. At each time step $t \in T$, we have

$$ \underline{p}_t^n \le p_t^n \le \bar{p}_t^n. \quad (2) $$

If the EV is plugged in at time $t$, then $\bar{p}_t^n$ is equal to the maximal charging power available, typically based on charger limits, and $\underline{p}_t^n$ is equal to the maximal discharging power (negative). We include V2G mechanisms, allowing vehicles to inject power back into the grid. In the absence of V2G technology, $\underline{p}_t^n = 0$. If the EV is not plugged in at $t$, either because it is on the road or does not have access to a charging point, we have $\bar{p}_t^n = \underline{p}_t^n = 0$.

At each instant, the EV also has a state-of-charge (SoC) $\underline{SoC}_t^n$, bounded by the battery capacity $\overline{SoC}_t^n$ and the minimal energy required at time $t$, $\underline{SoC}_t^n$, giving that

$$ \underline{SoC}_t^n \le \underline{SoC}_t^n \le \overline{SoC}_t^n. \quad (3) $$

The minimal energy required at time $t$ is typically the energy required by the user to complete his or her next trip. Define $\gamma_t^n \ge 0$ the energy consumed by driving during time step $t$. Finally, we can link $\underline{SoC}^n$ and $p^n$ by

$$ \underline{SoC}_t^n = \underline{SoC}_{t-1}^n + p_t^n - \gamma_t^n, \quad \forall t \in T. \quad (4) $$

where $\underline{SoC}_0^n$ is the initial state-of-charge of the given user.

We can see that (3) and (4) can be combined into a constraint on the cumulative injected power:

$$ \underline{SoC}_t^n \le \sum_{t'=1}^{t} p_{t'}^n + \underline{SoC}_0^n - \sum_{t'=1}^{t} \gamma_{t'}^n \le \overline{SoC}_t^n, \quad \forall t \in T. \quad (5) $$

To simplify notations, let $\underline{s}_t^n = \underline{SoC}_t^n - \underline{SoC}_0^n + \sum_{t'=1}^t \gamma_{t'}^n$ and $\bar{s}_t^n = \bar{SoC}_t^n - \bar{SoC}_0^n + \sum_{t'=1}^t \gamma_{t'}^n$ such that (5) can be rewritten as follows:

$$ \underline{s}_t^n \le \sum_{t'=1}^{t} p_{t'}^n \le \bar{s}_t^n \quad \forall t \in T. \quad (6) $$

In this case, the individual EV constraint set is defined by

$$ \mathcal{P}^n = \{ p^n \in \mathbb{R}^T | p^n \text{ respects (2) and (6)} \}. \quad (7) $$

## C. Aggregating EV constraints

The power profile set $\mathcal{P}$ of constraint (1d) arising from the flexible EVs is in fact the Minkowski sum of the individual power profile sets of the EVs: $\mathcal{P} = \sum_{n \in \mathcal{N}} \mathcal{P}^n$. In general, this set has a very rich face description whose complexity can grow quickly with $\mathcal{N}$. This makes the UC (1) hard to solve.

To cope with the complexity of $\mathcal{P}$, a classical method is to aggregate the set constraints by using what we call a naive aggregation. This naive aggregation set $\hat{\mathcal{P}}$ is defined by summing the individual constraints:

$$ \hat{\mathcal{P}} = \left\{ p \in \mathbb{R}^T \left| \begin{array}{l} \sum_{n \in \mathcal{N}} p_t^n \le p_t \le \sum_{n \in \mathcal{N}} \bar{p}_t^n, \quad \forall t \in T \\ \sum_{n \in \mathcal{N}} \underline{s}_t^n \le \sum_{t'=1}^t p_{t'} \le \sum_{n \in \mathcal{N}} \bar{s}_t^n, \forall t \in T \end{array} \right. \right\} \quad (8) $$

Note that the aggregation method defines at most $4T$ constraints, thus $\hat{\mathcal{P}}$ has at most $4T$ facets.

It is immediate that $\hat{\mathcal{P}}$ is an outer approximation of $\sum_{n \in \mathcal{N}} \mathcal{P}^n$. The inverse is not true, as taking the Minkowski sum creates “mixed” facets, not obtained by a naive summation. However, we shall see that one can leverage the special character of the defining constraints (2),(6) to obtain an exact solution of the UC problem.

# III. GENERALIZED POLYMATROIDS AND SUBMODULAR OPTIMIZATION

In this section, we recall basic results on generalized polymatroids, based on Frank and Tardos [15] and Danilov and Koshevoy [16]. We also recall their application to EVs [8]. The considered ground set is $T = \{1, \dots, T\}$ where $T$ is the planning horizon.

In what follows, when considering a subset $A \subseteq T$ and a vector $\boldsymbol{x} \in \mathbb{R}^T$, we use the notation $x(A) = \sum_{a \in A} x_a$.

## A. Basics of generalized polymatroids

First, we define special types of set-functions.

**Definition 1.** A function $f: 2^T \to \mathbb{R} \cup \{+\infty\}$ is **submodular** if

$$ f(A) + f(B) \ge f(A \cap B) + f(A \cup B), \quad \forall A, B \subseteq T. \quad (9) $$

A function $g: 2^T \to \mathbb{R} \cup \{-\infty\}$ is **supermodular** if $-g$ is submodular.

The function $f$ is submodular if, and only if,

$$ f(A \cup \{a\}) - f(A) \ge f(B \cup \{a\}) - f(B), \quad \forall A \subset B \subseteq T. \quad (10) $$

This can be interpreted as a decreasing marginal utility, i.e., adding an individual element to a smaller set $A \subset B$ has more value than adding it to the larger set $B$. Submodularity may be thought of as an analog, for set-functions, of the notion of concavity.

**Definition 2.** Consider a submodular function $f$ and a supermodular function $g$ such that $g(\emptyset) = f(\emptyset) = 0$. The pair
$(g, f)$ is said **paramodular** if the following cross-inequality holds:

$$f(A) - g(B) \geq f(A \setminus B) - g(B \setminus A), \quad \forall A, B \subseteq \mathcal{T}. \qquad (11)$$

We can note that paramodularity ensures that the space between the two functions is not empty, i.e.,

$$\{x \in \mathbb{R}^{\mathcal{T}} | x(A) \leq f(A), \forall A \subseteq \mathcal{T}\} \cap \{x \in \mathbb{R}^{\mathcal{T}} | g(A) \leq x(A), \forall A \subseteq \mathcal{T}\} \neq \emptyset.$$

Polymatroids, introduced by Edmonds [20], are polyhedra defined by a submodular function as $\{x | x(A) \leq f(A), \forall A \subseteq \mathcal{T}\}$. This is inspired by the theory of matroids in which $f$ is the rank function [21]. Frank and Tardos [15] extended this notion to polyhedra defined by a paramodular pair, leading to the notion of generalized polymatroids.

**Definition 3.** Consider a paramodular pair of functions $(g, f)$. The polyhedron

$$Q(g, f) := \{x \in \mathbb{R}^{\mathcal{T}} | g(A) \leq x(A) \leq f(A), \forall A \subseteq \mathcal{T}\} \qquad (12)$$

is a **generalized polymatroid**, or a **g-polymatroid**. The pair $(g, f)$ is called the **border pair**, with $g$ the **lower border function** and $f$ the **upper border function**.

Generalized polymatroids have also appeared in work by Danilov and Koshevoy in the broader setting of discrete convexity, deadling with polyhedra whose edges are parallel to a unimodular collection of vectors. In particular, generalized polymatroids correspond to the special unimodular family consisting of the vectors $e_i - e_j$ and $e_i$ for $i, j \in \mathcal{T}$ originating from the root system $A_n$; we refer the reader to [16] for more information.

According to [15, Prop. 2.5], the border pair of a given g-polymatroid $Q \neq \emptyset$ is unique. In particular, we have $f(A) = \max_{x \in Q} x(A)$ and $g(A) = \min_{x \in Q} x(A)$ for every subset $A \subseteq \mathcal{T}$.

One of the main advantages of these polytopes is the following property, which is established in [22, Thm. 14.2.15], and also follows from [16, Sec. 7].

**Theorem 1.** Consider paramodular pairs $(g^i, f^i)$, $i \in [k]$. Then

$$\sum_i Q(g^i, f^i) = Q(\sum_i g^i, \sum_i f^i). \qquad (13)$$

In particular, g-polymatroids are stable by Minkowski sum.

The following key observation ensures that EV-flexibilities are modeled by generalized polymatroids.

**Theorem 2** ([17], [8]). For each EV $n \in \mathcal{N}$, the set $\mathcal{P}^n$ is a g-polymatroid.

As pointed out to us by [17], this follows from the laminar character of the family of constraints. Recall that a collection of sets $\mathcal{F}$ is **laminar** if

$$\forall A, B \in \mathcal{F}, A \subseteq B \text{ or } B \subseteq A \text{ or } A \cap B = \emptyset, \qquad (14)$$

i.e., any two sets are either contained in or contain each other or are non-intersecting. It is straightforward to see that the family of subsets $\mathcal{F} = \{\{t\}|t \in \mathcal{T}\} \cup \{\{1, \dots, t\}|t \in \mathcal{T}\}$ on which the initial constraints 2, 6 are defined is a laminar set family. For an arbitrary set function $f$ (not necessarily submodular), the polyhedron $\{x|x(A) \leq f(A), \forall A \in \mathcal{F}\}$ is in fact a generalized polymatroid (see [23, Sec. 3], [16, Sec. 6]).

Without loss of generality, we assume that the initial collection of constraints (2) and (6) is tight. By this, we mean that, considering the border pair $(g^n, f^n)$ such that $\mathcal{P}^n = Q(f^n, g^n)$, we have $f^n(\{t\}) = \bar{p}_t^n$ and $g^n(\{t\}) = \underline{p}_t^n$, as well as $f^n(\{1, \dots, t\}) = \bar{s}_t^n$ and $g^n(\{1, \dots, t\}) = \underline{s}_t^n$ for each $t \in \mathcal{T}$. We denote by $(g, f) = (\sum_n g^n, \sum_n f^n)$ the border function of the Minkowski sum $\sum_n \mathcal{P}^n$, which is a g-polymatroid, by Theorem 1 and Theorem 2.

*Remark.* When optimizing a linear cost over g-polymatroids, the greedy algorithm gives an exact solution (see [22]). This setting is described in [8, Sec. IV] but does not suffice when the g-polymatroid is integrated into a larger model in the UC problem.

To tackle the larger UC problem, we rely on base polyhedra, which are special cases of g-polymatroids.

**Definition 4.** Consider $\tilde{\mathcal{T}} = \mathcal{T} \cup \{\mathcal{T} + 1\}$ and a submodular function $f$ such that $f(\tilde{\mathcal{T}})$ is finite. The **base polyhedron** with border function $f$ is the set

$$\mathcal{B}(f) := \left\{ x \in \mathbb{R}^{\tilde{\mathcal{T}}} \mid \begin{array}{l} x(\tilde{\mathcal{T}}) = f(\tilde{\mathcal{T}}) \\ x(A) \leq f(A), \forall A \subseteq \tilde{\mathcal{T}} \end{array} \right\}. \qquad (15)$$

A **0-base polyhedron** is a base polyhedron such that $f(\tilde{\mathcal{T}}) = 0$.

We can easily show that a base polyhedron is a g-polymatroid by taking $g(A) := f(\tilde{\mathcal{T}}) - f(\tilde{\mathcal{T}} \setminus A)$ [22]. In fact, the correspondence goes even further.

**Theorem 3.** (See [22, Thm. 14.2.5]) Every g-polymatroid $Q(g, f)$ is the projection of a 0-base polyhedron.

Therefore, optimizing over a g-polymatroid reduces to optimizing over the corresponding base polyhedron [22]. These polyhedra can easily be described as, given a paramodular pair $(g, f)$, the submodular function defining the base polyhedron is given by

$$f^*(A) = \begin{cases} f(A) & \text{if } A \subseteq \mathcal{T} \\ -g(\mathcal{T} \setminus A) & \text{if } T + 1 \in A \end{cases}. \qquad (16)$$

## IV. SOLVING THE UC PROBLEM WITH EVs

We next show that the UC problem integrating EV charging flexibilities can be solved efficiently using an approach combining cutting planes and submodular optimization. In Section IV-A, we provide a theoretical complexity result. Furthermore, we give in Section IV-B a practical cutting-plane approach, used to solve our real instances.
A. Polynomial-time solvability of the convex UC problem

In this subsection, we suppose that the constraint sets $\mathcal{K}^m$ are polyhedra given by collections of linear inequalities, so that the production $z^m$ of unit $m$ must belong to the set $\mathcal{K}^m = \{z^m \in \mathbb{R}^T \mid F^m z^m \le b^m\} \subset \mathbb{R}^T$, where $F^m$ is a $r_m \times T$ matrix and $b^m$ is a column vector of dimension $r_m$, where $r_m$ is the number of inequalities. This allows both for bound constraints and dynamic linear constraints on the production but excludes minimal on/off duration constraints for nuclear plants (which lead to nonconvex – in fact MILP – formulation). We refer to this problem as the convex UC problem. The convexity assumption is useful to get a theoretical complexity result; it will be relaxed in the practical method of Section IV-B.

Our approach relies on the analysis of linear programs defined implicitly by separation oracles, which goes back to the work of Gröetschel, Lovász and Schrijver [24]. To obtain a tighter explicit bound, we use a recent improvement of their approach [25] relying on the cutting-plane method of [26].

A key notion is that of a polyhedral separation oracle [25]. Given a polyhedron $P$ in $\mathbb{R}^d$ defined by a finite collection of inequalities $(G_i x \le h_i)_{i \in \mathcal{I}}$, with $G_i \in \mathbb{R}^{1 \times d}$, $h_i \in \mathbb{R}$, a polyhedral separation oracle is an algorithm which, given a vector $x \in \mathbb{R}^d$, asserts that $x \in P$ or returns a violated inequality, i.e., an index $i \in \mathcal{I}$ such that $G_i x > h_i$. Note that this notion is more demanding than the classical notion of strong separation oracle, used in [24]. The number of inequalities $|\mathcal{I}|$ is allowed to be exponential in $d$.

We work in the Turing model of computation, so we assume that $F^m$ is a rational matrix and $b^m$ is a rational vector, for all $m \in \mathcal{M}$. Without loss of generality, after multiplying by common denominators, we will even assume that the entries of $F^m$ and $b^m$ are integers. We also assume that the bounds $\underline{s}_t^n, \bar{s}_t^n, \underline{p}_t^n$ and $\bar{p}_t^n$ arising in the description of the EVs are rational numbers, and even integers, which is a matter of scaling (choice of units of the charging vector $p^n$). Then, we denote by $B$ the maximal absolute value of all the integer coefficients appearing in the problem input, i.e., of the entries of the matrix $F^m$, of the vector $b^m$, and of the bounds $\underline{s}_t^n, \bar{s}_t^n, \underline{p}_t^n$ and $\bar{p}_t^n$. The vector-valued variable of the UC problem is the vector $((z^m)_{m \in \mathcal{M}}, p) \in (\prod_{m \in \mathcal{M}} \mathbb{R}^T) \times \mathbb{R}^T$. So the dimension (total number of scalar variables) is $d = (|\mathcal{M}| + 1)T$. In this context, given a vector $x = ((z^m)_{m \in \mathcal{M}}, p)$, a polyhedral separation oracle either asserts that $x$ belongs to the feasible set of the UC problem or returns either an inequality of the system $F^m z^m \le b^m$ violated by $z^m$, a generalized-polymatroid type inequality $p(A) \le f(A)$ or $p(A) \ge g(A)$ violated by $p$ for some subset $A \subset \mathcal{T}$, or a violated global demand inequality $\sum_m z_t^m \le D_t + p_t$ for some $t \in \mathcal{T}$ (when considering the demand equality as two opposite inequalities).

**Theorem 4.** The convex UC problem integrating a collection of $N$ flexible EVs can be solved in a number of polyhedral separation oracle queries bounded by $O(d^3 \log(dBN))$, with $d$ the dimension and $B$ the maximal absolute value of integer coefficients of the problem input.

**Remark.** This bound is independent of the bit-size of of the cost vector $c^m$.

Before proving this theorem, we explain how such an oracle can be implemented efficiently. Given a vector $x = ((z^m)_{m \in \mathcal{M}}, p)$, checking the validity of the inequalities $F^m z^m \le b^m$ or of the global demand constraint is immediate (there are $\sum_m r_m + T$ scalar constraints that can be checked one by one). The hard part of the separation oracle consists in deciding whether the vector $p$ belongs to the Minkowski sum $\sum_n P^n$, which is described by $2^T$ g-polymatroid type inequalities. We show that this can be done in polynomial time.

**Lemma 5.** Let $f^*$ be the submodular function defined as per (16), where $(g, f)$ is the border pair of the generalized polymatroid $\sum_n P^n$. Then, a polyhedral separation oracle for the Minkowski sum $\sum_n P^n$ can be implemented in $O((T^4 E(f^*) + T^5) \log(TW))$ arithmetic operations, where $E(f^*)$ is the number of arithmetic operations needed to evaluate $f^*$, and $W = \max_{A \subseteq \mathcal{T}} |f^*(A)|$ the maximal absolute value of $f^*$. A strongly polynomial version can be implemented in $O(T^5 E(f^*) + T^6)$ arithmetic operations.

*Proof.* The polyhedral separation oracle will be implemented by a reduction to Submodular Function Minimization (SFM). In fact, since $\sum_{n \in \mathcal{N}} P^n$ is a g-polymatroid, define $(g, f)$ the corresponding border pair. We can then define $f^*$ as in (16) and $B(f^*)$ the corresponding 0-base polyhedron. For a vector $x \in \mathbb{R}^T$, define the extended vector $x^* = (x_1, x_2, \dots, x_T, -\sum_{t \in \mathcal{T}} x_t) \in \mathbb{R}^{T+1}$. In this case,

$$x \in \sum_{n \in \mathcal{N}} P^n \iff x^* \in B(f^*), \quad (17)$$

meaning that the membership problem of $\sum_{n \in \mathcal{N}} P^n$ is equivalent to that of $B(f^*)$, and the separation problem for $\sum_{n \in \mathcal{N}} P^n$ can be deduced from that for $B(f^*)$.

Given a vector $p \in \mathbb{R}^T$, the separation problem is given by minimizing the submodular function $f^* - p^*$. In fact, if for a minimal subset $A$, $(f^* - p^*)(A) \ge 0$, then $p^* \in B(f^*)$ and $p \in \sum_{n \in \mathcal{N}} P^n$, thus the solution is an exact aggregation. If $(f^* - \bar{p}^*)(A) < 0$, then the constraint $\bar{p}^*(A) \ge f^*(A)$ is violated and yields a cutting plane. The corresponding cut for $\sum_{n \in \mathcal{N}} P^n$ can be deduced from (16).

Therefore, the oracle consists in calling a SFM algorithm. Such an algorithm with a weakly polynomial complexity is given by Iwata and Orlin [27], while the strongly polynomial algorithm is given by Orlin [28]. This leads to the complexity bounds stated in the lemma. $\square$

We now prove Theorem 4.

*Proof of Theorem 4.* Dadush et al. [25, Thm. 1.1] showed that if $P \subset \mathbb{R}^d$ is a polyhedron, and if $c \in \mathbb{Q}^d$, then a vector in $P$ minimizing the linear form $x \mapsto c \cdot x$ can be obtained in a number of calls to a polyhedral separation oracle in $O(d^2 \log(d/\delta))$, where $\delta$ is a geometric condition number.

Owing to the aggregation of $N$ charging constraint sets, we have that the maximal absolute value $\bar{B}$ of the integers
arising in the problem input satisfies $\bar{B} \le BN$. Moreover, it follows from [25, p. 2703, para. 2, line 4] that $\delta \ge 1/(\bar{B}^{2d}d^{d+1})$. This gives us the bound of $O(d^3 \log(dBN))$ for the number of calls to the separation oracle. $\square$

**Corollary 6.** The convex UC problem integrating $N$ flexible EVs can be solved in $N \log N$ poly($T$, $d$, $\log B$, $r$) arithmetic operations, where $r = \sum_m r_m$ is the total number of constraints satisfied by production units, and poly($\cdot$) denotes a function polynomially bounded in its arguments.

*Proof.* By Theorem 4, the convex UC can be solved in $O(d^3 \log(dBN))$ separation oracle calls. By Lemma 5 and the preceding remarks, the separation oracle can be implemented in $O(T^5 E(f^*) + T^6 + r)$ arithmetic operations.

We have $f^* = \sum_n f^{*,n}$, where $f^{*,n}$ denotes the submodular function defining the base polyhedron of $P^n$, replacing $f,g$ by $f^n,g^n$ in (16). Therefore, evaluating $f^*(A)$ reduces to evaluating $f^{*,n}(A)$ for each $n \in \mathcal{N}$, i.e.,

$$f^*(A) = \sum_{n \in \mathcal{N}} f^{*,n}(A) = \sum_{n \in \mathcal{N}} \max_{x \in B(f_n^*)} x(A) . \quad (18)$$

In practice, this involves solving $N$ Linear Programs (LPs) with $T$ variables and $O(T)$ constraints, of type (2) and (6). Recall that a LP in dimension $n$ with a number of inequalities $m \ge n$ can be solved by interior point methods in time $O(m^{1.5}n^2(L+|\log \epsilon|))$ where $L$ is the bit-length of the input, and $\epsilon$ is the desired accuracy, see [29], [30]. Moreover, the bit-size of $\epsilon$ needed to recover the exact solution is in $O(L)$, see [31, Thm. 2].

In our case, $m = 4T$, $n = T$, and $L = O(T \log B)$, yielding a complexity of the evaluation oracle of $O(NT^{4.5} \log B)$.

By combining these elements, we obtain a final complexity of $O(d^3 \log(dBN)(NT^{9.5} \log B + r))$ for the resolution of the convex UC problem, with the announced dependence of $N \log N$ in the number of flexible EVs. $\square$

## B. The practical cutting-plane algorithm

Having established the theoretical complexity in Corollary 6, we present here a practical algorithm to solving UC problem with an exact aggregation of EV constraint sets. The algorithm, described in Algorithm 1, iteratively solves the UC problem (1) while enriching the constraint set at each iteration. We build a decreasing sequence of polytopes

$$\mathcal{P}^{(0)} \supset \mathcal{P}^{(1)} \supset \dots$$

such that $\mathcal{P}^{(0)} = \hat{\mathcal{P}}$ the naive aggregation polytope (8), $\mathcal{P}^{(\infty)} := \cap_{k \in \mathcal{N}} \mathcal{P}^{(k)} = \sum_{n \in \mathcal{N}} \mathcal{P}^n$ the exact polytope, and each intermediate polytope has a richer constraint dictionary than the previous one.

Additionally, consider, for $k \in \mathcal{N}$, the problem

$$\min_{z,p} \sum_{m \in \mathcal{M}, t \in \mathcal{T}} c_t^m z_t^m \quad (UC_{k-a})$$

$$\text{s.t.} \quad (1b), (1c) \quad (UC_{k-b})$$

$$p \in \mathcal{P}^{(k)} \quad (UC_{k-c})$$

i.e., the UC problem with the enriched polytope of iteration $k$. After solving problem $(UC_k)$, we can apply the separation

oracle described in the proof of Lemma 5 to the EV solution $p_k$: if the solution is an exact aggregation, the algorithm stops. Otherwise, the separation oracle returns a violated constraint which can be added to build the enriched constraint set $\mathcal{P}^{(k+1)}$. In practice, running the SFM algorithm allows for far more constraints to emerge as it must evaluate $f^*$ repeatedly, and we use the whole collection of cuts obtained in this way, all at once, to enrich the constraint set, passing from $\mathcal{P}^{(k)}$ to $\mathcal{P}^{(k+1)}$.

<caption>**Algorithm 1:** A cutting-plane resolution of UC</caption>

1. $\mathcal{P}^{(0)} \leftarrow \hat{\mathcal{P}}$;
2. $k \leftarrow 0$;
3. **for** $k \ge 0$ **do**
4. &nbsp;&nbsp;&nbsp;&nbsp;Solve $(UC_k)$ and retrieve optimal $p_k$;
5. &nbsp;&nbsp;&nbsp;&nbsp;Get $A \in \arg \min(f^* - p_k^*)$ by SFM;
6. &nbsp;&nbsp;&nbsp;&nbsp;Get $C_k$ polyhedron defined by facets calculated during SFM;
7. &nbsp;&nbsp;&nbsp;&nbsp;**if** $(f^* - p_k^*)(A) \ge 0$ **then**
8. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else**
9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$p_k$ is disaggregeable: STOP;
10. &nbsp;&nbsp;&nbsp;&nbsp;**end**
11. **end**
12. **end**

**Proposition 7.** *Algorithm 1 terminates and returns an optimal solution.*

*Proof.* By Theorem 2, the set $\sum_{n \in \mathcal{N}} \mathcal{P}^n$ is defined by at most $2^{T+1}$ constraints. Each iteration of Algorithm 1 either yields an exact solution, terminating the algorithm, or returns at least one tight constraint of $\sum_{n \in \mathcal{N}} \mathcal{P}^n$, which gives the termination result. The final solution provides a feasible EV charging profile, as certified by the separation oracle, and the resolution of the LP $(UC_k)$ ensures optimality. $\square$

## V. NUMERICAL RESULTS OF THE CUTTING-PLANE ALGORITHM

We next present a realistic instance of the European grid and the French EV fleet, as well as some numerical results of Algorithm 1 applied to this instance.

### A. The European Grid Instance

Following the EU Electricity Regulation in 2019, the European Network of Transmission System Operators for Electricity (ENTSO-E) began work on the European Resource Adequacy Assessment (ERAA) as part of a toolbox to improve comprehension of the European power system and ensure that investments and regulations today are coherent with future needs [9].

In particular, the ERAA report provides a relatively complete and open-access dataset on the European instance, describing various aspects of the grid by electricity market node. In this paper, we exploit the data of the 2023.2 edition. In particular, this dataset gives a projected demand scenario on each node, installed generation capacities aggregated
per type of production unit, capacity factors for concerned
renewable energy sources, and interconnection capacities
between market nodes for selected target years (2025, 2028,
2030, and 2033) and climatic scenarios (corresponding to
weather conditions of historical years ranging from 1982 to
2016).

Using this data, we were able to implement a seven-
country UC problem centered around the French market
node. In this problem, we consider a total of 64 aggregated
production units (nuclear, thermal, and hydroelectric plants),
renewable energy sources being integrated to the residual
demand.

B. Modeling the French fleet of EVs

In order to simulate the aggregation of EVs in the UC problem, we used the EV data of the *Enquête de Mobilité des Personnes* [10], a survey on the behavior of French drivers. From this survey, we can extract different user profiles and generate realistic individual weekly driving schedules with potential charging slots and driving distance, thus energy need. This data directly supplies us with different profiles of EV constraint sets described in Section II-B.

In order to correctly size the proportion of EVs present
in the UC problem, we rely on predictions by RTE [4]. In
this report, several growth scenarios are presented, with the
*Crescendo* being the most likely. Considering this scenario,
there will be 8.5 million EVs in France in 2030, 60%
of which should subject themselves to smart charging and
supposed here made available in the UC problem. As such,
we consider a fleet of 5.1 million "controllable" EVs, which
each belong to one of *N* different profiles chosen at random.

Finally, we choose SoC₀ the initial SoC and SoC_T the
target SoC (minimal level for the end of the optimization
horizon demanded by each user) such that the total EV power
consumption should fall around 3 – 4% of the total demand
of the period.

C. Implementation

The UC problem is implemented in Python 3.12 as a
LP and solved by CPLEX 22.1.2. The separation oracle
is implemented in Julia 1.9.4 and is based on an exist-
ing SFM package [32], which implements the Fujishige-
Wolfe minimum norm point algorithm [33] as described
by Chakrabarty et al. [34]. Though the complexity of this
algorithm is theoretically worse than that of [27], it is shown
to outperform the latter algorithm in practice.

Finally, the evaluation oracle of $f^* - p_k^*$ is implemented
as described in the proof of Corollary 6. In practice, we
implemented a simple parallelization of the calculation of
the $N$ LPs using multithreading.

D. Benchmark

In order to evaluate the performance of Algorithm 1,
simulations were run on the projected ERAA data from the
week, starting on Monday, of January 13, 2030 with the
climatic conditions of 2003 (see Section V-A), over horizons
$T \in \{24, 48, 96, 168\}$ and considering different numbers of

EV user profiles $N \in \{2, 10, 50, 100\}$, where the population of 5.1 million EVs is evenly distributed among profiles. These simulations were run on 24 cores of an Intel® Xeon® Platinum 8260 processor, with 10 runs for $T = 24, 48, 96$ and 5 for $T = 168$ $^1$, each run differing in the selected EV profiles.

In this paper, we report numerical results in the convex UC
setting, corresponding to the available public data, though
tests on the "full" UC problem (MILP model integrating
dynamic on/off constraints) yielded similar performance.

These simulations show Algorithm 1 to terminate in few
iterations, as illustrated by Figure 1. In fact, all instances
required fewer than 8 iterations to terminate, and most fewer
than 5. Furthermore, the number of cuts calculated by the
separation oracle remained far smaller than the theoretical
$2^{T+1}$ bound, as shown by Figure 2.

The main point of improvement for this algorithm is the
runtime, as illustrated by Figure 3. The bottleneck is the
separation oracle; for $T = 168$ and $N = 50$, 85% of the com-
putation time is taken by the separation oracle, for instance.
The multithreading implementation of the evaluation oracle
is already faster than a sequential calculation (8 times faster
on average for $T = 96$, $N = 50$ for example); exploring
other parallelization implementations could further improve
the performance. This will be the object of future studies.

VI. CONCLUDING REMARKS

We studied the integration of flexible EVs in a unit commitment problem. We showed that this problem can be solved exactly and in a scalable way for instances with a large number *N* of categories of flexible EV users, with a theoretical complexity scaling in *N* log *N*. We also developed a practical cutting-plane algorithm, which, on a real large-scale instance, converged in few iterations. This work can be extended in several ways. First, improvements of the practical algorithm can be considered, such as exploring other strategies to add cutting planes. Next, it would be interesting to obtain tight bounds on the true number of facets of the polytopes representing EV flexibilities (experiments in small dimension indicate that for typical instances, this number is far below the theoretical *O*(2<sup>*T*+1</sup>) bound); parcimonious approximations of these polytopes may also be investigated. Finally, it may be interesting to cover other types of flexibilities, such as hydropower.

ACKNOWLEDGMENT

We thank Gleb Koshevoy, for pointing out to us the
generalized polymatroid structure of EV flexibilities. We also
thank Juliette Lesturgie for her help with understanding the
power system and UC constraints. We also thank both of
them for many discussions.

<footnote n="1">¹The case $T = 168$, $N = 100$ is not included in the figures because the solver crashed during execution. We suspect that this is due to a known memory leak of the Julia 1.9 using multithreading on Linux.</footnote>
<figure><img src="image_2.png" /><figcaption>Fig. 1. Number of iterations performed by Algorithm 1. The error bar represents extreme values obtained, as well as the average value. Despite an increase with problem size, the iteration number remains low.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Fig. 2. Number of cuts added to UC. There is no point for $N = 2$ at $T = 24$ as every simulation converged in 1 iteration. All values are much smaller than the theoretical $2^{T+1}$ bound.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 3. Resolution time as a function of $T$ and $N$. As expected, it increases with $T$ and $N$.</figcaption></figure>

REFERENCES

[1] I. Abdou and M. Tkiouat, "Unit Commitment Problem in Electrical Power System: A Literature Review," *International Journal of Electrical and Computer Engineering (IJECE)*, vol. 8, p. 1357, June 2018.

[2] M. Tahanan, W. Van Ackooij, A. Frangioni, and F. Lacalandra, "Large-scale Unit Commitment under uncertainty," *4OR*, vol. 13, pp. 115–171, June 2015.

[3] J. Meus, K. Poncelet, and E. Delarue, "Applicability of a Clustered Unit Commitment Model in Power System Modeling," *IEEE Transactions on Power Systems*, vol. 33, pp. 2195–2204, Mar. 2018.

[4] RTE, "Integration of Electric Vehicles into the power system in France," tech. rep., May 2019.

[5] RTE, "Bilan prévisionnel 2023-2035," tech. rep., 2023.

[6] H. R. Tiwary, "On the Hardness of Computing Intersection, Union and Minkowski Sum of Polytopes," *Discrete & Computational Geometry*, vol. 40, pp. 469–479, Oct. 2008.

[7] O. Beaude, P. Benchimol, S. Gaubert, P. Jacquot, and N. Oudjane, "A Privacy-Preserving Method to Optimize Distributed Resource Allocation," *SIAM Journal on Optimization*, vol. 30, pp. 2303–2336, Jan. 2020.

[8] K. Mukhi, G. Loho, and A. Abate, "Exact Characterization of Aggregate Flexibility via Generalized Polymatroids," Mar. 2025. arXiv:2503.23458.

[9] ENTSO-E, "ERAA - European Resource Adequacy Assessment." https://www.entsoe.eu/eraa/.

[10] Ministère De L'Environnement (SDES), "Enquête Mobilité des Personnes - 2019," 2021.

[11] F. L. Müller, O. Sundström, J. Szabó, and J. Lygeros, "Aggregation of energetic flexibility using zonotopes," in *2015 54th IEEE Conference on Decision and Control (CDC)*, pp. 6564–6569, Dec. 2015.

[12] P. Jacquot, O. Beaude, P. Benchimol, S. Gaubert, and N. Oudjane, "A Privacy-preserving Disaggregation Algorithm for Non-intrusive Management of Flexible Energy," in *2019 IEEE 58th Conference on Decision and Control (CDC)*, pp. 890–896, Dec. 2019. ISSN: 2576-2370.

[13] K. Mukhi and A. Abate, "An Exact Characterisation of Flexibility in Populations of Electric Vehicles," in *2023 62nd IEEE Conference on Decision and Control (CDC)*, (Singapore, Singapore), pp. 6582–6587, IEEE, Dec. 2023.

[14] N. K. Panda and S. H. Tindemans, "Efficient quantification and representation of aggregate flexibility in Electric Vehicles," *Electric Power Systems Research*, vol. 235, p. 110811, Oct. 2024.

[15] A. Frank and É. Tardos, "Generalized polymatroids and submodular flows," *Mathematical Programming*, vol. 42, pp. 489–563, Apr. 1988.

[16] V. I. Danilov and G. A. Koshevoy, "Discrete convexity and unimodularity—I," *Advances in Mathematics*, vol. 189, pp. 301–324, Dec. 2004.

[17] G. Koshevoy, "Personnal communication on g-polymatroids," Feb. 2025.

[18] K. Mukhi and A. Abate, "Polymatroidal Representations of Aggregate EV Flexibility Considering Network Constraints," Sept. 2025. arXiv:2509.16134.

[19] D. Angeli, Z. Dong, and G. Strbac, "Exact aggregate models for optimal management of heterogeneous fleets of storage devices," *IEEE Transactions on Control of Network Systems*, vol. 11, no. 3, pp. 1430–1439, 2023.

[20] J. Edmonds, "Submodular Functions, Matroids, and Certain Polyhe dra," in *Combinatorial Structures and their Applications* (R. Guy, H. Hanani, N. Sauer, and J. Schonheim, eds.), pp. 69–87, Gordon and Breach, New York, 1970.

[21] H. Whitney, "On the Abstract Properties of Linear Dependence," *American Journal of Mathematics*, vol. 57, p. 509, July 1935.

[22] A. Frank, *Connections in combinatorial optimization*. No. 38 in Oxford lecture series in mathematics and its applications, Oxford: Oxford Univ. Press, 1. publ ed., 2011.

[23] N. A. Borsik, A. Frank, P. Madarasi, and T. Takács, "Prefix-bounded matrices," May 2025. arXiv:2505.10739.

[24] M. Grötschel, L. Lovász, and A. Schrijver, *Geometric Algorithms and Combinatorial Optimization*. No. v.2 in Algorithms and Combinatorics Ser, Berlin, Heidelberg: Springer Berlin / Heidelberg, 1988.

[25] D. Dadush, L. A. Végh, and G. Zambelli, "On finding exact solutions of linear programs in the oracle model," in *Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, pp. 2700–2722, Society for Industrial and Applied Mathematics, 2022.

[26] H. Jiang, Y. T. Lee, Z. Song, and S. C.-w. Wong, "An improved cutting plane method for convex optimization, convex-concave games, and its applications," in *Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing*, (Chicago IL USA), pp. 944–953, ACM, June 2020.

[27] S. Iwata and J. B. Orlin, "A Simple Combinatorial Algorithm for Submodular Function Minimization," in *Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms*, pp. 1230–1237, Society for Industrial and Applied Mathematics, Jan. 2009.

[28] J. B. Orlin, "A faster strongly polynomial time algorithm for submod- ular function minimization," *Mathematical Programming*, vol. 118, pp. 237–251, May 2009.

[29] J. Renegar, *A Mathematical View of Interior-Point Methods in Convex Optimization*. Society for Industrial and Applied Mathematics, Jan. 2001.

[30] A. Ben-Tal and A. S. Nemirovskij, *Lectures on modern convex optimization: analysis, algorithms, and engineering applications*. - Includes index. No. 2 in MPS-SIAM series on optimization, Philadelphia, Pa: SIAM, 2001.

[31] Y. Ye, "On the finite convergence of interior-point algorithms for linear programming," *Mathematical Programming*, vol. 57, pp. 325–335, May 1992.

[32] E. Lock, "SubmodularMinimization.jl," 2025. https://github.com/edwinlock/SubmodularMinimization.jl.

[33] S. Fujishige and S. Isotani, "A Submodular Function Minimization Algorithm Based on the Minimum-Norm Base," *Pacific Journal of Optimization*, vol. 4, 2009.

[34] D. Chakrabarty, P. Jain, and P. Kothari, "Provable Submodular Mini- mization using Wolfe's Algorithm," in *Advances in Neural Information Processing Systems*, vol. 27, Curran Associates, Inc., 2014.