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

learn more… | top users | synonyms

4
votes
5answers
6k views

Why maximum/minimum of linear programming occurs at a vertex?

I'm in high-school and I'm told that the maximum/minimum of a linear programming occurs at the vertex.For more info see the chapter here. For convinience I'm putting relevant excerpt here: Now, we ...
0
votes
2answers
41 views

Line that passes between two vectors

I encountered the following in a text book I'm reading and I can't seem to understand why this is true (I'm translating this into English so excuse me if I'm not using the correct english terms): ...
1
vote
1answer
2k views

How to linearize a quadratic objective function with linear constraints?

I have an optimization problem that I'm working on. The objective is defined as follows: $Maximize: c_i\cdot w_i \cdot x_i - d_i \cdot y_i \cdot \delta_i $ subject to some linear constraints where $...
0
votes
1answer
42 views

Can there be a unique natural number vector solution to $Ax =b$ where $A$ is not a specific type of square matrix?

Let $A$ be $(n-1) \times n$ matrix that is of the following form: $$\left( \begin{array}{ccc} n-1 & 1 & 0 &.... & ....\\ 0 & n-2 & 2 & .... & ....\\ 0 & 0 & n-3 ...
2
votes
1answer
177 views

Prove vertices of a simplex are affinely independent

I'm given that the definition of a simplex $T$ is $x \in\mathbb R^n$ such that $x$ satisfies $n+1$ linear inequalities: $(u_k, x) \lt c_k$ for $k = 1,\ldots,n+1$ (i.e. $T$ is the intersection of $n+1$ ...
2
votes
1answer
102 views

Find the minimum value of C subject to the given constraints.

C=2x+5y Constraints: x+y>=2 2x-3y<=-6 3x-2y>=6 A-42 B-4 C-49 D-10 I encountered this question while doing the Systems of Linear Equations and Inequalities test at http://www.classzone.com/books/...
0
votes
1answer
43 views

The meaning of initial value in linear programming

I am new to LPP. I would like to know what is meant by setting an initial value(IV) to a variable. For example I was solving a problem where objective function(OF) is non-negative. When I give some IV ...
1
vote
0answers
70 views

Proving boundedness of a function .

Consider the function \begin{eqnarray} f(x_1,x_2,\cdots, x_n) = \frac{\sum_{i}^{n}a_ix_i}{\sum_{i}^{n}b_ix_i}, \end{eqnarray} over the set $S = \{x := (x_1,x_2,\cdots, x_n):-1 \leq x_i \leq 1,\; \...
0
votes
1answer
108 views

Proving boundedness of a function (part 1).

Consider the function \begin{eqnarray} f(x_1,x_2,\cdots, x_n) = \frac{\sum_{i}^{n}a_ix_i}{\sum_{i}^{n}b_ix_i}, \end{eqnarray} over the set $S = \{x := (x_1,x_2,\cdots, x_n):-1 \leq x_i \leq 1,\; \...
1
vote
0answers
141 views

Proof of Strong Duality via Farkas Lemma

I am trying to prove what is often titled the strong duality theorem. There is a hint in the book that I'm following, and I want to follow the method they have outlined for me. I will outline the ...
1
vote
2answers
43 views

How to introduce flat cost of flow over a node using mixed integer programming.

In the set up for the program we have a graph where we are trying to minimize the cost of sending flow over the arcs. I have formulated the following linear program. \begin{array}{ll} \text{minimize} ...
0
votes
1answer
54 views

Shortest point on a line segment from point outside the line

From the above pic I found the value $x$ from line $(p1,p2)$ and point a using $y=mx+b$ and imaginary red line which is perpendicular to black line having slope $-1/m$ and the intersecting point $x$. ...
1
vote
1answer
58 views

Above what order of magnitude a pure cutting-plane algorithm must be forgotten in favour of branch-and-cut?

Crawling the web on the subject of the cutting-plane algorithm, I have seen everywhere that a pure cutting-plane method cannot be used for numerical instability reasons after some iterations. But do ...
0
votes
1answer
329 views

How to transform a maximizing objective function which contains a max operator to a standard LP form

My Optimization objective function looks like this: $\max\quad(c_1 x_1 + c_2 \max\{x_2, x_3, x_4\})$ all variables, $x_i$ are binary variables. There are also some linear constraints such as $a_ix_1 ...
2
votes
1answer
75 views

Simple minimization problem

Suppose we want to execute a program on a processor which can run in three different modes. Each mode can be describe by a pair $(E,\tau)$ where $E$ denotes the energy consumption per cycle (in nJ) ...
2
votes
1answer
92 views

Can Gomory's cutting plane be used to solve Mixed Integer Linear Programs?

Do you know if Gomory's cut can be used to solve MILP problems ? I have read that Gomory's cut is useful when all variables are integer, but what if just some of them are integer ? Is is necessary ...
0
votes
1answer
42 views

Minimze min max (A*x)

has this example matrix A some special propertries, which might be useful? $$ \left[\begin{array}{rrrrrr} 3 & 0 & 0 & 0 & 2 & 0 & 0 & 0 \\ 4 & 3 & 0 & ...
1
vote
0answers
39 views

How to import matrix from sif document

I want to make some computation (with scilab, scipy or other) over the matrix A of linear problems (in inequational form). Those problems are in .sif format (from the netlib library in fact) and I don'...
0
votes
0answers
341 views

Using l1 magic toolbox for compressive sensing : Positive definite matricies.

I'm trying to use l1 magic to reconstruct an image from a single pixel camera I've developed. The test functions used are random binary patterns projected onto the object scene, so each pattern is ...
0
votes
1answer
38 views

Under-determined linear problem

To compute all solution of following under-determined linear problem in matrix form $ Ax = y $ we can use Pseudo inverse of A and the solution would be : $ x = A^{PI}y + [I - A^{PI}A]w $ I couldn't ...
0
votes
1answer
44 views

Linear Constraints Solution Existence

how can one decide if $$A*t\ge b$$ $A$ is a Matrix with integer Entries and $t$ is a Vector with integer Entries, $b$ is a fixed Vector with integer Entries exists?
2
votes
0answers
37 views

Finding optimal hyperplane

I have a set of vectors $\{V_i\}$ in $n$-dimensional space. There is a number corresponded to each vector $\alpha_i = f(V_i)$ ($\alpha_i$ can be negative). I want to find a hyperplane which would ...
0
votes
1answer
53 views

Pseudoinverse system of linear equation

$Ax = b$ describes a convex polyhedron, where $A$ is a real matrix and $b$ is a real vector. Now assume $A$ has less rows than columns. If you take a look here: http://en.wikipedia.org/wiki/...
0
votes
1answer
55 views

Simplying linear equation to get quartic in q using Maple and then using Descarte’s rule of sign

Using the maple I am trying to get quardic in q from this big linear equation. Then use Descarte’s rule of signs to determine the number of positive roots. \begin{equation} \frac{\gamma*q*P_Q}{k_p*(1-...
0
votes
1answer
1k views

Shortest path problem: dual formulation and proof of total unimodularity

The IP formulation of the shortest path problem looks as follows: \begin{align*} \min & \sum_{u,v \in A} c_{uv} x_{uv}\\ \text{s.t } & \sum_{v \in V^{+}(s)} x_{sv} - \sum_{v \in V^{-}(s)}x_{...
0
votes
2answers
601 views

Linear Programming Problem?

You are about to take a test that contains computation problems worth 6 points each and word problems worth 10 points each. You can do a computation problem in 2 minutes and a word problem in 4 ...
0
votes
2answers
46 views

LP: An algorithm to decide whether a polyhedron is a subst of another polyhedron

I've encountered the following question which I am unable to solve: $$ P = \{\vec x | A\vec x \geq \vec a\} \\ Q = \{\vec x | B\vec x \geq \vec b\}\\ P, Q \subseteq R^n $$ Find an algorithm to ...
0
votes
1answer
58 views

Almost linear programming problem

I have a problem that is almost the typical in linear programming, but not quite. All variables take real non-negative values. Certain simple linear inequalities and equalities should hold. But what ...
1
vote
0answers
43 views

Conic programming duality - relative interior

Consider the primal/dual conic programming problems $$ \newcommand{\ip}[1]{\left< #1 \right>} \newcommand{\myvec}[1]{\mathbf{#1}} \newcommand{\bvec}[0]{\mathbf{b}} \newcommand{\cvec}[0]{\mathbf{...
0
votes
1answer
144 views

Disjunction of conjunction in linear programming

I'm trying to get my model working with less variable/constraints possible. I want the binary variable $R$ to store the result of this Boolean expression: R = (a1 and b1) or (a2 and b2) or (a3 and b3)...
1
vote
0answers
184 views

The dual simplex algorithm

Following is the dual simplex algorithm, adapted from p. 283 of Daniel Solow's "Linear Programming, An Introduction to Finite Improvement Algorithms", Elsevier Science Publishing Co., Inc., 1984. I ...
2
votes
1answer
111 views

Does the Duality Theorem of Linear Programming hold only in closed convex cones

I've just read the the Duality Theorem of Linear Programming. Here is the proof from my book (and my questions after it): Duality Theorem of Linear Programming: If the primal or dual linear ...
2
votes
0answers
56 views

Rayleigh Quotient variant?

If $A$ is a covariance matrix and I want to get $\max X^TAX$ where each value of $x$ is between -1 and 1. Is there a closed-form solution for this? I understand when $X^TX = 1$ this becomes the ...
1
vote
2answers
144 views

Forbidden range for a linear programming variable

I would like to express a linear program having a variable that can only be greater or equal than a constant $c$ or equal to $0$. The range $]0; c[$ being unallowed. Do you know a way to express this ...
1
vote
2answers
84 views

linear programing : maximize $\sum \limits_{i=1}^{n} C_i$ where $C_i$ is circumference of circle with center at $\{x_i,y_i\}$

given n points on $\mathbb{R^2}$ $\{(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)\}$ formulate a linear program to maximize the sum of the circumference of all circles so any two circles won't intersect (two ...
0
votes
1answer
115 views

Linear programming alternate optimum solutions

**Q- The Optimum of a linear programming problem occurs at (1,2,3) and (-1,0,7) then the optimum also occurs at? a)(2,4,6) b)(0,3,5) c)(0,1,5) d)(3,2,1) e) None of the above. When we are given two ...
1
vote
0answers
67 views

Check feasibility of a system of integer linear equations

I'm currently working on a very large integer linear programme which cannot be solved within any reasonable time. The initial set of linear equations S={Ax<=b) is feasible. I want to add more ...
4
votes
1answer
2k views

Linearization of a product of two decision variables

I am trying to solve a problem that involves constraints in which products of two decision variables appear. So far, I read that such products can be reformulated to a difference of two quadratic ...
1
vote
1answer
43 views

Why $(1,\textbf{0}) \not\in \{(r,\textbf{w}): r=tz_0-\textbf{c}^T\textbf{x}, \textbf{w}=t\textbf{b}-\textbf{Ax}, \;\textbf{x}\geq\textbf{0}, t\geq0\}$

I'm learning about linear and nonlinear programming and on the chapter about duality I have the following statement and proof I can't understand: minimize $\textbf{c}^T\textbf{x}$ subject to ...
1
vote
1answer
124 views

linear inequalities using LP solutions not from simplex

I am trying to solve a set of inequalities using linear programming (LP) with objective function set as a constant. Usually this set of inequalities would have many solutions all of them in the ...
0
votes
1answer
20 views

What if objective function $Z$ is also in the constraints?

What if objective function $Z$ is in the constraints? To construct the dual form for this problem? how do I approach to this problem? Maximize $\;\;\;\;\;\;\; z$ subject to $$\;\;\;z - \...
1
vote
0answers
15 views

Symbol or name for Basismatrix of Linear Programming

This question is about the Basismatrix in the context of Linear Programming. Basically (haha!) we have the Matrix of the standard (or normal) form, which consists of (A|E) with the coefficient matrix ...
0
votes
1answer
285 views

Writing an unconstrained variable as an equality

I am working on some problems on the Simplex Algorithm for Linear Programming. In order to apply the simplex algorithm, the LP must be in standard form. If the constraint is an inequality with a $\leq$...
1
vote
1answer
92 views

Minimum distance of extreme points of polyhedra

Let $P = \{x \in \mathbb{R}_{\geq0}^n \colon Ax \leq b\}$ with $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R^m}$. Let $E \subseteq P$ be the extreme points of $P$. Can anything be said about ...
0
votes
0answers
32 views

Approximation of optimum for two linear programs

Suppose you got two linear programs. They are the same except that one has a shifted objective by a positive constant (1) $$\min c^Tx$$ (2) $$\min c^Tx + d$$ For (2) there exists a 10-...
3
votes
1answer
44 views

Trouble seeing why this is the dual of an LP

$A$ is an $m \times n$ matrix. Using the notation $x=(x_1, \ldots, x_n)$, $z=(z_1, \ldots, z_m)$, and $y=(y_1, \ldots, y_m)$, I'm reading that if the primal LP is $$ \min 0x_1 + 0x_2 + \cdots + 0x_n +...
0
votes
0answers
20 views

Perturbation factor terminology

This is a question about usage of English. I have an inequality $a^\textsf{T}x \leq b$, where $a$, $b$, and $x$ are vectors in $\mathbb{R}^n$. Now, I want to perturb this inequality by a small amount $...
2
votes
2answers
131 views

How can I calculate if a given point is wrapped inside a pentagon?

If I have a pentagon and I know the coordinates of it's nodes, how do I calculate if a point is wrapped inside it? An example to clarify what I mean: Assume that we know the coordinates of the ...
0
votes
0answers
133 views

Prove solution does not exist for inequalities system

I have an inequalities sytem like the following: Example > x+y+z <= A > x+y <= B > x+z > C > y+z > D > x >= E Let A,B,C,D,E be any ...
0
votes
1answer
69 views

Projection onto Polyeder

I know how to projects onto a linear subspace of $\mathbb R^3$, but how to project a point $x$ onto an polyhedron given as the intersection of three halfspaces $$ \langle y_1, x \rangle \ge c_1 \mbox{...