Tagged Questions

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

learn more… | top users | synonyms

3
votes
1answer
118 views

Solving ill posed linear equations

Given a set of linear equations $AX=B$, say $A$ is an ill posed matrix (has a few singular values equal or very close to zero), which numerical algorithm (conjugate gradient, least squares or steepest ...
1
vote
2answers
408 views

Invertability of submatrix?

If I have a matrix $A \in R^{(m \times n)}$ with $m \leq n$. All rows in matrix a are linearly independent and therefore $A$ has a full row rank. I can decompose matrix $A$ such that $A = [B|N]$ with ...
2
votes
2answers
228 views

Simplified nurse scheduling problem

I'm currently handling a project with a problem that is very similar to nurse scheduling problem in many respects. It is a part time workforce scheduling system whereby we need to determine which ...
1
vote
1answer
69 views

Vizualisation about line search in Linear Programming?

I am trying to visualize this recursive algorithm in LP, Wikipedia here. I am looking for references about in which kind of problems is this used and what does it really look like? I am also ...
3
votes
1answer
246 views

Steps in the Simplex Method

I'm trying to look at how the Simplex method in standard form works. I understand the basics of how ti works, but I can't understand what happens between two steps. I'm using the example from chapter ...
1
vote
1answer
279 views

“Base is degenerate IFF its corresponding basis matrix is singular”: degenerate with solution and degenerate without solution?

Statement "Base is degenerate IFF its corresponding basis matrix is singular" is wrong according to my Linear-programming teacher Mat-2.3140 in Aalto University (translated from Finnish here/here) ...
1
vote
0answers
272 views

Linear programming: writing a problem with artificial variables?

Use artificial variables to write a linear programming problem in canonical form with non-negative resource vector whose solution will determine whether there exists (and if so, find) non-negative ...
3
votes
0answers
50 views

finding the largest $p$ components of $x$

Given an $n \times n$ matrix $A$, and an $n \times 1$ vector $b$, the conventional way of computing an $n \times 1$ vector $x$ such that $x=Ax+b$ is to use the following iterations: ...
6
votes
1answer
341 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
71 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
309 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 ...
2
votes
1answer
373 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
87 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
102 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! ...
7
votes
5answers
3k 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
246 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
165 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
76 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
244 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
70 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
29 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
530 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
227 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
47 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
122 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
148 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
304 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
47 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
140 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 ...
4
votes
2answers
1k 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
540 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
159 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
286 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
492 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
399 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
121 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
74 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
224 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
42 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
386 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
233 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
763 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
5k 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
270 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
31 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
199 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
216 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
64 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 ...