Questions on linear programming, the optimization of a linear function subject to linear constraints.
5
votes
1answer
226 views
What is graph theory interpretation of this linear programming problem?
So, I am looking at a paper by Rosenfeld, "On a problem of C.E. Shannon in graph theory", where he gives necessary and sufficient conditions for a graph $H$ to satisfy
$$\alpha(G \boxtimes H) = ...
1
vote
1answer
31 views
Is this linear programming problem right?
The problem is: Beth works a maximum of 20 hours/week programming computers and tutoring math. She receives 25 dollars/hour for programming and 20 dollars/hour for tutoring. She works between 3 and 8 ...
2
votes
1answer
161 views
A variation of the Assignment Problem
In the following Wikipedia article about the Assignment Problem in the Example section, it says:
Similar tricks can be played in order to allow more tasks than agents, tasks to which multiple ...
0
votes
0answers
51 views
Will the objective function change the constraints/graph?
So I'm referring you to this question on linear programming, in which I asked about my constraints. My objective function, is 25x + 20y = maximum income, so will that change the constraints/graph of ...
1
vote
1answer
85 views
Linearizing min function Problem
How can I linearize $\min(x_1,x_2,x_3)$ in a maximization linear programming problem? Please help me. I've tried many things but I didn't solve.. My LP equations are as follows:
Objective function ...
1
vote
1answer
37 views
Linear programming: expressing the fact that precisely $k$ variables are nonzero
Given some variables $x_1,\ldots,x_n$ is it possible to somehow express in a linear program the fact that precisely $k$ of them are non-zero?
I suspect this would already be enough to simulate ...
1
vote
1answer
53 views
Is this use of the simplex method correct?
I am trying to implement a simplex algorithm for solving LP task. I will post the question and my solution as well - what I need to know is whether my solution is correct, thanks in advance!
...
4
votes
4answers
245 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
86 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:
...
1
vote
1answer
81 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
44 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
81 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
39 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 ...
0
votes
0answers
27 views
If a number can play the same as a vector in LP
I have a simple linear program as below:
$min L(x)=\sum_i w_i x_i$
subject to
EDIT:
$a\leq f(x_i) \leq b$
where $w_i$ are constants and known calculated by $w_i=(v1_i).*(v2_i)\ \forall i$, where ...
4
votes
5answers
142 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 ...
0
votes
0answers
54 views
closed form of a linear program
I have a linear program:
$\min. L(b_{ij})=\sum_i\sum_j w_{ij} b_{ij}$
subject to
$\ 2 \leq \sum_j b_{ij} \leq 3 \ \ \ \forall i$
$ \sum_i b_{ij} = 1 \ \ \ \forall j$
$0\leq b_{ij}\leq1$
...
1
vote
0answers
36 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
16 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
79 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
63 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
89 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
40 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
88 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 ...
2
votes
2answers
181 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
235 views
Finding minimal cost edge cover for a bipartie graph
I have got two sets of elements and a pruned graph of bipartie 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
53 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
165 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 ...
0
votes
0answers
144 views
Linear Programming-minimize cost
Exeter Mines produces iron ore at four different mines; however, the ores extracted at each mine are different in their iron content. Mine 1 produces magnetite ore, which has 70% iron content; mine 2 ...
0
votes
0answers
62 views
Proving that a nonlinear system has a unique solution
Let $x^*$, $y^*$, $w^*$ and $z^*$ be initial values for $x, y, w$ and $z$. Let $t$ be a parameter between $0$ and $1$. $X, Y, W,$ and $Z$ are diagonal matrices of the vectors $x, y, w,$ and $z$. ...
1
vote
2answers
126 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 ...
3
votes
1answer
196 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
86 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
313 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
65 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
187 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
31 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
0answers
27 views
Dual program- linear programming [duplicate]
Possible Duplicate:
Dual of max-flow
I have a hard time understanding dual of max flow problems. Can experienced thinkers solve the problems below and possibly give reasoning? Thank you.
...
0
votes
0answers
150 views
Dual of max-flow
I have a hard time understanding dual of max flow problems. Can experienced thinkers solve the problems below and possibly give reasoning? Thank you.
$$S\rightarrow A\quad 1$$
$$S\rightarrow B ...
0
votes
1answer
199 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
119 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
1answer
385 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 ...
0
votes
0answers
16 views
how to get the quantile regression estimator
how to get the quantile regression estimator? in some references mentioned to get estimator with the simplex method, but I was still hard to learn. can help?
0
votes
0answers
29 views
Road lighting LP formulation
Bertsimas & Tsitsiklis text Introduction to Linear Optimization, p. 35, Exercise 1.8:
My attempt:
Let $c$ be the cost per unit power for a road lamp, a possible linear programming formulation ...
1
vote
1answer
709 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
146 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
24 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
102 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
133 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
47 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
61 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 ...
