Questions tagged [linear-programming]

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

3,589 questions
Filter by
Sorted by
Tagged with
316 views

Difficulties in Writing the Dual of a Primal Program

I am a student and I am studying the following problem during my spare time. Your comments and suggestions would be helpful. Given the following primal program: (Decision variables are $\xi_{v}$, ...
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 ...
176 views

Transform an optimisation problem into a linearly-constrained quadratic program?

I would like your help with a minimisation problem. The minimisation problem would be a linearly-constrained quadratic program if a specific constraint was not included. I would like to know whether ...
348 views

Nearest signed permutation matrix to a given matrix $A$

Let $A \in \mathbb{R}^{n\times n}$ be a square matrix and let $Q \in O(n)$ be the nearest orthogonal matrix to $A$ under the Frobenius norm, i.e. $$Q = \text{arg}\min_{M \in O(n)} ||A - M||_{F}^2$$ ...
115 views

Name for a cardinality-constrained transportation problem variant

The transportation problem is a well-studied problem in operations research. Given sources $i\in\{1, \ldots, n\}$ and destinations $j\in\{1, \ldots, m\}$, we seek to minimize the total cost of ...
2k views

Computationally proving a linear programming solution is unique?

I have a simple linear programming problem min $c^{T}x$ subject to $Ax\leq b$. That gives me the solution I am looking for when solving in maple. My only problem is that I do not know how to check, ...
1k views

Generating random linear programming problems

I've just finished writing a a linear programming problem solver which uses the simplex method. Now I would like to start optimizing my solver but before I can do this, I need a way of reliably ...
1k views

How does multiplying a primal constraint by a constant change the dual solution?

Suppose we have the problem $\min c^T x$, subject to $Ax=b, x \geq 0$. Suppose that this program and its dual are feasible. Let $\lambda$ be the optimal solution of the dual. If the $k$th constraint ...
243 views