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

learn more… | top users | synonyms

2
votes
1answer
136 views

Sparsest cut is solvable on trees

The problem is to prove that Sparsest cut is solvable on trees in polynomial time. A short review, a sparsest cut is linear program $$\min \frac{c(S,\overline{S})}{D(S,\overline{S})}$$ where ...
1
vote
2answers
471 views

Recommendation of Book about Linear Programming and Linear Algebra?

I'm going to take this course next semester Description Formulation, solution and applications of integer programs. Branch and bound, cutting plane, and column generation algorithms. Combinatorial ...
4
votes
1answer
427 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 ...
2
votes
1answer
205 views

Approximate Set Cover Problem by Rounding

Here is the simple algorithm for approximating set cover problem using rounding: Algorithm 14.1 (Set cover via LP-rounding) Find an optimal solution to the LP-relaxation. Pick all sets ...
1
vote
1answer
920 views

Two-Phase Method (Linear Programming)

In Linear programming, when is it beneficial to use the Two-Phase Method? Why not just use the Simplex Method? (edit: typo)
3
votes
1answer
357 views

Connected graph solution from IP/LP

I have a problem on a graph (of maximum degree $c$) which looks for a connected subset of edges fulfilling some properties. I have problems formulating the connectedness condition in an IP/LP. The ...
1
vote
1answer
237 views

How to choose $u_i$'s for Chvatal-Gomory cutting plane?

Trying to understand the example of Chvatal-Gomory cutting planes (Lee p. 153), they say: $\max 2x_1 + x_2 $ subject to: $7x_1 + x_2 \leq 28$ $-x_1 +3x_2 \leq 7$ $-8x_1 -9x_2 \leq -32 ...
4
votes
1answer
805 views

Regarding complementary slackness condition

I have a question regarding complementary slackness, the answer should be true of false. The complementary slackness conditions connect pairs of optimal basic feasible solution of primal and dual ...
4
votes
1answer
198 views

Book on advanced topics of Network Flows

I am taking linear optimization class. Could you suggest me good fundamental textbook on advanced topics of network flows. To be more specific I am interested in: Multicommodity flow and multicut, the ...
0
votes
1answer
151 views

About linear programming

Before to write my question. (P) linear programming, and the dual problem is denoted (P*). Th linear problem defined via matrix (m x n) matrix A. b is a vector in R^m and c in R^n. The program (P) can ...
2
votes
1answer
89 views

Linear programmimg

