8

Maybe the unnecessarily large value for $A$ is causing numerical trouble. Try instead $A = \max_{i,j} p_{i,j} = 9$. Probably your $=0$ in the declaration of $x$ should be $\ge 0$. In fact, you generally need to declare $x$ to be binary when you include side constraints.


5

By Farkas lemma, infeasibility of $Ax\leq b$ is equivalent to feasibility of $A^Ty = 0, y^Tb < 0, y\geq 0$, or more practically useful $A^Ty=0, y^Tb \leq -1, y\geq 0$. Unfortunately, this will lead to a bilinear model when you parameterize $b(z)$. It is fairly similar to an application I worked on a decade ago Oops! I cannot do it again: Testing for ...


5

Consider maximizing $\sum_{i=1}^n x_i$ subject to $x$ binary and $\sum_{i=1}^n i x_i \leq 2$ Solve relaxation and it gives $x_1 = 1, x_2 = 1/2$ with remaining variables 0. Branch on $x_2 = 0$ and the new solution is $x_1 = 1, x_3 = 1/3$ with the rest 0. Continue in the same fashion and you will have to go through fixing all variables. Had you minimized $\...


4

I doubt you can do so in polynomial time without any additional condition. Let $g$ be an arbitrary polynomial function, and let $f$ be defined by $f(X) = g(X) - C^{T}X$ over $B(0, R)$, and an appropriate extension so that it's twice differentiable with bounded Hessian over $\mathbb{R}^{n}$. Then, $f(X) + C^{T}X = 0$ reduces to $g(X) = 0$, i.e., your setting ...


3

I think this can be approached using a constraint generation technique (variant of Benders decomposition), although I have no idea if it would efficient. By reordering the rows of $A$, we can assume that $$b(z)=\left[\begin{array}{c} \hat{b}\\ c+e-z \end{array}\right]$$where $\hat{b}\in\mathbb{R}^{d-m}$, $c\in \mathbb{R}^m$, $e=(1,\dots,1)^\prime \in \mathbb{...


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