Tag Info

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