Consider a graph $G=(V,E)$ with nonnegative weight function on the edges $w$.How would you express in LP that you want to allow cycles in $G$ with total weight at most $s$ ?I've found this while googling:$\sum_{v\in S} (d_S(v) -1)x_v \geq b(S)  $ for all $S\subseteq V$Where $d_S(v)$ is the degree of $v$ in the subgraph $G_s=(S,E[S])$ ($E[S]$ is the set of edges with both endpoints in $G$) and $b(S)=|E[S]|-|S|+1$ and $x_v$ is a boolean variable for all $v \in V$ describing if $x_v$ was picked by the LP. This constraint is for making sure we pick a set of vertices such that if we remove them from the graph it will be acyclic, however, I want to allow cycles of weight at most $s$.(If anyone's interested, it's taken from page 16 here)
Linear programming - How to allow cycles with weight at most s?
ds.algorithms;graph theory;linear programming