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

learn more… | top users | synonyms

8
votes
5answers
5k views

Good software for linear/integer programming

I never did any linear/integer programming so I am wondering the following two things What are some efficient free linear programming solvers? What are some efficient commercial linear programming ...
0
votes
1answer
296 views

Interpolation of sin/cos

I am trying to optimize sin/cos for my MCU in order to calculate geo distance. This part of formula particularly is using trigonometry: ...
2
votes
1answer
177 views

Convert problem to linear programming task

I have function $\max \{ |x-1| + 2|y-1| | x,y \in R, x+y \leq 2 \}$. Can this problem be converted to LP? I think it cant because of the abs. value in criterial function, but Im not sure. If it can, ...
1
vote
1answer
85 views

Are these linear programming constraints correct?

The problem is: Beth works a maximum of $20$ hours/week programming computers and tutoring math. She receives $\$25$/hour for programming and $\$20$/hour for tutoring. She works between $3$ and $8$ ...
1
vote
1answer
358 views

Directly from primal to dual when primal not in standard form

This is a simple problem, but after spending some hours with linear programs in the primal and its dual form, I still can't do it quite intuitively for LPs which are not in the standard form. I know, ...
1
vote
1answer
82 views

Correlated Equilibrium - Transforming a non-linear objective function into a linear one

I am trying to transform a non-linear objective function into a linear one, in order to create a LP. How might I go about to do this (I have never taken a course in linear programming). I have that I ...
4
votes
5answers
688 views

Find a convex combination of scalars given a point within them.

I've been banging my head on this one all day! I'm going to do my best to explain the problem, but bear with me. Given a set of numbers $S = \{X_1, X_2, \dots, X_n\}$ and a scalar $T$, where it is ...
1
vote
0answers
50 views

Duality gap in cone programming