If we are solving a linear programming question using graphical method, it is said that the optimum point will be one of the extreme points. I want to make clear how this happens always (assume that ...
4
votes
1answer
724 views

Proving Helly's theorem

The problem is to prove Helly's theorem for the case, when the convex bodies are polytopes, by using linear programming duality. Helly's theorem Let $B_{1},...,B_{m}$ be a collection of convex ...
2
votes
1answer
1k views

Simplex method : Duality by Bazaraa

I use great textbook (Linear Programming and Network Flows by Bazaraa II ed) On the page 240 the author states that for every primal problem, regardless of it's type (canonical or standard), dual ...
1
vote
1answer
414 views

Simplex method : Improving a basic feasible solution by Bazaraa

My question is about improving a basic feasible solution according to Bazaraa's explanation (Linear Programming and Network Flows ed II p94) Improving a basic feasible solution ...
2
votes
1answer
183 views

Lagrange multipliers for discrete variables

Is there a way to adapt the method of Lagrange multipliers to problems involving discrete variables? Unfortunately I don't have a specific problem to ask here (I haven't completely formulated it ...
5
votes
1answer
5k views

Degeneracy in Linear Programming

Consider the standard form polyhedron, and assume that the rows of the matrix A are linearly independent. $$ \left \{ x | Ax = b, x \geq 0 \right \} $$ (a) Suppose that two different bases lead to ...
3
votes
1answer
1k views

In Simplex Method, if the leaving variable fails for all candidates of MRT, what's wrong?

I'm facing a problem programming a full tableau solver for some LP problems. The difficulty is when the test for leaving (line) variable cannot find a single positive value on the pivot column for ...
4
votes
2answers
2k views

Solving $Ax=b$ under $L_1$ $|Ax-b|$ minimization

I would like to solve a linear system $Ax = b$ under the $L_1$ norm constraint $\min(|Ax-b|)$. All that I can find about $L_1$ minimization is a way to minimize $|x|_1$ subject to $Ax=b$. I wanted to ...
2
votes
1answer
255 views

Finding lexicographic maximum point using a linear program

I'm trying to find the lexicographical maximum point of a bounded polyhedron, i.e. I have a set $P = \{x \in \mathbb{R}^n : Ax \leq b\}$ and I'm looking for the lexicographic maximum point of this ...
4
votes
2answers
391 views

Linear programming for combinatorics/graph theory

I just went to a graph theory talk talking about various fractional graph parameters (but focusing on one). These were defined using linear programming. A question was asked, "How can we learn more ...
2
votes
3answers
197 views

Linear inequalities to make a specific solution infeasible

Say we have a binary linear programming problem: \begin{equation*} \begin{aligned} & \underset{\mathbf{x}}{\text{minimize}} & & c\cdot\mathbf{x} \\ & \text{subject to} & ...
3
votes
2answers
180 views

How many ${0, 1}$ solutions would this system of underdetermined linear equations have?

The problem: I have a system of N linear equations, with K unknowns; and K > N. Although the equations are over $\mathbb Z$, the unknowns can only take the values 0 or 1. Here's an example with N=11 ...
1
vote
1answer
282 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 ...
1
vote
0answers
216 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" ...
2
votes
1answer
416 views

Why we call it technological coefficients?

I'm learning linear programming's basic concepts. In following inequality: $$ \begin{align} \text{Minimize }c_1x_1 + c_2x_2 + \cdots+ c_nx_n \\ \\ \text{Subject to }a_{11}x_1 + a_{12}x_2 ...
1
vote
0answers
50 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 ...
1
vote
2answers
705 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
323 views

Column generation algorithm gets stuck — subproblem returns an existing column in master

I have implemented a column generation algorithm to (try to) solve a computationally large transportation routing problem. The gist of the algorithm is the classic column generation scheme: 1) start ...
2
votes
1answer
163 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
77 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.} ...
2
votes
1answer
246 views

Linear Programming - Getting a vertex of the polytope

I have a standard basic linear programming problem. Is there a polynomial time algorithm that can return a vertex of the polytope that describes the feasible set of solutions. I know that the ...
5
votes
1answer
2k 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 ?
0
votes
1answer
214 views

Positive semidefinite vector $\bar{x}$ as $\bar{x}>0 :=\bar{x} \lambda \bar{x}^{T}>0$?

$A \lambda A^{T} $ (quadratic form?) is used with matrices to check definiteness. What about with vectors? If I see conditions such as $\bar{x} > 0$, how can I know whether it means $\bar{x}_{i} ...
3
votes
1answer
557 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
115 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
504 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$ ...
3
votes
2answers
2k views

Linear programming problem formulation

Stuck in this problem for quite a while. Anyone can offer some help? The problem is as follows: Fred has $5000 to invest over the next five years. At the beginning of each year he can invest money in ...
3
votes
1answer
2k views

Choosing Pivot differently in maximization Simplex- and minimization Simplex method?

In maximization simplex, the pivot is the smallest element in the column divided by the rightmost corresponding number. I am stumbling with the Example 3 here with solution that choose the pivot with ...
5
votes
2answers
1k 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 ...
6
votes
1answer
193 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}$, ...
4
votes
1answer
106 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 ...
2
votes
2answers
270 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. ...
9
votes
3answers
8k views

Optimum solution to a Linear programming problem

If we have a feasible space for a given LPP (linear programming problem), how is it that its optimum solution lies on one of the corner points of the graphical solution? (I am here concerned only with ...
3
votes
1answer
199 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
239 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
90 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
207 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
205 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 ...
1
vote
1answer
232 views

Lower bound for the complexity of linear programming

Since it is known that you can sort $n$ numbers by solving a certain kind of linear program - doesn't this imply a lower bound on the complexity of solving linear programs in general via the lower ...
3
votes
1answer
543 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 ...