Hot answers tagged

28

There sure is! It's called the SOB Method, originally proposed by A.T. Benjamin. In the SOB method, we classify each variable and each constraint as either sensible, odd, or bizarre (hence the name SOB). For "usual" models, we expect variables to be non-negative (for example, lengths, times, etc.). Sometimes, a variable might be unrestricted (maybe like $xy$...


22

KKT and duality are indeed closely related. To demonstrate this, I will look at a convex minimization problem in which all functions are convex and smooth. I will make use of Lagrange duality. Linear programming duality is just a special case of Lagrange duality applied to linear programs. Consider the following convex minimization problem \begin{align} p^* =...


17

The notions of dual bound and primal bound originate a bit more generally, I think. We typically call an (iterative optimization) algorithm primal when it maintains a feasible solution in every iteration. The Ford-Fulkerson algorithm for solving maximum flow is an example where we have a feasible flow in every iteration, or the simplex method, where we have ...


15

$\newcommand{\Rbar}{\overline{\mathbb{R}}}\newcommand{\R}{\mathbb{R}}\newcommand{\minimize}{\operatorname{Minimize}}$Another way to derive the dual for any convex problem is to use Fenchel duality. Fenchel duality Define $\Rbar=\R\cup \{+\infty\}$. A function $f:\R^n\to\Rbar$ is called proper if there is an $x\in\R^n$ such that $f(x) < \infty$. Given a ...


14

It is a difference whether one can dualize (or not) or that a duality theory holds (or not). Formally, you can formulate a dual of any integer program, e.g., by considering the linear relaxation, dualizing it, and then enforcing integrality again on the dual variables. It is already trickier which variables to consider as integer in the dual when you dualize ...


14

I have always, for some reason, had troubles remembering those rules. In the book by Bertsimas and Tsitsiklis there is even a nice little table showing the conversion from a primal to a dual in a nice compact fashion. But as stated, I am not good at remembering these rules. Thus, I always write up the Lagrangean and identify for what values of the dual ...


13

In Linear Programming (LP) one chooses a vector $\lambda \geq 0$ to obtain $\lambda^\top Ax \geq \lambda^\top b$ and whenever we find such a $\lambda \geq 0$ with $A^\top\lambda =c$ we obtain a lower bound $b^\top \lambda$ for our linear programming problem. In conic programming we also search for vectors $\lambda$ such that $\lambda^\top Ax \geq \lambda^Tb$...


12

