# Questions tagged [linear-programming]

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

3,587 questions
Filter by
Sorted by
Tagged with
340 views

### What is an efficient way to get blur from source and blurred images?

I'm doing little program to get blur from source image and blurred image. But I haven't learned so much things about math in school yet. The equation used for blurring the image A into B: ...
110 views

### Does max { $w^Tx$ subject to $x$ is a point on a given polyhedron } optimize at an extreme point?

Is it necessary that the linear program max { $w^Tx$ subject to : $x$ is a point on a given polyhedron } attain its maximum at an extreme point of the polyhedron for any arbitrary w ? Let $c$ = ...
516 views

### is there a generalization of unimodular matrices for non-square matrices?

Is there a generalization of unimodular matrices for non-square matrices? It is well-known that unimodular matrices guarantee an integral solution for a linear program (if the constraint matrix is ...
243 views

### Using Correlation for mouse gesture recognition

I am in need to build a mouse gesture recognition system which will compare given recognition to the the gestures in training data and will say where a given gesture best fits. I am planning to use ...
1k views

### Finding tight constraints on a linear inequality

I have $a^\intercal M b > 0$, where $\forall a_i > 0$, $\forall b_j > 0$, and M is known. I'd like to find a tight linear constraint on $b$ which is independent of $a$ (other than the ...
771 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 ...
5k views

### Simplex Method row operations help?

before programming an algorithm which implements the simplex method, I thought I'd solve an issue before the actual programming work begins. For some reason, I can NEVER get the correct answer. I've ...
2k views

### Sufficient Conditions for a Bounded Feasible Region in the Linear Programming Problem

I am working on a problem where it would be nice to prove that the feasible region of a LP problem is bounded, but where it is not necessary to solve any particular problem. In particular, given an ...
11k views

### How can not-equals be expressed as an inequality for a linear programming model

I have this linear programming model I'm building but one of the constraints needs to specify that the solution's basic variables need to all be different from one another. This is an integer linear ...
760 views

### Confused about linear programming exercise solution in my textbook

please see this simple linear programming exercise and its solution from my textbook. The task is to convert the prose and matrix to a formal linear programming problem. My answer matched theirs ...
333 views

### $l_1$-metric and cut metric equivalence

I would like to show that the following two statements are equivalent. Let $(A,d)$ be an $n$-point metric space and $B$ a set of $\binom{n}{2}$ pairs of points of $A$. Then $\exists t \geq 1$, an ...
2k views

### What is the restriction matrix used for in the stepping stone method?

Let's say that we want to solve a classic transportation problem without capacities using the stepping stone method. (Problem definition: A bipartite graph with supply nodes a1...m, demand nodes b1......
649 views

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 ...
132 views

### Basic linear problem solving

I have some LP problem and I'm willing to solve it (this is an exercise from some optimization-related book). Now, Mathematica tells me that the problem is unbounded and I want to make a generic ...
48 views

### How can I adapt my problem so that it is amenable to the simplex algorithm?

According to the Wikipedia article, the Simplex algorithm depends on constraining all the unknowns to be >= 0. I have a problem where one of my variables is highly likely to be negative in many cases....
20k views

### Linear Programming Books

Do you know of a good book on linear programming? To be more specific, i am taking linear optimization class and my textbook sucks. Teacher is not too involved in this class so can't get too much help ...
1k views

### In linear optimization, what does “AP” stand for?

I am learning algorithms, and there is a chapter which uses linear optimization methods to solve a matching problem. This is the problem definition: I find the abbreviations AP for the constraints ...
154 views

### Mathematical Programming Community [closed]

Is there a good online community for discussing optimization models? The ones I have found don't seem to have a critical mass for active discussions.
214 views

### Use duality to find a strong alternative

Find a necessary and sufficient condition for the linear equation Ax = b to have no solution. (hint: Use duality to find a strong alternative to Ax = b).
11k views

### Primal- degenerate optimal, Dual - unique optimal

Simple question- Is it possible for a linear programming optimization problem possible to have a degenerate optimal solution whereas the dual has a unique optimal solution? I can't find a scenario ...
699 views

### Determine which of 8 points make up the 4 corners of a cube's face

I am working on a game program. I have an array of 8 points in 3d space $(X,Y,Z)$ that are the 8 corners of a cube whose $W=H=D$. The 8 points are listed in no particular order. For the sake of ...
463 views

### Prove property of dual Linear Programming problem

If i have a standard LP problem: $$\min \mathbf{d}^T \mathbf{x}$$ subject to $$\mathbf{B}\mathbf{x}=\mathbf{f},\qquad \mathbf{x} \geq 0$$ $\mathbf{y}$ is the optimal solution and $\mathbf{z}$ is ...
847 views

### Linear optimization constrained by cost function

Suppose I have an optimization problem of the form: $$\min \mathbf{d}^{T}\mathbf{y}$$ subject to $$\mathbf{M}\mathbf{y} \geq \mathbf{d}, \qquad \mathbf{y} \geq 0$$ If a solution $\mathbf{s}$ ...
3k views

### Finding all n×n permutation matrices

If I have a doubly stochastic matrix, how can I find the set of all basic feasible solutions? Here's Wikipedia on doubly stochastic matrices.
100 views

### Simplex - 2 different points with the same cost?

Is it possible to have 2 different points (non-degenerate) in $n$-dimensions for any value of $n$ where $n>1$, share the same cost and both be visited by the simplex method?
534 views

### Convert linear programming problem

Suppose x is the solution to a standard linear programming problem ($Ax=b$, $x>=0$) and the set $S$ is every $i$ where $x_{i} = 0$. How can I show this is optimal only where minimize $c'f$ subject ...
2k views

### Prove feasible direction

If $x$ is an element in a standard convex linear optimization set constrained by $Ax = b, x \geq 0$, then how can I prove $d$ is a feasible direction only if $Ad=0$ and $di \geq 0$ for every $i$ where ...
3k views

### Karush-Kuhn-Tucker condition - Lagrange multiplier

I was maths student but now I'm a software engineer and almost all my knowledge about maths formulas is perished. One of my client wants to calculate optimal price for perishable products. He has ...
I have a standard linear programming problems I want to solve:  \min_x f^T x \text{ such that } \left\{ \begin{aligned} A\cdot x &\le b, \\ A_{eq}\cdot x &= b_{eq}, \\ lb \le x &\le ub. ...