Let $K\subset \mathbb{R}^2$ be a closed convex and pointed cone, $A$ be a $2\times 2$ square matrix and $b, c\in \mathbb{R}^2$. Consider the problem $$ (P)\quad \min\{\langle c, x\rangle: Ax\geq_K ...
1
vote
0answers
24 views

Sufficiency of the condition for this linear programming problem to have solutions.

I'm looking for $x_1,x_2,x_3$ which satisfy the following constraints: $$ \begin{align*} &x_1,x_2,x_3\geq 0\\ &x_1+x_2\geq a\\ &x_2+x_3\geq b\\ &x_3+x_1\geq c\\ &x_1+x_2+x_3=1 ...
2
votes
3answers
142 views

Dual of a Linear Program

\begin{align} \min_{x} c^Tx \\ s.t.~Ax=b \end{align} Note that here $x$ is unrestricted. I need to prove that the dual of this program is given by \begin{align} \max_{\lambda} \lambda^Tb \\ ...
1
vote
1answer
183 views

How does the two phase method for linear programs work…

I understand that by adding artificial variables the problem can be reformulated as a new problem where the "starting point" is readily found. What I don't get is how when this extended problem is ...
3
votes
1answer
437 views

Generating random linear programming problems

I've just finished writing a a linear programming problem solver which uses the simplex method. Now I would like to start optimizing my solver but before I can do this, I need a way of reliably ...
2
votes
1answer
49 views

Why can't the hyperplane H intersected with polyhedral set S contain any line…

S is the polyhedral set $ S = \{ \mathbf{x} \in \mathbb{R}^{n} ; \mathbf{Ax}=\mathbf{b}, \mathbf{x} \ge \mathbf{0} \} $ and $ H : \mathbf{c}^{T}\mathbf{x} = \beta $ with $ \min_S ( ...
1
vote
1answer
155 views

Linear programming - task formulation

I have a question concerning the formulation of a linear programmign task. I am trying fo find $x^* \in argmax_{x \in R^n}\{ a_1x_1 + a_2x_2, a_2x_2 + a_3x_3 + a_4x_a, a_4x_4 + a_5x_5 \}$, subject to ...
7
votes
2answers
2k views

What are the advantages of dual of a problem

I am studying linear programming and I came across primal-dual algorithm in Linear Programming. I understood it but I am unable ...
3
votes
4answers
842 views

Finding the minimal cost edge cover for a bipartite graph

I have got two sets of elements and a pruned graph of bipartite edges with weights assigned to each edge. I need to find the minimal set of edged with the minimum cost covering all nodes from both ...
2
votes
0answers
188 views

Determine if a polyhedron is a polytope

Note, a polyhedron is the intersection of finitely many half spaces in $\mathbb{R}^n$ and a polytope is a bounded polyhedron. Let $M$ be an $m \times n$ matrix of integers. Let $P$ be the (possibly ...
0
votes
2answers
342 views

Convex function from Hessian

Am I correct to say that the following function is convex? $$\begin{align} & f(x,y)=-\sqrt{xy} \\ & x>0,y>0 \\ \end{align}$$ After computing the Hessian: $$ Hf =\left[ \begin ...
1
vote
2answers
672 views

Removing linear redundant constraints using Gauss Elimination

I have a set of linear constraints in the form of $c_i x \ge d_i$ and I need to identify if an additional constraint is redundant with respect of the previously mentioned set. Here I found a similar ...
4
votes
1answer
521 views

Duality. Is this the correct Dual to this Primal L.P.?

Given a problem: Find the dual: $$ Primal =\begin{Bmatrix} max \ \ \ \ 5x_1 - 6x_2 \\ s.t. \ \ \ \ 2x_1 -x_2 = 1\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x_1 +3x_2 \leq9\\ ...
2
votes
1answer
131 views

Critical Points. Find and classify.

Given $g(x,y)=y^2 - x^3$ find the critical points and classify them $$\nabla g(x,y) = \begin{pmatrix} -3x^2 \\ 2y \\ \end{pmatrix}$$ So, $\implies -3x^2=0,2y=0$ ...
0
votes
1answer
1k views

Linear Programming question- optimal solution

A film producer is seeking actors and investors for his new movie. There are n available actors; actor i charges $s_i$ dollars. For funding, there are m available investors. Investor j will provide ...
1
vote
1answer
79 views

Question on Linear Algebra

NOTE: I tried hard and came up with a lose proof, I have posted it as a answer. Do comment/correct if you can. Let $$P=\{x|Ax\geq b\}, A\in \mathbb{R}^{m\times n}$$ $$Q=\{y|Gy\geq h\},G\in ...
3
votes
3answers
241 views

0-1 knapsack like - the set of all non-contained affordable binary selections

This is my first question here, so please go easy on me :) The following problem is – I think - similar to the 0-1 knapsack problem. It's simplified somehow in that each item has only a cost ...
1
vote
0answers
46 views

Linear programming, Maximise Z

Maximise $Z = X_1 -2X_2$ Such that $3X_1 + X_2 \ge 3$ $2X_1 - X_2 \le 5$ $X_1, X_2 \ge 0$ I've done using CET. Find out that $\max(Z)=-6$ when $X_1=0$, $X_2=3$ which is feasible. But i really ...
0
votes
1answer
602 views

Linear Programming question

I am kind of lost on this problem and would like it if I can get help on this. Matching Pennies. In this simple two player game, the players (call them R and C) each choose an outcome, heads or ...
3
votes
1answer
304 views

Dimension of solution space for system of linear inequalities

Let's say I have a system of inequalities: $Ax \leq g$ for some $A \in \mathbb{R}^{4\times4}$, $x \in \mathbb{R}^4$, $g \in \mathbb{R}^4$, and $A$ is full rank. Here, the $\leq$ denotes element-wise ...
6
votes
0answers
897 views

Farkas Lemma proof

I am trying to prove the Farkas Lemma using the Fourier-Motzkin elimination algorithm. From Wikipedia: Let A be an $m \times n$ matrix and $b$ an $m$-dimensional vector. Then, exactly one of the ...
2
votes
1answer
8k views

What is the standard form of a linear programming (LP) problem?

According to Bertsimas' text, the standard form of a LP problem is: According to Vanderbei's text, the standard form of a LP problem is: So, what is the standard form of a linear programming ...
1
vote
1answer
353 views

MATLAB LP formulation of investment problem (in Bertsimas' lecture notes)

I wish to write MATLAB codes to solve the following linear programming problem found in Bertsimas' lecture notes: My attempt was as follows (sequence of variables for f' is A, B, C, D, E, Cash1, ...
0
votes
1answer
35 views

intuitive explanation of sparsity / references

I know it is a vague question, but I am confused by why/when we actually want sparsity of a matrix. For example, interior-point methods work better when constraint matrix is sparse. Similarly, it is ...
1
vote
1answer
279 views

Linear combination question in Linear Programming Problem

I have two constraints in a linear programming model: x1 + x2 <= 5 x1 >= 2 Note that there are no nonnegativity constraints so the problem is unbounded from below. The point (2,3) is the only ...
1
vote
2answers
282 views

How can I infer a result using primal feasibility, dual feasibility, and complementary slackness?

I am trying to find the minimum of $-x_1$ with restrictions $\bar g\leq\bar 0$ so that $$\bar g=\begin{pmatrix} (x_1+2)^2+(x_2-4)^2-20\\ (x_1+2)^2+x_2^2-20\\ -x_1\end{pmatrix}\leq ...
0
votes
1answer
67 views

Solving equation of the form $Axb^Tx = y$

I have a square, invertible $n\times n$ matrix $A$, and column vectors $b$ and $y$. I'd like to find a column vector $x$ such that $Axb^Tx=y$. I suspect there's some way to get it into a QP form, but ...
0
votes
1answer
138 views

Are these solutions to a LP problem feasible? basic?

Consider the following LP: \begin{align*} \max 8x_1 + 14x_2 + 12x_3 + 50x_4\\ \text{s. t. } x_1 + 2x_2 + 2x_3 + 16x_4 &\le 8\\ 2x_1 + 3x_2 + 4x_3 + 5x_4 &\le 15\\ 5x_1 + 6x_2 + 8x_3 + 10x_4 ...
-1
votes
1answer
111 views

Finding an $O(n \log n)$ time algorithm for an optimization problem

Consider the following optimization problem: Let $n$ be even and let $c$ be a positive vector in $\mathbb{R}^n$. Find $$\min\left\{c^T x : (x \geq 0) \text{ and } \left(\forall S \subseteq [n], \ ...
1
vote
0answers
39 views

using the ellipsoid algorithm to find a poly time algorithm for the optimization problem

Consider the following optimization problem: Let $n$ be even and let $c, x$ be positive vectors in $\mathbb{R}^n.$ Find $\min(c^Tx)$ for $\sum_S x_i\geq 1,$ for any $S\subset \{1,...,n\}$ with $|S| ...
2
votes
1answer
847 views

Linear programming / linear optimization video lectures?

Is there a good set of linear programming / linear optimization video lectures somewhere? I found "Linear programming and Extensions" by Prof. Prabha Sharma, Department of Mathematics and ...
0
votes
3answers
2k views

Linear Programming Problem Using the Two-Phase Method

I have been given the following LP problem and asked to use the two phase simplex method to solve it. I believe there isn't a solution, but would anyone be able to confirm this for me? Thanks. max ...
1
vote
1answer
1k views

Linear programming: basic solutions?

http://www.math.toronto.edu/kergin/236_t1_2.pdf For number 3(a), I don't get how "any of the last 4 columns are linearly dependent" and how x1 is the basic variable... I thought only the last 2 ...
2
votes
0answers
448 views

Reconstructing an optimal Simplex tableau from an optimal solution

I have here a bounded LP with infinite optimal solutions: ...
2
votes
1answer
3k views

What does basic solution mean?

Linear programming: basic solution? If the matrix consists of $$\begin{bmatrix}1&-2&0&0&0\\-3&6&1&3&0\\0&0&2&6&-1\end{bmatrix},$$ how is it that there ...
0
votes
1answer
66 views

Inequalities with matrices

For a linear system of equations constrained by inequalities, is $ Ax \le b => y^TAx \le y^Tb $ acceptable? Or does that not generally hold. ($ y^T $ being the transpose of $y$).
2
votes
0answers
192 views

intuitive explanation of Primal-Dual algorithms

I've recently heard of Primal-Dual algorithms and I was wondering if someone could give me an intuitive explanation of it. I searched online, but did not find an intuitive explanation. I'd be glad if ...
1
vote
2answers
94 views

What's the relation between the non-convex sets and the hardness of ILP problems?

If some or all of the unknown variables are required to be integers, then the problem is called an integer programming (IP) or integer linear programming (ILP) problem. If understand ...
1
vote
1answer
1k views

A question about the operation research and simplex method

For the simplex method, we need to add slack variables. My question is how to determine how many slack variables should be considered in the LP problem? I don't quite get why in the cases to find out ...
1
vote
1answer
97 views

Simple LP - simplex problem

I have a LP with constricting constraints, i.e. there is no feasible region. How would I use the simplex method to show this? After one iteration of the simplex method I have found no negative values ...
0
votes
2answers
109 views

When does $\max x+y $ subject to $ax+by \le 1$, $x,y\ge 0$ have a unique optimal solution?

From reading online I found someone said that it has a unique optimal solution when $a$ and $b$ are positive and $a \neq b$. Could someone explain why this is the case? I know that if $a = b$ then ...
1
vote
1answer
844 views

Example of a quadratic programming problem with no optimal solution on vertices?

Is there a way to write a quadratic programming problem with two variables bounded, nonempty feasible region linear constraints and yet have none of the vertices of the region optimize the ...
2
votes
1answer
465 views

Developing Constraints for a linear programming based problem

Recently, I thought of developing a mathematical approach to a task I commonly do every week. Simply enough, it's a schedule. That said, I have a few questions regarding the process. I haven't ...