Questions tagged [linear-programming]

Questions on linear programming, the optimization of a linear function subject to linear constraints.

3,304 questions
84 views

How to solve simplex problem with $x_1 + x_2 + x_3 + x_4 =1$ as restriction?

So, there's this problem: maximize $$6x_1 + 8x_2 + 5x_3 + 9x_4$$ subject to $$x_1+x_2+x_3+x_4 = 1 \;\text{ knowing that }\; x_1, x_2, x_3, x_4\geq0$$ The solution is obvious: since the sum of ...
42 views

Finding restrictions and convex hull by having a set of extreme points

Suppose we are given a set of extreme points. Is it possible to find out all possible restrictions of the Linear Programming problem by having those extreme points? Well, if we have a linear ...
81 views

Proof verification for simplex method problems

I was studying simplex method in LPP from "Introduction to Linear Optimization by Bertsimas and Tsitsiklis", and came across this problem: Consider the simplex method applied to a standard form ...
37 views

After Farkas Lemma, transforming $(A, -A)x = b$ into $Ax=b$

Let $A \in \mathbb R^{m\times n}$ and $c \in \mathbb R^{m}$ Show that either (i) $Ax=c$ has a solution or (ii) $c^{T}y=1$ with $A^{T}y = 0$ has a solution. My proof: Let (ii) be satisfied iff ...
37 views

Solving linear Programming problem with simplex method.

I have tried this question but can't come up with a maximization answer. I am not certain where I am wrong but I think my equations have an issue, you can't take look at them below the question. The ...
54 views

28 views

Dual of conic program

Let $A$ be an $m \times n$ matrix (over $\mathbb{R}$), $b \in \mathbb{R}^m$, $c \in \mathbb{R}^n$ and $K \subseteq \mathbb{R}^n$ is a closed, convex, pointed cone with non-empty interior. We define a ...
46 views

Strong Duality: If Dual is optimal then primal is optimal

Strong duality states that if the Primal has an optimal solution then the Dual has an optimal solution. Is the converse of this statement true? To me it would seem intuitive that it is, but I just ...
42 views

Can row/column penalty be zero in Vogel's Approximation Method?

If I have row with the following digits 10, 5, 12, 16, 5, 7 Will the row penalty be 5-5=0 or 7-5=2 In most books they ...
50 views

Correctness of integer reformulation in the FICO MIP quick reference

I have stumbled upon an industry quick reference for MIP formulation by FICO: However, after checking their writing on section 2.3 Maximum value. It seem that there are problems with their ...
30 views

What exactly is a basis matrix in LPP?

I'm studying simplex for solving a LPP. $A$ is a $m\times n$ matix. $$Ax=b$$Then the book says: Let $x$ be a basic feasible solution to the standard form problem. Let $$B(1), B(2),\cdots B(m)$$ ...
33 views

How can this linear problem be infeasible?

I have the following linear problem which is primal: I have converted this problem to its dual and tried to solve using the lpSolveAPI in R programming language. However, the ...
38 views

Iterative algorithm for a simple linear optimization problem

Let $c_1,\dots,c_n$ be $n$ positive numbers and so be $a_1,\dots, a_n$. For some $r$ such that $1\leq r\leq n$, consider the optimization problem \begin{align} \max_{x_i\in\mathbb{R}}&~~\sum_{i=1}^...
59 views

28 views

Solving a constrained linear system of equations

I want to solve the linear system of equations $$\begin{equation} Ax = b \\ \text{s.t} \quad x \geq 0 \end{equation}$$ The matrix A is a sparse symmetric matrix. What is the best time efficient ...
21 views

In linear programming, what does the primal problem imply about the sign of the dual variables?

In Bertsimas' Introduction to Linear Optimization, we define the primal problem in standard form as minimizing $c'x$ subject to $Ax=b$ and $x\geq0$, and the dual problem as maximizing $p'b$ subject to ...
37 views

How would Jack allocate his time to maximize his pleasure?

Jack is an aspiring freshmen at a university. He realizes that “all work and no play make Jack a dull boy.” As a result, Jack wants to apportion his available time of about $10$ hours a day between ...
43 views

How to quickly determine if a linear program is feasible?

I have a series of linear programs in canonical form $$\begin{array}{ll} \text{maximize} & c^T \mathrm x\\ \text{subject to} & A x \leq b\\ & x \geq 0\end{array}$$ and I need to ...
70 views

Open Travelling Salesman Problem

I am trying to find a linear program for the open Travelling Salesman Problem, where the salesman does not need to return to the starting point. More precisely, I have to do this with multiple ...
20 views

Inner and outer linearization

Why are Dantzig-Wolfe and Benders decomposition referred to as inner and outer linearization respectively? I am a newbie in Mathematical Programming and optimization and came across these terms while ...
32 views

49 views

Correct terminology for optimization problem

An optimization problem aims to minimize the sum of a variable u over a time-series. It is made of three variables that are in a linear relationship. Two binary variables $$x_1, x_2, \dots x_n$$ and ...
42 views

First step of simplex algorithm

I have the following linear program: Maximize $15x + 2y + z$ subject to $$x \le 10 \\ x + y \le 17 \\ 2x + 3 \le 25 \\ y + z \ge 11$$ I created the following Simplex Tableau: ...
I have the primal and dual problem (with slack/excess variables) Primal min $x_{1}+3x_{2}$ s.b. $x_{1}+w_{1}=3$ $x_{2}-w_{2}=2$ $x_{1}+2x_{2}-w_{3}=6$ $x_{1},x_{2},w_{1},w_{2},w_{3} \geq 0$ ...