Questions tagged [linear-programming]

Referring to optimization problems that consist only of linear constraints and a linear objective function.

Filter by
Sorted by
Tagged with
4
votes
1answer
97 views

Linear programming boundedness

Assume the optimal value of a primal problem is bounded. Is the following statement true? If the primal problem is bounded, then its dual problem is bounded as well.
8
votes
1answer
731 views

Linear system solution with inequality constraints - methods?

First of all, I hope I am posting this in the correct place. If not, I'm sorry and could you please direct me to where I should post this? Problem: You are given a set of vectors, $\{\mathbf{a}^i\}_{...
5
votes
2answers
2k views

LP feasibility checking

I have a linear programming problem. I want to know if this LP is feasible. What is the best known algorithm for checking feasibility of an LP or a linear system of equations?
6
votes
1answer
199 views

Symmetric matrix which satisfies conditions of the form $v_i^T X v_i = 0$

I want to solve an underdetermined system of linear equations $A x = b$ with $A \in \mathbb{R}^{n \times r^2}, x \in \mathbb{R}^{r^2}, b \in \mathbb{R}^n$. The matrix $A$ has the following additional ...
3
votes
2answers
188 views

polynomial time solvability

Consider the following optimization problem: $Min \qquad C^TX$ S.t.: $\qquad AX=0;$ $x_ix_j=x_kx_t$$\quad $for some $i\neq j\neq k\neq t$ $X=(x_1,x_2,...x_n)$ and $\quad x_j\geq 0\;\; j=1,2,......