I think there are two small mistakes in your formulation: In the final formulation, the roles of $x$ and $z$ should be reversed. Except for the first constraint and for the non-negativity of the variables, all signs should be reversed. The mistake probably occured when using duality to rewrite the expression $\max\limits_{(\alpha, \beta, \gamma, \delta) \...


12

TL;DR: column generation on the dual problem is 100% equivalent to cutting plane on the primal problem. Equivalence between primal and dual form Consider the (primal) LP problem \begin{align} (P) \ \ \ \min_{x \in \mathbb{R}^{n}} \ \ \ & c^{T}x\\ \text{s.t.} \ \ \ & \sum_{j=1}^{n} a_{i, j} x_{j} \geq b_{i}, & i = 1, ..., M, \end{...


9

Succinct and (freely) accessible references, which include general "theory". Also, solved examples,. for instance for Second Order Cones (SOCP) and Linear Semidefinite cones (LMI, i.e., Linear SDP): Chapter 8 "Duality in conic optimization" in "MOSEK Modeling Cookbook" . Section 5.9 "Generalized inequalities" in "Convex Optimization" by Boyd and ...


9

Here is a simple rule I use. Assume you are minimizing and $$ A x \leq b $$ So the dual value $(y)$ tells you how the objective value change if you increase b. Now if you increase b, then you relax the problem and the objective value most go down. Therefore, the dual variables must satisfies $$ y \leq 0. $$


9

For simplicity, I will replace $\sum_i \beta_{i,j}$, $ \sum_i f_{i,j}$, and $\alpha_j$ by $x$, $y$, and $z$, respectively. assume that $x$, $y$, and $z$ are defined to be non-negative. assume that $x$ has a coefficient $c$ in the objective, and $y$ has a coefficient $d$ in the objective. That is, we consider the following program, with the dual variables ...


8

I recommend having a look at the most recent developments around JuMP. They have developed two interesting packages this year: MathOptFormat.jl, that allows to import/export optimization problem in MPS, LP, CBF, etc... Dualization.jl, that allows to dualize automatically any optimization problem in conic form You can find here a Julia script that takes as ...


8

For each variable, you need to define a constraint in the dual problem and likewise, for each constraint in the primal problem, you will have a dual variable. \begin{align}\min&\quad\overline X\times D_1 + \overline Y \times D_2 + E\times D_3\\\text{s.t.}&\quad D_1+D_3 \ge a\\&\quad D_2-\beta D_3 \ge b\\&\quad D_3 = 0\\&\quad D_1 \ge 0\\&...


8

This may depend on how you define "reduced costs". If you mean reduced costs as computed by the simplex algorithm, then no, it is not possible that all are strictly positive due to the mechanics of the algorithm. If you mean $c^\prime - y^{*\prime}A$ for the original variables and $y^{*\prime} I$ for the surplus variables, where $y^*$ is any optimal dual ...


7

If strong duality holds, then it also holds when only a subset of the constraints is dualized. We define the following three problems: the original, the partially dualized, and the dual. Problem (P1): \begin{align}\min_x&\quad f(x)\\\text{s.t.}&\quad g_i(x)\leq 0, i \in C\end{align} Problem (P2): \begin{align}\max_{\lambda\ge0} \min_x&\quad f(x) +...


7

Can you elaborate a bit on what you mean when you say you are getting "Strange values"? One possible explanation is that if you call getDuals() on a model that includes some variables bounds other than $[0, +\infty)$, then your dual unbounded ray requires that you look at the reduced costs as well as the the dual variables returned by getDuals(). However, ...


6

In general, nonlinear optimization algorithms implemented in finite precision floating point software don't converge exactly to an optimal solution exactly satisfying the optimality conditions. Therefore, practical criteria are developed and implemented whereby the algorithm is terminated and optimality declared when the optimality conditions (or convergence)...


6

The link includes an online converter from primal to dual linear programs. The downside is you need to input all the coefficients and variables into the pre-defined form on the webpage.


6

It is common practice for MIP solvers to solve node LPs (other than at the root node) via dual simplex. I can't say with certainty that they terminate dual simplex prematurely if the objective value becomes inferior to the current incumbent, but I would think it likely. That does not address the question of stopping dual simplex early when the bound is ...


6

Yes, you can solve the dual and use that as a (weaker) bound than the optimal solution of the LP. This leads to the trade off between faster processing nodes vs processing more nodes. This approach is often exemplified in the choice between Lagrangean relaxation and Dantzig Wolfe decomposition. In its pure form you need to solve the DW to optimality in order ...


6

You should use the KKT conditions (turning the sign restrictions on $x$ into constraints), but it turns out they will not affect the results. First, let me point out that $\partial L/\partial x_1$ is undefined when $x_1=0$, so you need to deal with the case $x_1=0$ (and the case $x_2=0$) separately. Given the monotonicity of $L$, you can easily show that if $...


5

Use CVX's entr function. $\sum_{i=1}^ 4x_i\ln(x_i)$ can be entered as -sum(entr(x)) entr Scalar entropy. entr(X) returns an array of the same size as X with the unnormalized entropy function applied to each element: { -X.*LOG(X) if X > 0, entr(X) = { 0 if X == 0, { -Inf otherwise. If X ...


4

If I understand your question correctly, I think you can find your answer by considering the following two primal problems. The first is \begin{alignat*}{2} & \max & x_{1}\\ & \textrm{s.t.} & x_{1}+x_{2} & \le1\\ & & x_{1} & \le1\\ & & x & \ge0 \end{alignat*} and the second is \begin{alignat*}{2} & \max &...


4

I find the phrase "true shadow prices" misleading, and the use of "falsified" even more so, since the shadow prices any reputable solver returns are valid shadow prices ... possibly only in one direction, or even for a zero step size in either direction, when degeneracy occurs, but still correct. I can't say why it's "not a larger ...


4

The dual variables represent the marginal effect on the primal objective (total units purchased) per unit change in each primal constraint limit. So increasing (decreasing) the required amount $A_m$ of product $A$ by a small amount will reduce (increase) the total purchase quantity (TPQ to save me future typing) by $y_A$ times the change. The interpretation ...


4

If your sub-problem is a shortest path problem on a complete graph, without resource constraints, you can delete vertices which don't decrease the reduced cost. Indeed, for any path containing such a vertex, removing the vertex gives another path which is both feasible for the sub-problem and which corresponds to a master problem column with smaller reduced ...


3

Have not used CPLEX, but I've done that in Gurobi. In the latter, you just retrieve the equivalent of dualFarkas() when the primal version of the Benders subproblem you are solving is infeasible.


3

We can present the canonical format for minimization and maximization problems as follows: \begin{align} \min &\ cx\\ s.t.: &\ Ax\geq b\\ &\ x\geq 0 \end{align} and \begin{align} \max &\ wb\\ s.t.: &\ wA\leq c\\ &\ w\geq 0 \end{align} The second problem is dual of the first problem and vice versa. $Ax=b$ in the first problem ...


3

It does not look correct, and in particular the dual of an LP is an LP, so it makes no sense to have a binary variable in the dual. I suspect what led you astray was a misunderstanding of the penalty portion of the primal objective. You can rewrite the primal objective as \begin{gather*} \sum_{j=1}^{P}c_{j}x_{j}+P_{Dhd}\left[\sum_{i=1}^{F}\sum_{j=1}^{P}a_{ij}...


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