Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
1
vote
2answers
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: ...
0
votes
1answer
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$ = ...
2
votes
1answer
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 ...
3
votes
3answers
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 ...
3
votes
1answer
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 ...
4
votes
0answers
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 ...
2
votes
1answer
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 ...
3
votes
1answer
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 ...
8
votes
4answers
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 ...
4
votes
1answer
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 ...
1
vote
0answers
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 ...
2
votes
1answer
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......
1
vote
1answer
649 views

Questions about weak duality theorem

Following are some corollaries regarding the weak duality theorem. Consider a constrained problem, $\min_{x \in X} f(x),$ subject to $g(x) \leq 0$ and $h(x) =0$. Its dual problem is $\sup_{u \geq 0, ...
1
vote
1answer
1k views

Weak duality theorem and false corollary

Let $A\in\mathbb{R}^{m\times n}, \ c\in \mathbb{R}^n, \ b\in\mathbb{R}^m$ and consider the linear program $$\max \{ c^Tx : Ax\le b\} \ (1)$$ Its dual is $$\min \{ b^Ty : A^Ty=c, \ y\ge 0\} \ (2)$$ The ...
1
vote
1answer
1k views

How to set up a linear programming problem?

I'm not 100% sure if I set up the following problem right. Once I have the problem set up I know how to solve it. (this is a homework problem) The problem goes like this:"A company can use plastic, ...
6
votes
2answers
8k views

Understanding proof of Farkas Lemma

I've attached an image of my book (Theorem 4.4.1 is at the bottom of the image). I need help understanding what this book is saying. In the first sentence on p.113: "If (I) holds, then the primal ...
0
votes
1answer
154 views

binary variable question

I need to make a constraint for the following condition: Student 1 can only be on the team if students 2, 3, 4, and 5 are also on the team. I'm not sure how to model this using equations. The ...
1
vote
2answers
6k views

Help with binary variable

I need to make a constraint for the following condition: Among students 1, 2, 3, and 4, at least two of them must be on the team, if there are any on the team at all. I have defined Y1, Y2, Y3, and ...
11
votes
2answers
18k views

Primal and dual solution to linear programming

Lets say we are given a primal linear programming problem: $\begin{array}{ccc} \text{minimize } & c^{T}x & &\\ \text{subject to: } & Ax & \ge & b \\ & x & \ge & ...
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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....
26
votes
8answers
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 ...
2
votes
1answer
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 ...
2
votes
0answers
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.
1
vote
1answer
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).
8
votes
3answers
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 ...
4
votes
1answer
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 ...
3
votes
1answer
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 ...
2
votes
1answer
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}$ ...
5
votes
1answer
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.
3
votes
1answer
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?
0
votes
1answer
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 ...
2
votes
1answer
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 ...
4
votes
3answers
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 ...
4
votes
1answer
701 views

How to minimize a function where the number of variables is unknown?

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. ...
13
votes
3answers
1k views

What is linear programming?

I asked this question on Stack Overflow but it was closed as "not programming related". So I think this is probably the best place for it... I read over the wikipedia article, but it seems to be ...