13

I am going to assume that $x \in \mathbb{N}$ and $y \in \mathbb{N}$ are variables, and that $C \in \mathbb{N}$ is a constant. In this case, you can benefit from the fact that your equality constraint does not have that many possible solutions. Case 1: $C = 1$ This only happens when $y=0$ or $y = x$. Assume that we have some upper bounds $\bar{x}$ and $\bar{y}...


9

Not sure about solving the LP relaxation, but you can get a closed-form lower bound from LP duality, without calling any solver. Let $y_j$ be the dual variable for constraint $j\in U$. The dual LP is to maximize $\sum_j y_j$ subject to \begin{align} \sum_{j \in s_i} y_j &\le 1 &&\text{for $i\in \{1,\dots,m\}$} \\ y_j &\ge 0 &&\text{...


5

I am pretty sure the answer is NO! Consider the graph consisting of a $K_5$ (the fully connected graph with 5 nodes) and two additional nodes $r_1, r_2$ that have an edge to each of the nodes in the $K_5$. The optimal LP relaxation $S_{hi}$ is taking all nodes with value $\frac{1}{2}$. Adding the extra odd circle constraints one can get an optimal solution $...


3

Given what appears to be a nonlinear constraint (the 5% deviation constraint) and a nonlinear (and apparently arbitrarily complex) objective function, I would not be optimistic about finding a provably optimal solution. If you are willing to settle for a "good" solution, there are a variety of metaheuristics that might be applicable. Recommendation ...


2

I am pretty sure the answer is again NO. And it can be seen with the same graph as in the previous question here. Consider the graph consisting of a $K_5$ (the fully connected graph with 5 nodes) and two additional nodes $r_1, r_2$ that have an edge to each of the nodes in the $K_5$. First note that if we force any of the nodes $r_1, r_2$ to take value $0$ ...


1

AFAIK, some optimization software such as GAMS has some nice functions to deal with this. For example, function likes factorial (fact(x)). Indeed, some estimations for the factorial function using the probability distribution functions like Gama or Beta might be applied and be interpreted using (in)equality constraints. Reference: Factorial, Gamma and ...


Only top voted, non community-wiki answers of a minimum length are eligible