New answers tagged

4

Based on the mentioned references, suppose the primal problem is: \begin{align} \begin{array}{cl} \underset{}{\text{minimize}} & c x \\ \text{subject to} & Ax = a \\ & Dx \leq e \\ & x \geq \text{0} \end{array} \end{align} The idea behind Lagrangian relaxation is to relax the complicating constraints to produce an easier problem by adding ...


6

This is called Lagrangian relaxation, no matter what subset of constraints you choose to dualize.


10

Strict positivity, $x > 0$, is equivalent to the existence of nonnegative variable, $r \geq 0$, such that $xr \geq 1$. This means that it can be represented in second-order cone programming by the conic quadratic constraint $$x+r \geq \sqrt{ (x-r)^2 + 1^2 }.$$ To see this, just square both sides of the inequality and expand. Conclusively, MISOCP (mixed-...


3

The constraint is defined only for triples $(i,j,k)$ satisfying the domain conditions, including the requirement that $k\in K(i,j)$. So I think it is fine to just point out that $K(i,j)$ can be empty and remind the reader that $K(i,j)=\emptyset$ implies there are no instances of this constraint for that combination of $i$ and $j$. In other words, I think ...


4

One approach is to define a sparse set $T$ of triples: $$T=\{i\in [I], j \in [I], k\in [I]: A_i \cap A_j \cap A_k \not= \emptyset\}$$ or $$T=\{(i,j,k)\in [I]^3: A_i \cap A_j \cap A_k \not= \emptyset\}.$$ Then write the constraint as $$f_{i,j,k}(x) \le 0 \quad \text{for $(i,j,k)\in T$}$$


Top 50 recent answers are included