Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
4
votes
0answers
870 views

Book recommendation on Applied Integer Programming/Combinatorial Optimization/OR

Having some very basic and theoretical knowledge about these topics from my study, I'm looking for a book (or other good sources) that explains the stuff from a practical point of view. On the one ...
4
votes
0answers
776 views

Real-time linear programming

I'm going to implement in C a light-weight embedded LP solver for a production system. I need to be able to sequentially solve a series of (possibly unrelated) linear programs with ~6-60 variables and ...
4
votes
2answers
174 views

L1 minimization problem with nested sums as LP problem

I've been trying to solve this problem but I have an issue with the fact that there is a sum under each absolute value. I'm trying to convert this minimization problem (with respect to $x, y_1, \dots,...
3
votes
3answers
3k views

Maximize system of linear equations

Suppose you have the system $$ \begin{bmatrix} 4 & 3\\ 1 & 7\\ 5 & 9\\ 2 & 4\\ \end{bmatrix} \begin{bmatrix} x\\y\end{bmatrix}=\begin{bmatrix}b_1\\b_2\\b_3\\b_4\end{bmatrix} $$ How ...
3
votes
2answers
936 views

How to calculate volume given by inequalities?

I need to find the volume of the 3d space that is given by the following conditions: \begin{array}{c} 0 < x_1 < 1\\ 0 < x_2 < 1\\ 0 < x_3 < 1\\ x_1 + x_2 + x_3 < a. \end{array}...
3
votes
2answers
8k views

Can a non-degenerate LP have multiple optimal solutions?

In linear programming, an LP can have multiple optimal solutions if it contains degenerate vertices, i.e. where one of the base-variables is 0. Can an LP also have multiple optimal solutions if it ...
3
votes
3answers
6k views

Binary integer variables in linear programming

Could someone please explain the concept of switch variables (binary integer decision variables) in linear programming? This example has two alternative constraints $$\begin{array}{ll} \text{...
3
votes
3answers
251 views

Convert the non linear problem into standard minimization linear programming form

I have to convert the non linear problem into standard minimization linear programming form Minimize: $|x|+|y|+|v|$ Subject to: $$x+y\le1$$ $$2x+v=3$$ I dont have any idea how can I do it...I would ...
3
votes
2answers
1k views

About convex hull and closed sets

Let S be a closed set. Show with an example that $conv(S)$ is not necessarily closed. Also show that if S is compact then $conv(S)$ is always closed. Here $conv(S)$ denotes the hull of S. Proof: (...
3
votes
2answers
241 views

References for Linear Algebra needed for Differential Equations and Linear Programming

I am in need of learning the Linear Algebraic theory behind the following Applied disciplines. Could someone please recommend Linear Algebra books for: Differential Equations: Specifically learning ...
3
votes
2answers
46 views

If $F_0\cap G_0=\emptyset$ then $x$ is a local minimum of function

Consider the theorem: Consider the following linear optimization problem $$\max 2x_1+3x_2$$ $$\text{s.t.} x_1+x_2\le8\\ -x_1+2x_2\le4\\ x_1,x_2\ge0$$ a) For each extreme point verify if ...
3
votes
2answers
903 views

How to find the direction in linear optimization?

$$\max z=-x_1+3x_2 $$ $$\text{s.t.} -x_1+x_2\leq 2 $$ $$ -x_1+2x_2 \leq 6 $$ $$ x_1,x_2\geq 0 $$ Is there any way to find extreme points and directions/extreme directions of problems like this ...
3
votes
2answers
149 views

What programing language Thomas Hales used in 1998 to prove Kepler’s conjecture?

Mathematicians have been studying sphere packings since at least 1611, when Johannes Kepler conjectured that the densest way to pack together equal-sized spheres in space is the familiar pyramidal ...
3
votes
2answers
3k views

Linear programming simplex - can I have a constraint with a multiplication?

I'm not sure of this, can I have a constraint like this in a linear programming problem to be solved with simplex algorithm? $$n_1t_1 + n_2t_2 > 200$$ where $n_1$ and $t_1$, $n_2$ and $t_2$ are ...
3
votes
2answers
6k views

Nash Equilibrium for the prisoners dilemma when using mixed strategies

Consider the following game matrix $$ \begin{array}{l|c|c} & \textbf{S} & \textbf{G} \\ \hline \textbf{S} & (-2,-2) & (-6, -1) \\ \hline \textbf{G} & (-1,-6) &...
3
votes
1answer
943 views

Pivoting and Simplex Algorithm

I would like to understand exactly how the pivoting works geometrically in Simplex algorithm. What is meant geometrically by moving a vector into BFS and moving out one. Also, what is the geometrical ...
3
votes
2answers
226 views

Need help defining a Quadratic Programming problem

I have an optimization problem which should be solvable with Quadratic Programming: There are $n$ multiplication coefficients $c_i$ for which optimized values are searched. The coefficients are ...
3
votes
1answer
1k views

why maximizing the L1 norm of a vector can not be formed as a linear programming problem

I am new to optimization, and one of the examples the professor gave in class was that we cannot form $\max \lvert\lvert x \rvert\rvert$ subject to $Ax=b$ as a linear programming problem. The reason ...
3
votes
2answers
427 views

Online view of a polyhedron defined by linear inequalities

I am studying the simplex algorithm which finds an optimal solution for a minimization or a maximization of a set of linear inequalities. I know that such a set of inequalities defines a polyhedron. ...
3
votes
1answer
155 views

Can I know all the elements of a matrix given that I know its sum along one dimension and the fact that it is axisymmetric?

For this discussion I will assume a 9x9 matrix but my question is for a general nxn matrix. I have a matrix which is not only symmetric along the vertical and the horizontal axis, but is axisymmetric ...
3
votes
1answer
1k views

A linear program for maximizing a fraction

Given $\lambda_1,\ldots,\lambda_n \geq 0$ and an $n\times n$ matrix $A$, I wish to maximize the ratio $$ \frac{\lambda_1x_1 + \cdots + \lambda_nx_n}{x_1+\cdots+x_n}, $$ where $x_1,\ldots,x_n \geq 0$ ...
3
votes
2answers
206 views

Terminology: Linear 'programming'

What is the origin of the term 'programming' in 'linear programming'? It is not obvious to me why this should be called a type of programming.
3
votes
1answer
683 views

What is the computational complexity of linear programming?

What is the computational complexity of solving a linear program with $m$ constraints in $n$ variables?
3
votes
1answer
1k views

Guaranteed Winning Strategy on Horse Betting Odds

Suppose four horses - $A, B, C$, and $D$ - are entered in a race and the odds on them, respectively, are $5$ to $1$, $4$ to $1$, $3$ to $1$, and $2$ to $1.$ If you bet $\$1$ on $A$, then you receive $\...
3
votes
1answer
56 views

Clarification about Simplex Algorithm concepts

We have the following generic program: $max \;\; c^Tx$ $\quad \quad Ax \le b$ $\quad \quad x \ge 0$ where $x$ is the vector of variables $(x_1, x_2,..., x_n)$. Suppose the origin is feasible. ...
3
votes
1answer
55 views

Is this a typo on my book?

See (6.74). I believe this is a type as I got this constraint to be $$ \pi_1 + \pi_3 = -1 $$
3
votes
2answers
212 views

How to solve the following optimization problem?

I want to know the solution (the values that maximizes the objective function) of the following optimization problem. The objective function is as follows $$f(\mathbf{x})=a_1x_1+a_2x_2+a_3x_3+\cdots ...
3
votes
2answers
5k views

Linear programming: minimizing absolute values and formulate in LP

Look for $x$ that minimizes $\sum_i| x – a_i|$ with numbers $a_1,\ldots, a_N$ that are given and formulate this as a LP. I have searched online and found that first of all this $\sum_i| x – a_i|$ ...
3
votes
2answers
65 views

A line intersecting segments

There are n parallel segments on a plane, for any three of them, there exist a line crossing all three of them, how to prove there exist a line crossing all n segments? Thank you very much.
3
votes
1answer
136 views

Permutohedron: Wikipedia vs. Günter Matthias Ziegler

The Wikipedia site on permutohedra displays a drawing of a 3-permutohedron in which vertices $\begin{pmatrix}2\\1\\3\end{pmatrix}$ and $\begin{pmatrix}3\\1\\2\end{pmatrix}$ are connected by an edge: ...
3
votes
1answer
692 views

Simplex method - identity matrix

I want to solve the following linear programming problem: $$\min (5y_1-10y_2+7y_3-3y_4) \\ y_1+y_2+7y_3+2y_4=3 \\ -2y_1-y_2+3y_3+3y_4=2 \\ 2y_1+2y_2+8y_3+y_4=4 \\ y_i \geq 0, i \in \{ 1, \dots, 4 \}$$...
3
votes
1answer
3k 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\le B$, is there any sufficient and/or necessary condition represented by A and B ...
3
votes
1answer
2k views

Degeneracy in Simplex Algorithm

According to my understanding, Degeneracy in a linear optimization problem, occurs when the same extreme point of a bounded feasible region $X$ can be represented by more than one basis, that is not ...
3
votes
1answer
4k views

Prove optimal solution to dual is not unique if optimal solution to the primal is degenerate and unique.

How do I prove an optimal solution to dual is not unique if an optimal solution to the primal is degenerate and unique? What I tried: Let the primal be $$\max z=cx$$ subject to $$Ax \le ...
3
votes
1answer
2k views

comparison of simplex and shortest path method

In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming. The journal Computing in Science and Engineering listed it as one of the ...
3
votes
1answer
1k views

''min $c^tx$ subject to $x^tAx=1$'': is is possible to solve it with Lagrange multiplier or in the scope of KKT?

I find a problem: Minimize $c^tx$ subject to $x^tAx=1$, where $A$ is a positive semidefinite symmetric matrix. But the question obligates to use KKT but I am trying to apply simple Lagrange ...
3
votes
5answers
951 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 ...
3
votes
1answer
6k views

Will the feasible region always be convex in linear programming? [duplicate]

In linear programming we find a feasible region , is this region always convex? . if a concave region is found where objective is minimization , I think then a solution exists . Advance thanks. ...
3
votes
1answer
2k views

Using max/min operators in linear programming.

I'm currently implementing a Markov Decision Process using the solver GLPK, I'm following the lecture by Vincent Conitzer, and there is a step I don't understand between the theoretical problem and ...
3
votes
2answers
132 views

find the minimum value for the following expression $\max \{ {x_{i_1}, x_{i_2}-x_{i_1},x_{i_3}-x_{i_2} … x_{i_n}-x_{i_{n-1}}, 1-x_{i_n} }\}$

Given the numbers $0<x_1<x_2<...<x_{n^2}<1$, For each sub group of n of those elements: $x_{i_1}<x_{i_2}<...<x_{i_n}$ we will look at the value of the following expression : $...
3
votes
1answer
173 views

How to get an equation system from a Simplex table

Let's assume I already have a simplex table (with an optimal solution): $$\left(\begin{array}{ccccc|c} & x_1 & x_2 & S_1 & S_2 & \\ S_1 & 0 & 2 & 0 & 1 & 2 \\ ...
3
votes
2answers
111 views

How to solve simplex problem with $x_1 + x_2 + x_3 + x_4 =1$ as restriction?

So, there's this problem: maximize $$6x_1 + 8x_2 + 5x_3 + 9x_4$$ subject to $$x_1+x_2+x_3+x_4 = 1 \;\text{ knowing that }\; x_1, x_2, x_3, x_4\geq0$$ The solution is obvious: since the sum of ...
3
votes
1answer
484 views

Optimizing Linear Programming using Deep Neural Network .

Are you afraid of maths? I guess you say "NO". Well, maths is scaring me always, this time again :( I was going through this Research Paper. In this paper , I don't understand how do they solve the ...
3
votes
1answer
180 views

Convert NL equality constraint involving minimum to linear inequality constraint?

Is it possible to convert an equality constraint involving the minimum, to a linear inequality constraint? Suppose I have an optimization problem which involves the variables $x_1,\,x_2,\,x_3$, with ...
3
votes
1answer
938 views

Linear Programming: “at most k out of n variables nonzero” constraint

I have a Mixed-Integer Program that contains (among other things) $n$ variables $v_1, \dots v_n$ (continuous or integer doesn't matter, in $[0, M)$ for some $M$). I want to formulate the constraint ...
3
votes
1answer
114 views

LP modeling issue (factory process)

I am working on a linear programming problem in the following logistic network : $F_1$ and $F_2$ are supply nodes, $U_1$ and $U_2$ are factories, $C_1$ and $C_2$ are customers. $A$ and $B$ are ...
3
votes
1answer
985 views

Proving Farkas' Lemma by using Theorem of Alternatives

Consider the following Theorem of Alternatives: Let $A \in \mathbb{R}^{n}, b \in \mathbb{R}^{m}.$ Then exactly one of the following statements is true: (1) $\exists x \in \mathbb{R}^{n} : Ax \leq b$ ...
3
votes
3answers
719 views

Non-negative solution to linear equation in $n$ variables

Given a positive integer y and n positive integers x1 , x2 , ... , xn does there exist non negative integers a1 , a2 , ... , an ...
3
votes
1answer
759 views

Linear programming with a product term in the objective function

The title might sound a little weird. I actually want to ask if this problem can be solved as a LP. And if so, how to convert the product term? set $P=\{1,2,3,\ldots,n\}$ for index $i$. Variables $...
3
votes
1answer
2k views

Proof of Why Optimal Solutions Occur at Extreme Points

I'm taking my first class in Linear Programming. The book I am reading from is good in that it uses a lot of examples, but bad in that it provides few proofs. I need a proof for the following theorem. ...