Questions tagged [linear-programming]
Questions on linear programming, the optimization of a linear function subject to linear constraints.
4,137
questions
2
votes
1answer
49 views
How to algebraically (without graphing) find coordinates delimiting the solution region of a system of linear inequalities?
I would like to know how to algebraically (without graphing) find coordinates delimiting the solution region of a system of linear inequalities. For example:
$$
\left\{
\begin{array}{c}
x\ge2 \\
y\...
1
vote
0answers
41 views
Edges Joining Adjacent Vertices
Theorem 3 (Edges joining adjacent vertices; Exercise 2.15, p. 78) Consider the polyhedron $P = \{x \in \mathbb{R}^n \mid a_i'x\geq b_i, i = 1, \dots, m\}$. Suppose that $u$ and $v$ are distinct basic ...
0
votes
0answers
31 views
Are complementary slackness conditions always *sufficient* to obtain the dual solution from an optimal primal solution?
Suppose that I have a guess for the optimal solution $x^\star$ of a linear program $P$. Let $D$ be the dual of $P$. One way to verify optimality of $x^\star$ is through complementary slackness ...
0
votes
1answer
17 views
Dualizing linear optimization problem with difficult indices in summation
I have a question about linear optimization in which I have a double summation and I can't find out how I can convert this to it's dual.
This is the problem$:\\$
Maximize $p$
Subject to:
$\sum_{i \in ...
0
votes
1answer
27 views
Dualizing linear optimization problem with double summation and dependent indices
I have a question about linear optimization in which I have a double summation and I can't find out how I can convert this to it's dual.
This is the problem:
\begin{align}
\min \quad & \sum_{l=1}^...
0
votes
2answers
26 views
If the polytope is unbounded then there is no optimal solution
Show if true or a counterexample if false
a) If the feasible polytope described by the solution space of a linear programming problem is unbounded then there is no optimal solution
b) If there are two ...
0
votes
0answers
12 views
Cyclic of Simplex Method
Show that for standard form linear optimization problem with $A\in\mathbb{R}^{m\times n}$ (you may assume that $A$ has full row rank) where $n-m=2$, the simplex method will not cycle, no matter which ...
4
votes
1answer
71 views
Does this matroid invariant have a name?
For a matroid $M$ on $X$ with closure operator $\tau:2^X\to 2^X$ let $c(M)=\min\{|S|:\tau(X\setminus S)\neq X\}$. This is an invariant because if $M$ and $M'$ are isomorphic (i.e. if flats of $M$ are ...
0
votes
1answer
19 views
1-norm reformulation for the following linear program
I have a linear program that I am trying to rewrite in a (possibly not) simpler form, most likely with a 1-norm constraint. The problem is quite simply
$\displaystyle\min_{x}{\sum_{i}{x_i}} \quad\text{...
0
votes
1answer
31 views
Is it possible for an inequality constraint to be active at all feasible region in linear programming?
Suppose we have an optimization problem
$\min f(x)$
s.t. $ c_1(x) \ge 0$
with one constraint only.
Is there a nonlinear constraint (specific example) that is active at all feasible points? what ...
0
votes
0answers
18 views
uniqueness of optimal value when all reduced costs are positive(minimization problem)
I want to prove that if all reduced costs of a basic feasible solution of a minimization problem( linear programming SEF format)are positive, then that Basic feasible solution is the unique optimizer ...
1
vote
1answer
39 views
I don't understand how I can solve the dual of a linear programming model knowing the solution to the primal.
If we know the optimal solution for a primal model how can I find the optimal solution for the dual of that primal model?
I heard about complementary slackness which to my understanding is that the ...
2
votes
1answer
33 views
Determine basic feasible solutions in LP
Consider a linear programming problem
\begin{align*}
\min_x \; &c^Tx\\
\text{s.t. } & Ax \leq b.
\end{align*}
Assuming the constraints form a polyhedron, is there any way we can group the ...
0
votes
2answers
34 views
Positve part and negative part of a real number
Let $a$ be a real number . The positive part of $a$, denoted by $a^+$ is given by expression
$$a^+ = \text{if } a\geq 0 \text{ then $a$ else } 0$$
The negative part of $a$, denoted by $a^-$ is given ...
0
votes
1answer
26 views
An otherwise linear matrix equation with the presence of a signum function : reference request
Consider the equation $$\pmb{c}+\text{sign}(G\pmb{c}) = L$$
$\pmb{c}$ is a $n\times1$ matrix.
$G$ is a $n\times n$ matrix which is also positive definite.
matrices $G$ and $c$ are real.
$L$ is a $n\...
1
vote
0answers
20 views
Solution space exists, but with introduction of objective function 'linprog' returns no solution
I am trying to solve the problem of the following form:
$\min \frac{1}{2} x'Hx + f'x$
subject to,
$Ax = b$, and $lb \leq x \leq ub$
I have utilized 'linprog' to check whether the set $Ax = b$, and $lb ...
2
votes
1answer
29 views
Basic optimization problem of n 1 degree variables
Let's say I have the function $f(x_1, x_2, x_3) = ax_1 + bx_2 + cx_3$ and the constraint that $x_1+x_2+x_3=1$ with every $x_1,x_2,x_3\geq0$. I want to find $\operatorname{argmax} f$. It is pretty ...
0
votes
0answers
29 views
LP formulation from simplex tableau
Consider the following simplex tableau for minimization problem:
\begin{matrix}z & x_1 & x_2 & x_3 & x_4 & x_5& \text{RHS}\\
1 & 0 & a & 0 & b & 0 &f\\...
1
vote
1answer
62 views
Solving the LP $\min\{c^Tx\; :\; Ax=b\}$
Let $A\in\Bbb{R}^{m\times n}$, with rank$(A)=m, b\in\Bbb{R}^m, c\in\Bbb{R}^n$. Solve the LP$$\min\{c^Tx\; :\; Ax=b\}$$ and determine when it is unbounded:
$\min\{c^Tx\; :\; Ax=b\}=\max\{-b^Ty\; :\; A^...
0
votes
1answer
37 views
Finding the optimal value of a linear program
Consider the LP$$\min c^Tx+b^Ty\\s.t.\;\ Ax\leq b\\\quad \quad A^Ty=-c\\\quad\; \quad y\; \geq 0$$Assume there is a feasible point. Show that there is a (optimal) solution with value $0$.
I am not ...
0
votes
0answers
42 views
Maximum flow problem: one arc always has full capacity in the maximum flow does this imply there is a minimal cut through this arc?
I have a maximum flow problem with directed graph G = (V, E) and edge capacities c : E ā Rā„0 and s, t ā V . Of course, there may be more than one flow f that gives the maximum flow value. But now I ...
0
votes
1answer
42 views
Linear programming formulation confusion
I have a silly confusion.
For this constraint here, $a_{i1,j1} + a_{i2,j2} ā¤ 1$ if $0 < |i1āi2|+|j1āj2| < d$.
I understand this constraint but I want to ensure that this encompasses all $i$ ...
1
vote
0answers
14 views
Choosing the index with the strictest constraint and solving the simplex algorithm
Could someone provide an intuitive explanation as to why we choose our pivot element in the simplex algorithm to be the element whose index $\frac {b_i}{a_{ik}}$ is smallest?
EDIT: $a_{ik}$ is the ...
0
votes
0answers
15 views
Are these linear programs the same?
Consider the programs
$$\forall\underline x\in\mathbb R^n$$
$$\exists a\in\mathbb R$$
$$A\underline x'\leq b\implies B[\underline x,a]'\leq c\wedge a>0$$
and
$$\forall\underline x\in\mathbb R^n$$
$$...
1
vote
1answer
36 views
Modeling problem (of Operational Research)
Consider a logistics system consisting of $n$ production sites and $m$ warehouses. For a given product, the monthly production capacity of the production sites is $p_i$ units, with $i = 1,\dots, n$. ...
0
votes
1answer
48 views
Solving a non-linear constrained linear function optimization
Given $k \in \mathbb{N}$, the $k$-vector-norm is defined as the sum of the $k$ largest entries of a vector (largest w.r.t. to absolute value). So if $k=1$, then the $k$-norm is actually the supremum ...
1
vote
1answer
31 views
Efficiently solving system of matrix equations
Suppose I have the two matrix equations:
$$A_1 M = C_1$$
$$A_2 M = C_2$$
where $A_1, A_2, C_1,C_2$ are given. I want to know if there is a matrix $M$ with entries in $\{0,1\}$ that satisfies the ...
2
votes
1answer
43 views
Polynomial time for a quadratic equation and linear inequalities?
Does anyone know how to find a feasible solution (or the infeasibility of any solution) in a polynomial time to the following problem:
\begin{align*}
xAx^t = 0, \\
Bx^t = c, \\
x_i \ge 0,
\end{align*}
...
0
votes
1answer
37 views
Showing that the linear program is unbounded
Let $A\in\Bbb{R}^{m\times n},\ b\in\Bbb{R}^m, c\in\Bbb{R}^n.$ Consider the linear program:$$\;\;\;\;\qquad \max c^Tx\\ \text{s.t.}\quad Ax\leq b$$Assume that there is a feasible $w$, with $c^Tw\gt 0$ ...
2
votes
2answers
39 views
Multiple variable optimization methods with constraints
This is something I'm doing for a video game so may see some nonsense in the examples I provide.
Here's the problem:
I want to get a specific amount minerals, to get this minerals I need to refine ore....
0
votes
0answers
20 views
Why we find out the initial feasible solution for transportation problem?
I saw several methods that available to obtain an initial basic feasible solution of a transportation problem.
...
1
vote
1answer
56 views
A question about implementation of Farkas lemma
The Farkas Lemma: Let $A$ be an $m\times n$ matrix, $b\in\mathcal{R}^m$. Then exactly one of the following two assertions is true:
(1) There exists an $x\in \mathcal{R}^n$ such that $Ax=b$ and $x\ge0$...
1
vote
1answer
39 views
Linear Programming Basic Solution. Could someone help?
so I am working through the proofs and reading the book "Linear and NonLinear Programming" by Luenberger and wanted to ask for some help. If someone could read the following extract and ...
0
votes
1answer
24 views
How can model this conditional constraint?
I have a known matrix, $S$ of size $N_U\times N_B$. For each row, the elements are sorted in ascending order.
I have also defined a binary variable $X$ of size $N_U\times N_B$.
I want to formulate a ...
0
votes
0answers
22 views
compute primal variables based on dual answer in linear programming
I have an optimization problem (primal problem) which is solved by the duality theorem. So I have constraints of the dual and its variable's value. it is worth mentioning the problem is linear. how ...
1
vote
0answers
38 views
Can the number of columns be less than the dimension?
I don't see how $k < m$ can possibly occur in part (b).
Imagine $X \in R^{n, k}$ describes a matrix for the vectors $x^1$ to $x^K$.
$m = \dim( span(S)) \leq \min(n,k)$
Then if $k < m$ in part (b)...
0
votes
0answers
30 views
understanding step in Simplex Algorithm
I am learning the Simplex Algorithm, and currently understand every step except one part. The relevant section from my notes are below. In the second step below, I am not sure why we need to pick $a_{...
0
votes
1answer
32 views
Regression/forecast with an added linear constraint
I am not sure if I am asking on the right place.
But given a set of independent variables $X_i$ and the dependent variable $Y_i = f(X_i, b) +c$, how can I estimate the regression equation given a set ...
0
votes
1answer
37 views
How to show that a system of linear equations is not solvable given certain constraints?
Imagine you have the following system of linear equations,
$$1 - 3x_1 - x_2 + x_3 + 3x_4 = 0$$
$$1 - x_1 - 5x_2 + 2x_3 + 4x_4 = 0$$
$$1 + x_1 + 2x_2 - x_3 - 2x_4 = 0$$
$$1 + 3x_1 + 4x_2 - 2x_3 - 5x_4 =...
1
vote
1answer
17 views
How to find the $(S ,T)$ for which the objective function $C$ will be maximized?
I have been given the following problem.
Maximize $C = S+T$ using duality
Subject to the $S + 3T \geq 8$ and $3S + T \geq 8 , S,T \geq 0.$
The duality of this problem is following.
Minimize $C' = 8S' ...
0
votes
1answer
43 views
Absolute value problem involving linear programming
John R. has up to $10,000 to invest. His wife suggests investing in two bonds, A and B. Bond A is rather risky with an annual yield of 10%, and bond B is more conservative with a yield of 7%. He ...
2
votes
2answers
76 views
Linear program to model given problem
Here is the problem I'm trying to solve:
"A company makes three products, named product A, product B and product C. The company has 4 available workers, and the workers have different rates as ...
1
vote
0answers
39 views
Problem: First determine whether Polyhedron is pointed. If it is find all extreme points of the Polyhedron.
The Polyhedron is defined by these inequalities
$x_1 + 2x_2 + 3x_3 \ge 1$
$āx_2 \ge 0$
$x_2 + x_3 \ge 0$
$āx_1 + x_3 \ge ā2$
First I want to say you can use the rank condition to determine weather it ...
1
vote
0answers
36 views
Geometric interpretation of linear programs with both inequality and equality constraints
I recently do a homework with linear programming, the standard form as:
$$\begin{array}{ll} \text{minimize} &\displaystyle \mathbf{c}^T\mathbf{x}+\mathbf{d}\\ \text{subject to} & \mathbf{A}\...
0
votes
1answer
43 views
Find all the solutions to the system of linear equations
I was given this system of linear equations
$x + 2y = 1$
$2x + 4y = 2$
I basically put the system into matrix form and transformed it into rref.
\begin{pmatrix} 1 & 2 & 1 \\ 2 & 4 & 2 \...
1
vote
0answers
21 views
Adding a variable to a LP: Does the reduced cost completely determine whether the optimal basis and optimal objective function value will change?
On page 203-204 of "Linear Optimization" by Bertsimas and Tsitsiklis, they discuss how introducing a new variable $x_{n+1}$ with corresponding objective function and constraint coefficients (...
0
votes
1answer
38 views
Reference request on how to get a linear optimisation problem from absolute value objective function
Consider the following optimisation problem
$$
\min_{\theta\in \mathbb{R}^K} \sum_{l=1}^L |r_l-c'\theta|\\
\text{s.t. } R\theta\leq q
$$
where :
$r\equiv (r_1,...,r_L)$ is an $L\times 1$ vector of ...
0
votes
0answers
21 views
Active constraints for unbounded Linear programming problem
I want to find which constraints are active for the LP problem under consideration. But the problem turns out to be unbounded.
Q. I wish to ask whether it is possible to find which constraints will ...
2
votes
2answers
150 views
Mid-range via minimax
Warning: crossposted at Statistics SE.
Given vector ${\rm a} \in \Bbb R^n$,
$$\begin{array}{ll} \displaystyle\arg\min_{x \in {\Bbb R}} & \left\| x {\Bbb 1}_n - {\rm a} \right\|_2^2\end{array} = \...
0
votes
0answers
46 views
Why are spans in Linear Algebra represented using free variables?
I have been doing some refresher work in Khan Academy for Linear Algebra and there was mention of how a column space or any other space can be represented as a fucntion of the free variables and not ...
