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

learn more… | top users | synonyms

0
votes
0answers
31 views

Finding the optimal solution to an ILP, when feasibility is not ultimately required

I have the following problem: I would like to solve an ILP with binary variables, i.e. I have a set of possible items, each having properties like "size" "weight" "value" "age" and so on, in total, ...
0
votes
0answers
20 views

Every polyhedron $P \ne \mathbb{K}^n$ equals an intersection of finitely many half spaces.

Currently, I am reading some lecture notes on linear optimisation. I cannot see why the following (seemingly trivial) proposition holds. (How could I understand/proove it?) Every polyhedron $P \ne ...
2
votes
1answer
26 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 ...
0
votes
1answer
33 views

Euclidean and rectilinear distance and nonlinearity

Can some one please explain why Euclidean distance and rectilinear distance make a problem nonlinear? Thanks
2
votes
1answer
40 views

Two forms of duality in linear programming

I do not know much about this subject, but I am trying to learn a little. In a book I have it says that a primal problem is: max $c'X$ subject to $AX \ge b$ $X \ge 0$ It says ...
0
votes
0answers
27 views

Converting nested IF's to ILP

I'm trying to convert a nested if structure into a linear programming problem. Here is a simplified example of what I'm trying to do- r1, r2 are binary s1, s2 are natural (I can give an upper bound ...
0
votes
1answer
60 views

Linear problem: maximizing net income

Problem: A company produces and sells two different products. The demand for each product is unlimited, but the company is constrained by cash avaliable and machine capacity. Each unit of the first ...
3
votes
1answer
210 views

Solving special boolean equation set

I have boolean equation sets that look like this (where ^ means xor): eq 1: x1^x3^x5^x6^x9^x10^x11^x13^x17^x18 = 0 eq 2: 1^x1^x3^x10^x12^x17 = 0 eq 3: 1^x2^x3^x5^x8^x10^x14^x16 = 0 ...
4
votes
5answers
635 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
36 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
125 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
30 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 ...
0
votes
0answers
33 views

Quadratic programming using Python

guys I'm trying to solve quadratic programming problem with constraints. I know how to solve simple quadratic problems using scipy.optimize like following: Define objective function as F = ...
1
vote
1answer
268 views

Business Linear Programming Question

Now I don't need you guys to do my homework for me; however, I am a little stumped Xara Stores in Canada imports the designer-inspired clothes it sells from suppliers in China and Brazil. Xara ...
-1
votes
1answer
136 views

Sum of two polyhedra is a polyhedron

I'm reviewing for a midterm next week in an optimization course. Currently, I'm having a great deal of trouble with a review problem. The problem is as follows: Let $P$ and $Q$ be polyhedra in ...
2
votes
1answer
57 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$ ...
0
votes
1answer
46 views

Shadow Price in Linear Programming - Finite Mathematics [closed]

Why is it true that if a slack variable is nonzero, then the shadow price of the associated constraint will be zero?
0
votes
1answer
22 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 ...
0
votes
0answers
37 views

Counting the Number of Combinations Conditionally

A bank issues 10 loans ranging from 1000 to 10000 dollars each and charges 5% interest on each loan. On average, the bank finds that 1 in 10 loan recipients defaults. If the loan that defaulted is ...
0
votes
1answer
33 views

Is the polar of the polar set the original set?

For each $Q \subset \Bbb R^n$, denote $Q^*:=\{z \in \Bbb R^n:z\cdot x \leq 1,\;\;\text{for all}\; x \in Q\}$. Let $P:=\{x \in \Bbb R^n: Ax \leq b\}$, for the matrix $A$ and the vector $b$. It is ...
1
vote
0answers
58 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
56 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
52 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
35 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
27 views

shortest point on a line segment from point out side 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. the ...
1
vote
3answers
489 views

Linear Programming to find the loan plan to minimize the interest payment

Assume that it is the first of July and you are running a small shop. The sales revenue and the amount of bills you have to pay for the next six months are estimated as following: In short, you ...
0
votes
1answer
30 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 ...
2
votes
1answer
33 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) ...
0
votes
1answer
56 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 ...
0
votes
0answers
16 views

Variable bounds of under-determined linear system

If I have a non-negative, under-determined linear system $\mathbf{Ax}=\mathbf{b}$ $\mathbf{x}\geq\mathbf{0}$ is there a fast way to compute the upper and lower bounds on values of each element of ...
1
vote
1answer
41 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
34 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 & ...
2
votes
4answers
230 views

Compressive sensing with non square matrices

I'm implementing the algorithm in the following paper: "Compressive sensing for wideband cognitive radios" http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=04218361 However I've run into a ...
1
vote
0answers
13 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 ...
0
votes
0answers
59 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
26 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
27 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
29 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 ...
1
vote
2answers
42 views

What is wrong with this linear program $\max z = 3x_1+2x_2$?

I solved a linear program. It is wrong. The answer is that $(x_1,x_2) = (50,75)$ and the maximum value is $300$, but instead I am getting $(x_1,x_2) = (50,100)$ and the maximum being $350$. Why is ...
0
votes
0answers
55 views

How to determine if a convex polytope is contained in a union of convex polytopes?

Given that we are in a Euclidean space of dimension d, that we have a bounded convex H-defined polytope P, and N possibly unbounded convex H-defined polytopes, I am looking for an "efficient" ...
0
votes
1answer
55 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 ...
0
votes
1answer
34 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: ...
0
votes
1answer
41 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} ...
0
votes
0answers
18 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}} ...
2
votes
1answer
150 views

Converting if else constraints into linear ones

I have the following two constraints: $$ x_1 \leq x_2 \leq x_3 \qquad \mbox{if } x_1 \leq x_3 \\ x_1 > x_2 > x_3 \qquad \mbox{otherwise} $$ Is there a way to get rid of the two conditions and ...
0
votes
2answers
26 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
0answers
36 views

Suppose I have the tableau below for a maximization problem. For the tableau to be optimal what are values for c1, c2, and b?

Suppose I have the tableau below for a maximization problem. For the tableau to be optimal what are values for c1, c2, and b? z x1 x2 x3 x4 x5 x6 RHS 1 c1 c2 0 0 0 0 10 ...
0
votes
2answers
159 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
1answer
39 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
2answers
77 views

Least Square Method for solving system of equations

So I am following this procedure through MathCad, but when I get to the bottom of page 3, he says I can use a built in command, which he doesn't include. So I am trying to figure out how to solve ...