52

Here's perhaps a better way to think of the shadow price. (I don't like the word "relax" here; I think it's confusing.) For maximization problems like this one the constraints can often be thought of as restrictions on the amount of resources available, and the objective can be thought of as profit. Then the shadow price associated with a particular ...


17

Maybe it's worthwhile to talk through where the dual comes from. This will take a while, but hopefully the dual won't seem so mysterious when we're done. Suppose we want to use the primal's constraints as a way to find an upper bound on the optimal value of the primal. If we multiply the first constraint by $9$, the second constraint by $1$, and add them ...


16

You can introduce new variables $t_i$ and constraints $t_i \geq a_i x + b_i y - c_i$ and $t_i \geq -(a_i x + b_i y - c_i)$, and then minimize $\sum_i t_i$ subject to the new constraints and your additional constraints.


15

Suppose your feasible region looks as shown below : Lets assume we're maximizing the objective function $C=ax+by$ Notice that, for different values of C, you get different straight lines of varying y intercepts but they will have same slope : Only the lines that cut through the feasible region satisfy all the given constraints because you can cookup x,y ...


14

There are two aspects of this. If you use the simplex method or some variant of it, you are actually simultaneously solving the primal and dual. That is, from an optimal simplex tableau you can read off both an optimal solution to the primal and an optimal solution to the dual. From an optimal solution of either primal or dual, complementary slackness ...


12

In two dimensional case the linear optimization (linear programming) is specified as follows: Find the values $(x, y)$ such that the goal function $$g(x, y) = a x + b y \;\;\; (Eq. 1)$$ is maximized (or minimized) subject to the linear inequalities $$a_1 x + b_1 y + c_1 \ge 0 \;\; (or \le 0) $$ $$a_2 x + b_2 y + c_2 \ge 0 \;\; (or \le 0) $$ $$ ... $$ Each ...


11

Here are some uses of the dual problem. Understanding the dual problem leads to specialized algorithms for some important classes of linear programming problems. Examples include the transportation simplex method, the Hungarian algorithm for the assignment problem, and the network simplex method. Even column generation relies partly on duality. The dual ...


11

A few Linear Programming solvers: GLPK (GNU Linear Programming Kit) is written in C. Take a look at this intro. GLPK can also do Integer Programming, I believe. CVXOPT is a Python library for convex optimization. In addition to LP, it allows you to solve quadratic and semidefinite programs, as well. Gurobi: you can download a free trial.


11

Commercial solvers like Gurobi analyze the structure of a problem and decide whether the problem is best suited for solving in primal or dual form. As a general rule, users should not worry about this. In fact, it can often be counterproductive for a user to attempt to coax the problem into a particular standard form---for example, by splitting free ...


10

In general strict inequalities are not treated in linear programming problems, since the solution is not guaranteed to exist on corner points. Consider the $1$-variable LPP: $Max$ $x$ subject to $x<3$. Now there does not exist any value of $x$ for which maximum is achieved and which lies in the feasible region.


10

I think the question you are trying to ask is this: If we have a set of linear constraints involving a variable $x$, how can we introduce $|x|$ (the absolute value of $x$) into the objective function? Here is the trick. Add a constraint of the form $$t_1 - t_2 = x$$ where $t_i \ge 0$. The Simplex Algorithm will set $t_1 = x$ and $t_2 = 0$ if $x \ge 0$; ...


9

Some basic linear algebra is essential for this. Have you already studied that a bit? Say you have point $p$ inside your polyhedron of feasible points inside $\mathbb{R}^n$, and let's say you want to maximize the objective function. The objective function is linear, given by some $c \in \mathbb{R}^n$. If $v \in \mathbb{R}^n$ and $c \cdot v = 0$, then $p+v$ ...


9

