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

learn more… | top users | synonyms

0
votes
0answers
3 views

Solving large system of Linear equations

I am trying to solve an optimization prob of the below form: $$ \min \sum_{k=0}^{n} p_k$$ subject to : $$0 \leq p_k \leq p_{\max}$$ $$ g_k p_k \leq I_t$$ $$g_k p_k - \eta_k \sum_{j \neq k} p_j ...
0
votes
0answers
17 views

Deduce LP maximization problem from sensitivity analysis

I have the answer to and the sensitivity analysis for a LP maximization problem. (See picture) http://postimg.org/image/xs4iowbrj/ How can I deduce the original LP problem? I have figured out this: ...
0
votes
1answer
17 views

How to find the point in convex set $C$ that is closest to $y\notin C$?

How to find the point in convex set $C$ that is closest to $y\notin C$? $C=\{ x\in \mathbb{R^2}:(x_1-1)^2+(x_2-1)^2\le1 \}$ and let $y\notin C $ but $y\notin \mathbb{R^2} $.
0
votes
2answers
16 views

Single nonzero value constraint formulation in linear programming problem statement

I'm trying to write a linear programming problem statement. Values of the solution vector have a bound constraint: $0 \leq x_i \leq 1$. Another constraint is that if we take a predefined subset of ...
1
vote
0answers
32 views

Can this be expressed in terms of linear constraints?

I'm attempting to find a matrix $X$ that minimizes some function $f(X)$ subject to the constraint that $$ X=W A Z $$ where $A$ is a given non-negative matrix with rows that sum to 1, and $W$ and $Z$ ...
0
votes
1answer
26 views

Use graphical methods to solve the linear programming problem. Maximize:

Use graphical methods to solve the linear programming problem. Maximize: $z= 4x+2y$ subject to : $x-y\le 7$ $19x+12y\le 228$ $18x+18y \le 324$ $x\ge 0,y\ge 0$ the max is ?? when x= ?? and ...
1
vote
0answers
9 views

best method for solving fully degenerate linear programs

I am looking for efficient computational methods for solving a class of linear programs whose right hand side is zero: $$ \min c^T x \qquad\text{ subject to }\qquad Ax\ge 0 $$ What is the best ...
0
votes
1answer
29 views

Shortest Path Length as mathematical function/expression

I have a graph (unweighted and undirected) of n vertices. My objective is to express the following constraints as inequalities. The degree of any node should be at least 3. The shortest path length ...
2
votes
0answers
18 views

Analytic Center of Convex Polytope

I have a convex polytope defined by $Ax \leq b$. I want to know how to find the "analytic center" of my convex polytope, because my goal is to sample from the polytope using Monte-Carlo Markov ...
3
votes
2answers
97 views

a vector inequality and combinatorics related question

This question is a similar restatement of this question which has been recently closed. Let $$A=\{\ (x,y,z)\in\mathbb{N}^3\ |\ 0\leq x,y,z\leq7\}$$ and $$B\subset A \text{ with } ...
-1
votes
0answers
33 views

unable to implement linear programming for min cut max flow problems [on hold]

iam trying to solve codechef problem using linear programming(simplex). https://www.codechef.com/problems/CHEFBOOK i understood the concept of linear programming , but i was unable to implement. I ...
0
votes
0answers
27 views

Fundamental Theorem of Linear Programming

I'm reading Dan Stefanica's book "A Linear Algebra Primer for Financial Engineering", which says in pp 92, $\S3.2$ that "...the Fundamental Thorem of Linear Programming, which, informally speacking, ...
0
votes
1answer
18 views

linear programming : Absolute value in constraint in mathematical model

I have a model have an constraint with evaluation of absolute value , a example can be: function objective : $\max \sum(x_i)$ statement: $x_i\geq |(y_i-t_i)|$ for all $i$ but value absolute ...
0
votes
2answers
29 views

Simplex algorithm with initial negative slack variables

I have the following LP problem: $$\begin{equation*} \begin{aligned} min. & & z = 2x+3y\\ \text{s.t. } & & x & \le 3\\ & & x & \ge 3\\ & & -x + 2y & \le ...
1
vote
1answer
198 views

What kind of a problem is this?

The problem can be stated as: I have $m$ liquids ($A_i$ is the amount of the $i$-th liquid) and $n$ tanks ($x_j$ is the volume of the $j$-th tank), and the task is to find the best way to ...
-1
votes
1answer
30 views

Linear equations problem [closed]

The Marshall County trash incinerator in Norton burns 10 tons of trash per hour and co-generates 6 kilowatts of electricity, while the Wiseburg incinerator burns 5 tons per hour and co-generates 4 ...
0
votes
0answers
11 views

How to Adequately Implement Phase I of Two-Phase Simplex Algorithm on a Computer with Floating Point Error

I'm currently trying to write some code that implements Phase I of the two-phase Simplex Algorithm described here: http://www.statslab.cam.ac.uk/~ff271/teaching/opt/notes/notes8.pdf In order to test ...
1
vote
1answer
38 views

