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
1answer
562 views

Sudoku mathematically, MILP?

My homework contains a word (freely-translated) "target-function" that I should generate somehow for 9x9 sudoku solver with some MILP problem. But I am bit lost what they mean. I have sofar described ...
2
votes
0answers
457 views

Sensitivity analysis on non linear problems

First of all, I would like to apologize if this question does not fit into the "soft" category. I am quite a newbie around here, and maybe I can fail to get the feeling of what exactly is a "soft" ...
1
vote
0answers
69 views

A question about $n\times n$ matrix [duplicate]

Possible Duplicate: For every matrix $A\in M_{2}( \mathbb{C}) $ there's $X\in M_{2}( \mathbb{C})$ such that $X^2=A$? Square root of a matrix Let $A$ be $n\times n$ matrix on $\mathbb C $. ...
1
vote
2answers
1k views

Optimizing with Absolute Value Objective Function

max : $w = |q^T y|$ subject to $A y \leq b$ $y \geq 0$ Please describe how one could solve the non-linear programming prob. above by using linear programming methods. I tried changing $y$ to $y' ...
2
votes
1answer
254 views

Linear Programming - Single Optimal Solution

Is it correct to state that if a linear objective function is not in parallel with any of the constraints, than there is a single optimal solution at some vertex of the polytope?
2
votes
1answer
103 views

Drawing samples from an LP program

Say I have an LP program in standard form: \begin{equation*} \begin{array}{rl} \mathbf{x}^* = \underset{\mathbf{x}}{\text{arg}\;\text{min}} & \mathbf{c}^T\mathbf{x} \\ \mbox{s.t.} &...
5
votes
1answer
5k views

simplex method : Entering Variable

In the Simplex method, a variable that enters the basis, cannot depart the basis in the very next iteration. Please explain..why so ?
3
votes
1answer
2k views

How can I get a huge Linear Programming Problem? Any public data set?

I'm working on a Parallel Simplex Solver using C and nVidia CUDA for my Bachelor Degree in Computer Science. I've already asked one of my teachers to bring me a super linear problem with thousands (...
3
votes
1answer
258 views

Sensitivity of a solution to an LP Problem to a change in the objective function

Suppose I have a LP problem of the kind $\max f(x) = 2x_1 + c_2x_2$, subject to several restrictions. Suppose I know that the point $(a, b)$ is optimal. How much can $c_2$ change so that $(a, b)$ ...
2
votes
2answers
2k views

Simplex method: Optimality criterion

I have to show that if for a minimization problem, $z_j - c_j <0$, for all non basic variables then it has a unique optimal solution. The proof says "If we start with a feasible point $x$ ...
6
votes
2answers
5k views

Berlin Airlift Linear Optimization Problem

I am trying to learn more about the Berlin Airlift transport problem. Two links I could find are here: http://drmohdzamani.com/notes/file/Simplex%20Method.pdf http://www.cabrillo.edu/~mladdon/math13/...
6
votes
1answer
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}$, ...
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.
4
votes
1answer
185 views

Membership problem for convex cones

Does anyone have a reference for the most efficient or some simple reasonably efficient algorithm for the membership problem for convex cones: Given a finite set of vectors $v_1, ..., v_n$ and a ...
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}...
2
votes
1answer
518 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 ...
4
votes
1answer
809 views

solving linear program with rank constraint?

I have a linear program where the variables are n vectors. Now I'd like to impose an extra constraint that k (k<=n) of the n vectors are linearly independent, or the matrix with the n vectors as ...
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$ = ...
4
votes
1answer
763 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 ...
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 ...
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 ...
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, ...
0
votes
1answer
155 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 ...
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 & ...
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....
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 ...
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).
2
votes
1answer
851 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}$ ...
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 ...
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 ...
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 ...