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

learn more… | top users | synonyms

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
816 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
185 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
340 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
660 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
515 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
130 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
597 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
299 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
894 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
347 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
274 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
275 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
833 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
447 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
190 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
91 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
93 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
837 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
459 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 ...
0
votes
1answer
19 views

why the optimized point always appear in the interception in LP problem

As the topics, why the optimized point always appear in the interception in LP problem? I think there should be a proof but i am not sure about it.
3
votes
0answers
67 views

relation between solution of a linear program and its perturbation

I have a linear program over a finite set of points $(x_1, x_2,\ldots, x_m)\in\mathbb{R}^n$: $$ \max_j c' x_j $$ Suppose the solution of this LP is obtained at a point $x_{j_1}$, which is a vertex ...
0
votes
1answer
149 views

Parametric Linear Program: Continuous Solution?

Consider the parametric linear problem $$ x^*(\theta) := \min_{Y , \ Z } \left\| Z \right\|_1 $$ $$ \text{sub. to: } \ \theta A + B Y = \theta C Z.$$ where $Y \in \mathbb{R}^{m \times s} $, $Z \in ...
1
vote
1answer
86 views

Proof required for an alternate method in solving a linear programming problem

Suppose that P and Q are two of the corner points of the feasible region lying completely in the first quadrant. In addition, P is located at South-East of Q*. z = 0 (or more specifically, Ax + By = ...
1
vote
0answers
19 views

Use Exact Non-linear formulation or a linear approximation?

I am writing a paper that discusses results to solve stochastic problems with recourse analytically. The problem is nonlinear. I can also write an approximate stochastic linear program to sove the ...
5
votes
1answer
446 views

Minimal set of inequalities

I have a set of $m$ linear inequalities in $R^n$, of the form $$ A x \leq b $$ These are automatically generated from the specification of my problem. Many of them could be removed because they are ...
1
vote
0answers
310 views

linear programming

Suppose you have won \$ 6000 from OK Grand challenge promotion and you want to invest is. Upon hearing the news , your two differnt friends Mukanya and Mhofu offer you each an opportunity to become a ...
0
votes
1answer
53 views

Can standard Linear Programming algorithms return all valid solutions without losing their efficiency?

I have a (generalized) Linear Programming problem to solve. I anticipate exactly two equally valid optimizations of my objective function. I would be happy if I could receive both these points; it ...
0
votes
2answers
685 views

Need Homework Help: A small corportion borrowed $500,000, some at 9%, 10% and 12%. Use a system of equations--how much was borrowed at each rate if…

A small software corporation borrowed 500,000 cash to expand its software line. The corporation borrowed some of the money at 9%, some at 10%, and some at 12%. Use a system of equations to determine ...
0
votes
1answer
360 views

Prove that an optimal solution $x^*$ of the problem 1 $\min f(x)$ s.t $x\in \mathbb{R}^n$ and..

Prove that an optimal solution $x^*$ of the problem 1 $\min f(x)$ s.t $x\in \mathbb{R}^n$ and an optimal solution $(\bar{x},\bar{z})$ of the problem 2 $\min z $ s.t $z\ge f(x)\,, x\in \mathbb{R}^n$ ...
2
votes
1answer
179 views

Maximizing a linear combination of certain integers

Consider some tuple $x = (x_1, ..., x_k) \in \mathbb{N}^k$ of $k$ non-negative integers such that $x_1 > x_1 > ... > x_k$ and suppose that $A \subset \mathbb{N}^k$ is such that there exists a ...
1
vote
3answers
476 views

Find a nonnegative basis of a matrix nullspace / kernel

I have a matrix $S$ and need to find a set of basis vectors $\{\mathbf{x_i}\}$ such that $S\mathbf{x_i}=0$ and $\mathbf{x_i} \ge \mathbf{0}$ (component-wise, i.e. $x_i^k \ge 0$). This problem comes ...
0
votes
1answer
409 views

LP: nonbasic solution made into basic solution, help me with this terminology

Related chat here, reading the Bertsimas book now on pages 50-51. By the way, I am gathering Linear-Programming -related studying material here, welcome to read a book and have coffee :) I cannot ...
2
votes
0answers
97 views

Linear Optimization Problem - Assign Objects to People

Say you have a 100x5 matrix of integers between -10 and 10, including zero. Each row represents an object; each column represents a person's ranking of the objects. Of the possible ranking values ...