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

learn more… | top users | synonyms

0
votes
0answers
327 views

Can this non-linear optimisation problem be converted to a linear?

I have to minimize the function: $F(x)$ $F(x) = \sum_{i=1}^{M}||x_{i+1} - x_i - K(\frac{x_{i+1} + x_i}{2})||^2 + ||x_1-c_1||^2 + ||x_N-c_2||^2$ , where $x$ is a vector of $N$ scalars, $c$ are ...
1
vote
2answers
582 views

Sign restriction on the Lagrange multiplier? Why?

Say we are given a linear program where the goal is to minimize $c^Tx$ with the constraints $Ax\ge b$. Why is there a sign restriction on the Lagrange multiplier associated with the active constraints ...
0
votes
1answer
59 views

primal simplex procedure

Minimize $-2x_1-x_2+2x_3$ subject to $x_1 +x_3 = 4$, $-2x_1 +x_2 = 8$ s.t. $x_1,x_2,x_3\geq 0$. In my book, the augmented matrix is defined as $[A : 0 : b; -c^T : 1 :0]$ (where : separates ...
0
votes
0answers
72 views

Solving PSD matrix in Newton's method

I have functions defined as follows: $f_1(A) = \sum\|x_i-x_j\|_A = \sum\sqrt{(x_i-x_j)^TA(x_i-x_j)}$ and $f_2(A) = \sum\|x_k-x_l\|^2_A$ where $A$ is a positive semi-definite (PSD) matrix, $x$ are ...
0
votes
1answer
69 views

Chaotic solutions to mixed integer linear problems

Is there a way to get the branch and bound algorithm to converge to a solution "close" to an initial value? One way I can think of, is to adding a "distance from initial value" term to the cost ...
0
votes
1answer
45 views

How do I solve a LP problem when constrains have different inequalties?

How can I solve this LP problem: Maximize p=x subject to : x+y <=30 x-2y <= 0 2x+y >=30 x>=0 , y>=0 using simplex method?
1
vote
1answer
407 views

Convex hull of sets defined by (in)equalities

If you define the convex hull of a set $X$ as the set of all convex combinations of elements of $X$, it becomes difficult to decide if a given element $w$ belongs or not to $conv(X)$ (You have to ...
0
votes
2answers
687 views

Gradient solver

my question is about gradient algorithms. Lets have function f like: $f(x) = \|Ax-b\|^2$ and i want to find its minimum (according to x). So i can use some gradient method, for instance gradient ...
1
vote
1answer
46 views

Assume $x\in \operatorname{cone}\{a_1, a_2,\ldots, a_m\}$. Is there a systematic way to find out the coefficients of $x$ with respect to $a_i$'s?

Assume $x\in \operatorname{cone}\{a_1, a_2,\ldots, a_m\}$. Is there a systematic way to find out the coefficients of $x$ with respect to $a_i$'s? When $a_i$'s are independent, it should easy. What ...
1
vote
1answer
142 views

Techniques for (upper-)bounding LP maximization

I have a huge maximization linear program (variables grow as a factorial of a parameter). I would like to bound the objective function from above. I know that looking at the dual bounds the objective ...
0
votes
1answer
138 views

trying to read quadratic programming problem in cplex, get error

I am trying to load a CPLEX LP file in to CPLEX using the "read" command. I believe that in this problem, I have a set of constraints that are quadratic. But, from what I understand CPLEX will still ...
-1
votes
1answer
243 views

How to express $y = x\ \mathrm{mod}\ 2$ as an ILP?

Using the signed modulo operation: $(x\ \mathrm{mod}\ 2) = \begin{cases} 0\ \mathrm{if}\ x\ \mathrm{is\ even} \\ 1\ \mathrm{if}\ x > 0\ \mathrm{and}\ x\ \mathrm{is\ odd} \\ -1\ \mathrm{if}\ x ...
1
vote
1answer
155 views

Continuity of a Parametric Linear Program

Consider the convex optimization problem $$ \min_{x \in X, \ y \in Y } x $$ $$ \text{sub. to } \ x A + B y + C = 0 $$ where $X = [0,1] \subset \mathbb{R}$, $Y \subset \mathbb{R}^M $ are compact ...
1
vote
1answer
259 views

Does the triangle inequality suffice to prove all minimum results on sums of absolute values of affine functions?

The title says it all ... more formally : let $n \geq 1$, and let $a_1, a_2 , \ldots ,a_n$ be positive numbers, let $b_1, b_2 , \ldots ,b_n$ be real numbers. Consider for $x\in {\mathbb R}$, $$ ...
0
votes
1answer
176 views

creating a set in ZIMPL (which creates .LP for SoPlex & CPLEX)

I am looking for some help creating a set dynamically in ZIMPL. I have a parameter table: ...
0
votes
1answer
182 views

Solving linear programming problem with global opt method

why not solve a linear programming problem with a global opt method, or a local search method as SQP or Newton methods? I am writting a solver facing linear and non linear problems, and I wonder ...
1
vote
1answer
131 views

Optimization for large scale linear problem with equality constraint

Given the wide range of optimization methods, which is the appropriate method to use? I am thinking of using either linear programming (interior-point methods) or augmented Lagrangian methods. Which ...
0
votes
1answer
167 views

Linear Programming Duality (Basic optimization)

Suppose that $A$ is an $m\times n$ matrix, $D$ is a $p\times n$ matrix, $b$ is an $m$-vector, and $d$ is a $p$-vector. Prove that there does not exist $n$-vector $x$ satisfying $$Ax \geq b, Dx \leq ...
3
votes
1answer
172 views

Efficiently solving a special integer linear programming with simple structure and known feasible solution

Consider an ILP of the following form: Minimize $\sum_{k=1}^N s_i$ where $\sum_{k=i}^j s_i \ge c_1 (j-i) + c_2 - \sum_{k=i}^j a_i$ for given constants $c_1, c_2 > 0$ and a given sequence of ...
1
vote
2answers
309 views

Need help with a Linear Programming homework.

Please help with the problem: A polyhedron P in $R^n$ is given by the system of m linear inequalities (of n variables). Furthermore, let P have k vertices (that is, k vectors satisfying all m ...
1
vote
1answer
83 views

Casting a linear (in)equality into a linear program problem

Suppose I have the systems $$S_1: Ax \leq b$$ where $A \in \mathbb{R}^{n\times m}$, $x \in \mathbb{R}^m$ and $b \in \mathbb{R}^n$, and $$S_2 : y^{\intercal}A=0,\\ y \geq 0,\\ y^{\intercal}b < 0 $$ ...
2
votes
0answers
117 views

Linear optimization, homework problem.

Please help with the following problem: Given a $m$ x $n$ matrix $A$, $m$-vectors $b$ and $y$, and $n$-vectors $c$ and $x$. Write the dual $LP$ problems $P$ and $P^d$ in the standard form. Whether ...
2
votes
0answers
160 views

Linear optimization problem.

I have copied the entire problem from the book. It has 7 parts. Please show me how to do any 1-2 of the parts. I mostly understand the problem, but need to see a fully woked out problem. Given a $m$ ...
1
vote
2answers
140 views

Solving LP from tableau

$$\begin{array}{cccccc} & x1 & x2 & x3 & x4& x5 \\ -4& 2 & 0& -2 & 0& 3\\ 3 & 1 & 0 & -1& 1 & 3\\ 2 ...
1
vote
1answer
934 views

What are the algorithms for integer programming in which constraints are dependent?

What are some ways to deal with dependent constraints in integer programming? For example, suppose I want to maximize $x+3y+2z$ subject to (i) $x+y<=3$ and (ii) if $y+z>=2$ then $x+z<=6$. ...
1
vote
1answer
155 views

Reverse Linear Programming Formulation

My question is about having an LP in the standard form $Ax \leq b$ and the set of basic feasible solutions. For each basic feasible solution (bfs) does there exist an appropriate objective function ...
1
vote
1answer
164 views

Linear Program feasibility

Let $A$ be an $m \times n $ matrix, $b \in \mathbb{R}^n$, and consider the linear program $$\max\{ 0^Tx: Ax = b, x \ge 0\},$$ and its dual $$\operatorname{min}\{y^Tb : y^TA \ge 0 \}.$$ Here $x \in ...
3
votes
1answer
254 views

What is the complexity of computing the minimum distance between two convex polyhedra that both have $n$ faces?

EDIT: (in response to what deinst said) sometimes using a sledgehammer for some menial task is rather convenient - especially if it also has the complexity $O(n)$ (which is what my question is about) ...
3
votes
1answer
2k views

How to show a primal program is unbounded by using weak duality?

In weak duality theorem, we assume $x_i$ and $y_i$ are feasible. But how could we show a primal program is unbounded by this theorem? Suppose we have a primal program: $\max \mathbf c^\top \mathbf x, ...
1
vote
0answers
494 views

non-degeneracy in linear programming

How to do the sum? Consider the standard form polyhedron $P = \{\mathbf{x} | A\mathbf{x}=\mathbf{b}, \mathbf{x} \geq 0\}$. Suppose the matrix $A$, of dimensions $m \times n$,(m<=n) has linearly ...
1
vote
1answer
610 views

Verifying optimality for given primal and dual solutions to a linear program

Consider the following linear program: maximize $\sum\limits_{j = 1}^n {{p_j}{x_j}}$ subject to $\sum\limits_{j = 1}^n {{q_j}{x_j}} \le \beta$ $\begin{array}{*{20}{c}} {{x_j} \le 1}&{j = 1,2, ...
1
vote
0answers
150 views

All optimal solutions of a linear program

Is there a software package that can output all optimal solutions of a linear program if there are multiple such solutions?
6
votes
0answers
88 views

Does the Hirsch conjecture hold for $n < 2d$?

The Hirsch conjecture states that the graph (i.e. $1$-skeleton) of a $d$-dimensional polytope with $n$ facets has diameter at most $n - d$. It was known for a long time that it sufficed to prove it ...
3
votes
1answer
77 views

The Hirsch conjecture in $3$-dimensions

What I am wondering is if the Hirsch conjecture has a simple proof (just a few lines) in $3$ dimensions, perhaps by using Steinitz's theorem or Kuratowski's theorem and some kind of induction ...
4
votes
1answer
475 views

How to determine whether a system of linear inequalities has a POSITIVE solution or not?

The question I'd like to ask is as in the title: How to determine whether a system of linear inequalities has a POSITIVE solution or not? Is there any poly-time algorithm to do this? Or the best ...
1
vote
2answers
226 views

Dual LP from Primal LP, how?

$$\min x +y + z$$ so that $$ x + y =2$$ and $$y + z = 3$$ where, $x,y,z >0$. How to create the dual? [Something like this?] $$ \max 2s + 3t$$ so that $$ ...+... =1$$ and $$ ...+...=1$$ ...
1
vote
1answer
1k views

Simple Minimization Problem: A few questions regarding the mechanics of solving

Consider the following elementary minimization problem: Minimize: $\phi = 2700x + 2400y + 2100z$, subject to: $\text{Constraint 1}: 55x + 45y + 35z \geq 41000$ $\text{Constraint 2}: 30x + 35y + 50z ...
0
votes
1answer
301 views

How to apply the simplex method to prove that the following problem is unbounded?

$\max 6t_1 + 4t_2$ $-t_1 + t_2 \leq 6$ $t_1 - t_2 \leq 1$ $t_1 - 2t_2 \leq 8$ $t_1, t_2 \geq 0$ Anyone?
8
votes
1answer
35k views

shadow price in linear programming

I am quite confused about the meaning of shadow price from explanations on the internet. It can be understood as the value of a change in revenue if the constraint is relaxed, or how much you would ...
0
votes
1answer
356 views

Multicommodity flow in polynomial size

The original linear program for multicommodity flow has exponentially many variables. How to find equivalent linear program that has polynomial size? Linear program of multicommodity flow $maximize ...
1
vote
1answer
291 views

Underlying assumption in a Primal/Dual table

I just read in one of the questions answered by @MikeSpivey that the following table is provided in Sierksma's Linear and Integer Programming: Theory and Practice, Volume 1, page 144. ...
2
votes
1answer
219 views

Multiple solutions for both primal and dual

If matrix $A$ in an LP (or $A^T$ in its dual) has full row (column- in dual) rank, is it possible that both primal and dual have multiple solutions?
1
vote
1answer
72 views

Does the sparsest cut always have a solution?

How do I prove that the sparsest cut always has an optimal solution which is the cut for some vertex-subset? It looks like it should be a kind of fundamental theorem for sparsest cut. But I didn't ...
2
votes
1answer
139 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
485 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
454 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
933 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
363 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
241 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 ...