# Tag Info

32

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

23

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^* =...

22

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

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

15


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

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{... 10 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 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 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 ... 9 This is called Lagrangian relaxation, no matter what subset of constraints you choose to dualize. 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 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 ... 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 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 ... 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 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)... 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 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$...

6

If you interpret $$A= \begin{pmatrix}G \\ H\end{pmatrix}$$ then $$\pi^TA_j = \mu^T G_j + \lambda^T H_j$$ (where $\pi,\mu,\lambda$ are the corresponding duals) is not a surprise.

5

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

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

5

First, as a note, your formulation (minimizing with $\le$ constraints) will produce nonpositive shadow prices. It might be easier to understand if you use $\ge$ constraints (nonnegative shadow prices). For clarity, I'll assume we are maximizing profit with $\le$ constraints, which results in nonnegative shadow prices. Each shadow price represents the ...

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

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

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