New answers tagged


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 ...


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


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-...


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 ...


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