Tutorial for Simplex Method with No Slack Variables

I found a nice tutorial here http://www.math.ucla.edu/~tom/LP.pdf for applying the Simplex Method to problems of the form: maximize $c^T x$ with the constraints $Ax\leq b$, $x_i \geq 0$. It suggests ...
0
votes
1answer
50 views

Edges of Hypercube

I may have some problem with this: Given a linear program $$\max{4x_1 + 2x_2 + x_3}$$ under the constraints $$ x_1 \le 5 $$ $$ 4x_1 + 1x_2 \le 25 $$ $$ 8x_1 + 4x_2 + 1x_3 \le 125 $$ $$x_1,x_2,x_3 ...
0
votes
1answer
33 views

how to check whether feasible solutions exist for linear programming

For a linear programming problem, how to decide whether there exists a feasible solution without solving it? For Ax<=B, is there any sufficient and/or necessary condition represented by A and B to ...
0
votes
1answer
31 views

Solution of linear inequality

I have the following system of linear inequality on $x_1, x_2, \dots, x_n$, $x_i \in \mathbb{R} \; \forall i$ $x_i - 2x_j < b \; \forall i, j$ The right hand side of the inequality ($b \in ...
3
votes
1answer
51 views

Different versions of theorem of the alternative?

I am looking for help to find necessary and sufficient conditions for a solution $x\in \mathbb{R}^n, x>0$ to exist to the following linear system: $Ax = b$ with where $A$ is $m\times n$ and ...
0
votes
0answers
37 views

How to find a formula for ratios?

I don't know if this is the correct section to post this, but here it goes. I recently got involved with hydroponics, and to feed the plants I've installed a system with a pump that delivers a ...
2
votes
1answer
38 views

How come $Ax\le b$ and $c^Tx\ge \alpha +\epsilon$ has NO nonnegative solution.

Let $\alpha=c^Tx^*$ be the optimum value of the standard form of (LP)(= max $c^Tx$ subject to $Ax\le b$ and $x\ge0$ in $\mathbf{R^n}$) Then we know: $Ax\le b$ and $c^Tx\ge \alpha$ has a nonnegative ...
0
votes
1answer
39 views

How do I determine the weight to assign to each bucket?

Someone will answer a series of questions and will mark each important (I), very important (V), or extremely important (E). I'll then match their answers with answers given by everyone else, compute ...
0
votes
2answers
40 views

Right coordinates of a slanting line when slope is zero and left coordinates never changed after transformation

I have a line in a program I am developing that I want to remove the slant (slope to zero) then get the new coordinates after transformation that removes the slope. This is how the line with the ...
1
vote
1answer
26 views

How to have just 3 result variables for this linear programming problem?

I have the following problem: +----------------------+--------------+--------------+----------+ | Process time (hours) | ...
1
vote
3answers
42 views

How to compute the projection of a polyhedron

Suppose that we have a polyhedron in $(x,y)$: $P=\{ (x,y) \mid A_1 x +A_2 y \leq b \}$ How can I find the polyhedron $P_x=\{ x \mid (x,y)\in P \}$? In other words, I would like to write $P_x=\{x ...
3
votes
2answers
60 views

In linear programming, how to check whether a convex polyhedron is contained in another

Suppose we have two convex polyhedra $P_1=\{x\in \mathbb{R}^n \mid A_1 x \geq b_1 \}$ and $P_2=\{x\in \mathbb{R}^n \mid A_2 x \geq b_2 \}$ Is there a way to check whether $P_1 \subseteq P_2$? I was ...
1
vote
1answer
20 views

Subgradient of the optimal value of a linear program with respect to its parameters

Consider the linear program $f(c)=\min\{c'x\mid x\in\mathbb{R}^n,Ax=b,x\geq0\}$. Are there any results on what is $\partial f/\partial b$?
0
votes
0answers
10 views

Bounded Knapsackproblem Formula DP

I knew how the binary Knapsack works with Dynamic Programming. But, now I am interested. How does the recursive formula look like if I allow n€{0,1,2} of the same item to be in the Knapsack? The only ...
1
vote
1answer
35 views

How to pivot to an adjacent vertex in simplex method

In the simplex method, we need to move from one vertex of the polyhedron to an adjacent one. Suppose the polyhedron is $P=\{x\in\mathbb{R}^n\mid Ax=b,x\geq0\}$ with rank$A=m<n$. For a ...
1
vote
0answers
20 views

Is $K =\{ S: \exists \text{ positive diagonal} D, D^TSD \;\text{diagonally dominant}\}$ convex?

I am doing some convex cone optimization and wonder whether the following set $K_1$ is convex or not. Assume the following matrices are all in $\mathbb{R}^{n\times n}$ and symmetric. Let the set of ...
0
votes
0answers
7 views

Gomory's cut typical running time until the constraint is fractional

I was considering the following problem. Say we are given an linear programming problem $$ \max c^Tx $$ $$ Ax \le b $$ $$ x \ge 0$$ Where instead I consider $i^{th}$ the optimal solution $X_i$ of ...
0
votes
1answer
55 views

Proof for the existence of basic feasible solution

I am trying to understand a proof for If F is non empty, the it has a BFS, where F = {x belongs to R: Ax=b, x>=0}, The proof goes likes this, first we collect all the indices(j) where xj > 0, then ...
1
vote
0answers
149 views

Linear programming: constraints that depend on sign

Edit: following a comment, more detail and context, and removed lengthy confusing remains of previous edits I basically want to check whether there is a sequence $y_1,\dots, y_n \in (-\infty,0]$ that ...
0
votes
0answers
14 views

Is there any non-linear optimization technique whose running time depends on the diameter of the underlying polytope(induced by constraints)

It is well known that the running time of the simplex algorithm depends on the diameter of the polytope induced by the constraints. Is there any non-linear optimization technique that also has this ...
1
vote
1answer
30 views

The optimal function value in linear programming has analytic solution

Consider the following linear programming problem: $\min c'x$ subject to $Ax=b$ and $x\geq0$, where $A$ is $m\times n$ with rank$A=m$. The dual is $\max -b'v$ subject to $A'v+c=\lambda$ and ...
1
vote
0answers
22 views

Strong duality in conic programmig

Let $K$ be a convex cone which is not closed. The look at a probem of the from $$\min <C,X>, \,s.t\; <A_i,X>=b_i,\, X\in C.$$ Now suppose I now that both this program and its dual have a ...
0
votes
0answers
17 views

Find $U \subset D $ with $|U|$ minimal s.t $v = (1/2,1/2,1/2)$ belongs to the convex hull of $U$.

Consider the convex hull $\text {conv} \{e_1,e_2,e_3,(1,1/2,1/2),(1/2,1,1/2), (1/2,1/2,1)\}$ in $\mathbb R^3$ and the vector $v = (1/2,1/2,1/2)$. I want to compute $U \subset ...
1
vote
1answer
32 views

What is Weyl-Minkowski theorem?

The book I am reading 'Quantum Probability and Logic by I Pitowsky' has the following lines in the introductory chapter : Under the second description, a vector is an element of the polytope if ...
1
vote
1answer
47 views

smoothing linear graph but keep the spikes

how can I smooth a linear graph, but keep the spikes ? the graph are speed points per second, so it goes up and down frequently (like sinus curve), but sometimes there are spikes, like the speed ...
1
vote
0answers
19 views

Max-flow-min-cut using LP duality

https://www.cs.oberlin.edu/~asharp/cs365/papers/Approximation-ch12.pdf is a chapter from Vazirani that discusses max cut-min flow using LP duality. The binary min-cut problem is: \begin{align} ...
0
votes
1answer
26 views

How do I show that the set $S$ in $\mathbb R^3$ defined by linear inequalities is a $3$-simplex?

Consider the set $S$ in $\mathbb R^3$ defined by the inequalities: $x+y+z \ge 1$ $-x+y+z \le 1$ $x-y+z \le 1$ $x+y-z \le 1$ How can I show that $S$ is a $3$-simplex ? (Convex hull of $3 + 1$ ...
0
votes
0answers
19 views

Guaranteed solution to linear programming problem.

I have formulated a linear programming problem on the form \begin{align} &\min\limits_{x_1,\cdots,x_p}\sum\limits_{i=1}^p x_i \\ &\text{st. } \begin{split} Ax &= b \\ ...
0
votes
1answer
43 views

How to linearize this constraint a summation of a product of a integer with a binary

I have to linearize the following constraint, $$ \sum_{i \in V_C} \sum_{j \in V} \sum_{k \in K} y_{ik} \cdot x_{ijk\ell} \leq I_\ell \qquad \forall \ell \in V_D $$ where $y$ is a integer variable ...
1
vote
1answer
36 views

Check if feasible region is zero

Say I have a system of linear equalities and inequalities with integer coefficients in $n$ variables, and let $R^n$ be the space of all possible solutions. I know that $\vec{0}$ is a solution. Is ...
2
votes
0answers
44 views

Solve constrained system of linear equations from samples of a reference function

I have a system of $2n$ linear equations in $2n$ unknowns represented by the standard matrix equation: $$Ax = b$$ Where the solution vector $x = (p_1, ..., p_n, q_1, ..., q_n)$ represents real ...
0
votes
0answers
37 views

How to decide if solution exists for a linear equation?

I have $p$ ( $P_1,P_2...P_p$ ) positions and $n$ ( $N_1,N_2...N_n$ ) options to fill each position. Thus I have $n^p$ $p$ length strings. Each of these strings has a variable corresponding to them ...
0
votes
1answer
23 views

Understanding graphical meaning of tangent line in optimization problem

In a trivial optimization problem where dependent variable $y(x_b)$ is a curve, I'm seeking the value of $x_b$ that minimizes $\frac{y(x_b)}{x_b-x_a}$,where constant $x_a>0$. The solution has been ...