I have a finite set of $n$ elements $A$, and a submodular function $f:2^A\rightarrow R$.

Let $g:[0,1]^n\rightarrow {R} $ be the Lovász extension of $f$.

I want to solve the following optimization function over the variables $x \in [0,1]^n, y \in[1, L ]$ for some known constant $L>1$.

Minimize $g(x) + c /y $

S.t. $x_i \geq c_i + d_i \cdot y$

for constants $c>0$, and $c_i,d_i \in R$.

I know that since $f$ is submodular then $g$ is convex, and since $c>0$, the objective is convex so convex optimization algorithms could work. However, I want to find an exact optimum in polynomial time. Since the objective is very structured ($g$ can be partitioned into a finite number of domains in which in each of them $g$ is a linear function) then I hope that there is a way to get an exact solution and not just approach the optimal solution using something like the interior point method.

One non-polynomial option is to go over all regions where $g$ is linear. In each, we can write the objective function as a function only of $y$, and optimize the single parameter function (which is minimizing a quadratic function in an interval).