Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
2
votes
4answers
319 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
229 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
561 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
456 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
2answers
2k 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 +\cdots+...
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
1k 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
249 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
101 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.} &...
3
votes
1answer
693 views

Getting a vertex of the polytope defined by an LP

I have a standard basic linear program. Is there a polynomial-time algorithm that can return a vertex of the polytope that describes the feasible region? I know that the ellipsoid method can give a ...
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 ?
1
vote
1answer
1k 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
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
256 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$ ...
4
votes
3answers
4k 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 ...
4
votes
1answer
4k 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 ...
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
315 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
181 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
914 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}...
15
votes
3answers
28k 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 ...
4
votes
1answer
799 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$ = ...
2
votes
1answer
509 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
766 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 ...
7
votes
4answers
10k 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
752 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
327 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
645 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
153 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
213 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).