This can not be formulated as a linear programming problem. We need extra binary variables and end up with a MIP. First we do: $$ a > b \Longleftrightarrow \delta = 1$$ This can be formulated as: $$\begin{align} &a \ge b + 0.001 - M(1-\delta)\\ &a \le b + M\delta\\ &\delta \in \{0,1\} \end{align}$$ (in practice I would drop the $0....


8

Jiri's answer gives the intuitive explanation. Formally, the fact that an optimal solution lies at an extreme point is a consequence of the representation theorem for polyhedra and the fact that the feasible region of a linear program is a polyhedron. The representation theorem says that a polyhedron is the convex sum of its vertices plus the nonnegative ...


8

Let $A=\left(\begin{smallmatrix} -1&0\\0&1\end{smallmatrix}\right)$, $b=\left(\begin{smallmatrix}1\\1\end{smallmatrix}\right)=-c$. $Ax\ge b$ and $A^Ty\le c$ cannot both be satisfied with positive $x,y$.


7

I recommend Introduction to Linear Optimization by Dimitris Bertsimas and John N. Tsitsiklis. The authors are professors at MIT.


7

If $X_1,\ldots,X_n$ are inedependent uniform$(0,1)$ random variables, then $$ {\rm P}(X_1+ \cdots +X_n \leq a) = {\rm volume}(A), $$ where $$ A = \{ (x_1 , \ldots ,x_n ) \in (0,1)^n :x_1 + \cdots + x_n < a\} . $$ For the probability density function of the sum $X_1+ \cdots +X_n$, see this answer. EDIT: When $0 < a \leq 1$, it holds $$ {\rm ...


7

(Most of this was written before the recent addendum. It addresses the OP's original question, not the addendum.) (a) Suppose we have distinct bases $B_1$ and $B_2$ that each yield the same basic solution ${\bf x}$. Now, suppose (we're looking for a contradiction) that ${\bf x}$ is nondegenerate; i.e., every one of the $m$ variables in ${\bf x}$ is ...


7

One way to make this work is to change the underlying representation. Instead of your basic variables being $x_i$ and $y_i$, use binary indicator variables to indicate which of $\{1,2,3,4\}$ is assigned to $x_i$. For instance, with four variables $b_{i1}, b_{i2}, b_{i3}, b_{i4}$, if we constrain each $0 \le b_{ij} \le 1$ as well as $b_{i1} + b_{i2} + b_{i3}...


7

In general, if the primal problem is too difficult to solve (i.e. put into standard form and use the Simplex method), then likely it is easier to solve the dual problem. If you have to add a lot of artificial variables for solving the primal, then you are probably better off writing the dual of the LP and solving it using the Dual Simplex method. Keep in ...


7

This is really a comment on littlO's answer. Comment box is too small for this. $$ \min (|a1 x + b1 y - c1| + |a2 x + b2 y - c2| + |a3 x + b3 y - c3|), x+y = 1$$ is equivalent to $$ \min t_1 + t_2 + t_3 \text{ such that} \\ a_1 x + b_1 y -c_1 \le t_1 \\ a_1 x + b_1 y -c_1 \ge -t_1 \\ a_2 x + b_2 y -c_2 \le t_2\\ a_2 x + b_2 y -c_2 \ge -t_2 \\ a_3 x + b_3 y ...


7

Greg Glockner showed how to linearize the following example: $$ \min\left\{\min\{x_1,x_2,x_3\}\right\} $$ For the sake of clarity, I will explain how he achieves this. He introduces a variable $z=\min\{x_1,x_2,x_3\}$ and binary variables $y_1,y_2,y_3$ to deactivate extra (big-$M$) constraints : $$ z\ge x_1-My_1\\ z\ge x_2-My_2\\ z\ge x_3-My_3\\ y_1+y_2+y_3=...


7

If the problem is described with rational data, there is always a rational optimal solution. I don't have any reference immediately, but it is a standard result. Search on rational data linear program, polynomial complexity etc, and you will find a lot of material. Edit: I see my answer was a bit unclear. If the solution to the rational LP is unique, it is ...


6

I believe you can view the connectedness requirement like a maximum flow problem. Introduce a new "supersource" node and a "supersink" node. Denote your candidate for a connected subgraph by $S$. Create an arc connecting the supersource to one of the nodes $x$ in $S$. Create an arc from each node in $S$ to the supersink; each of these arcs should have ...


6

(I feel like I'm taking one for the team here. :) ) Starting with your main questions at the end... There are two ways to convert to a maximization problem. One is to change the objective to maximizing $-\phi = -2700x -2400y - 2100z$. This is because the $(x,y,z)$ triple that minimizes $\phi(x,y,z)$ will maximize $-\phi(x,y,z)$. Another is to form the ...


6

Your problem is known as Linear Programming (if you change positive to non-negative). Usually linear programming is thought of as an optimization problem, but in fact the optimization problem is equivalent to feasibility, which is exactly what you're asking: whether a system of inequalities has any solution. If you really want to ask whether there's a ...


6

As you say, a feasible solution for the ILP is a feasible solution for the LP. So if the LP has an optimal solution with objective value $\alpha$, this implies there is no feasible solution for the LP with objective value $< \alpha$, and in particular no feasible solution for the ILP with objective value $<\alpha$. That's what it means for $\alpha$ ...


6

Mathematical optimization is used all over the place. The first example that comes to my mind (just because some papers are lying next to my desk) is controller design for cyberphysical systems. Other examples include all kinds of management things in economy, planning of infrastructure (e.g., location of transport hubs), some areas of software design (e.g., ...


6

I have seen both the $\min$ and $\max$ forms of an LP frequently, it seems to be an author preference sort of thing. The only difference is a minus sign in the objective ($-c^Tx$ instead of $c^Tx$). Regarding the constraints, I have more often seen the first form (your Bertsimas reference) referred to as standard or canonical. The two forms are equivalent ...


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