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

learn more… | top users | synonyms

0
votes
1answer
69 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 ...
4
votes
5answers
1k 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
37 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
205 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
42 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 = ...
2
votes
1answer
65 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
31 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
53 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
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
24 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
59 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
62 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
69 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
36 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
1answer
34 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
79 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
35 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
0answers
17 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 ...
2
votes
1answer
54 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 & ...
1
vote
0answers
17 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
74 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
27 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
31 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
0answers
60 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
35 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
46 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
1answer
68 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
0answers
54 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
218 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
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
1answer
42 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 ...
0
votes
0answers
20 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}} ...
0
votes
1answer
45 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 ...
0
votes
0answers
33 views

Justification for discarding constraints in Fourier Motzkin elimination

In the Fourier Motzkin elimination method, constraints are separated into three categories: 1) Constraints with positive coefficients for the dimension to be projected out. 2) Constraints with ...
0
votes
0answers
78 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
50 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
30 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
81 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 ...
0
votes
0answers
27 views

How is stochastic optimization accomplished by GAMS solvers?

I'm looking for a quick description of how stochastic optimization is done by numerical solvers. It was explained to me that for a stochastic programming problem, GAMS 1. simulated draws from each ...
1
vote
2answers
55 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
46 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
32 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 ...
2
votes
1answer
268 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
36 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
33 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
0answers
30 views

Proving equivalence between basic feasible solution and vertex

I stumbled upon this proof of the Bertimas book on Linear optimization and I don't see what the "key ingredient" is that makes it work. Baxic feasible solution $\implies$Vertex Let $x^*$ be a ...