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

learn more… | top users | synonyms

4
votes
1answer
99 views

Minimizing the distance between points in two sets

Given two sets $A, B\subset \mathbb{N}^2$, each with finite cardinality, what's the most efficient algorithm to compute $\min_{u\in A, v\in B}d(u, v)$ where $d(u,v)$ is the (Euclidean) distance ...
1
vote
1answer
95 views

First-order necessary condition for relative minimum point

I'm studying linear and nonlinear programming and I came across with the following proposition : given $\rm x\in\Omega$ we are motivated to say that a vector $\mathbf d$ is a feasible direction at ...
0
votes
1answer
86 views

How to solve a linear program with OR constraints

I have $n$ people. I want assign them to $c$ jobs. A job may be not assigned at all or there must be a minimum and maximum number of people assigned to it. $n$ is about 4000 and $c$ is about 1000. ...
2
votes
2answers
5k views

Simplex algorithm - primal or dual?

As far as I know there are two simplex algorithms - primal and dual. They have different halting criteria etc. Before using simplex I have to make a standarization of the LP. So when do I use ...
1
vote
1answer
58 views

Primal simplex algorithm

I have the following linear program: $f(x)=2x_{1}+18x_{2} -> min$ $80x_{1}+100x_{2}>=100$ $20x_{1}+200x_{2}>=300$ $80x_{1}>=1.5$ $x_{1},x_{2}>=0$ In standard form: ...
3
votes
1answer
535 views

comparison of simplex and shortest path method

In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming. The journal Computing in Science and Engineering listed it as one of the ...
-1
votes
1answer
60 views

Linear programming problem-optimal solution

I'm having the following linear programming problem: $$\begin{align} \max \quad & 2x_{1}+6x_{2}+3x_{3}, & \\ \text{s.t.} \quad & -3x_{2}+a x_{3} \geq2, \\ & x_{1}+5x_{2}+2x_{3} =2, \\ ...
5
votes
2answers
152 views

Almost a linear program. How to solve efficiently?

How can one go about solving this optimization problem efficiently? Unfortunately it is a maximization instead of a minimization, which stymied my attempts at converting it into an LP. $$ ...
1
vote
0answers
24 views

Reference for a Linear Programming result

I would like to know some reference for a result from Linear Programming. The function $F(s)$ to be maximized depends linearly on the m+1 values, say $x_i$, and the constraints for $x_i$ are linear ...
0
votes
0answers
475 views

finding the minimum number of lines to cover all zeros in an assignment probem

I have been trying to follow the following steps to find the minimum number of horizontal and vertical lines that cover all the zeros in an assignment problem using Hungarian method: Tick all ...
0
votes
1answer
178 views

Are my linear program equations correct?

Here's the problem: "An electronics company has a contract to deliver 21,475 radios within the next four weeks. The client is willing to pay 20 dollars for each radio delivered by the end of the first ...
0
votes
1answer
97 views

Simplex Algorithm

I'm currently trying to implement the (revised) Simplex Algorithm, but according to my notes the LP in standard form $\left( Ax = b, x \geq 0 \right)$ with $A \in \mathbb R^{m \times n}$ has to have ...
1
vote
0answers
85 views

Some problems with a proof of the Farkas Lemma

The following is a proof of the Farkas Lemma that is creating me quite some problems. [I presented the all proof simply to point out the notation used by the author.] My problem is with the last part ...
1
vote
1answer
50 views

Does the identity matrix adapt to any other matrix?

So I have a matrix of the form $X=AX+B$ Where $X$ is a 3 by 1 column matrix, $A$ is a 3 by 3 matrix and $B$ is a 3 by 1 column matrix. (Notice that I am talking about Leontief input-output). So I ...
2
votes
1answer
232 views

Iterative update of pseudo inverse solution

I have an overdetermined linear problem of the form $A x = b$, which is solved in least squares sense using the Moore–Penrose pseudo invers. The issue now is, that over time additional constraints and ...
0
votes
1answer
108 views

Regression with equally spaced set

I'm working on an algorithm (written in Python/Cython, but it reads like pseudo-code) that estimates the gradient of each point in noisy data, using a variable window size. It's working very well, but ...
1
vote
0answers
76 views

Understanding the beginning, while, sum, and end of an algorithm

My problem is as follows: \1brace procedure sum (n: positive number) sum:=0 while i < 10 begin sum :=sum + i end output(sum) \rbrace Then, I have the following choices to select from as ...
1
vote
0answers
303 views

Constraints of a linear programming problem

QUESTION Sandy Arledge is the program scheduling manager for WCBN‐TV. Sandy would like to plan the schedule of television shows for next Wednesday evening. Of the nine possible one‐half hour ...
0
votes
1answer
54 views

Sufficient conditions for relaxed integer programs to have integer solutions.

Suppose we are given an integer program and we remove the integrality constraints to get a relaxed linear program. Are there a set of sufficient conditions on the form of the linear program, (e.g. ...
0
votes
0answers
27 views

How to check if steepest gradient method will converge?

So I have this function $ f(x,y) = x^4 - 2x^2 +x + 4y^2 $ and I want to know if the steepest gradient method will converge if I pick an arbitrary point and apply said method. My initial thought ...
0
votes
1answer
46 views

How to check linear independence

How can I check the linear independence of my variables? I have this system $Ax=b$ where $A$ is a $N \times 4$ matrix. I want to check the linear independence between the 4 variables in matrix $A$.
2
votes
0answers
40 views

Showing a Hermitian preserving map is not necessarily positivity preserving?

Say I have a linear map, which is not positivity preserving $$\phi: \mathscr H \to \mathscr H$$where $\mathscr H$ is the set of $n \times n$ Hermitian matrices. Then does there exist a positive ...
1
vote
0answers
43 views

KKT conditions and feasibility of problems (P) and (D)

Let following linear problems: Primal Problem: \begin{eqnarray*} \textrm{Min}\quad c^T x & & \\ \textrm{s.t.}\quad Ax & \geq & b \end{eqnarray*} and its dual problem: ...
2
votes
1answer
68 views

Finding subgradients

How would I find the subgradients of this : $$ f(x) = \max_{i=1,\ldots,n} a_i^Tx + b_i$$ I'm new to subgradients and any hint on how to start this would be useful for me.
0
votes
0answers
206 views

Application of Farkas' Lemma

Suppose matrices $A_{p\times n}$ and $B_{q\times n}$. Use Farkas' Lemma to prove that one and only one of below systems has solution: $$(1)\qquad AX<0,\quad BX = 0, \quad X\in\mathbb{R}^{n} $$ ...
3
votes
1answer
309 views

Converting if else constraints into linear ones

I have the following two constraints: $$ x_1 \leq x_2 \leq x_3 \qquad \mbox{if } x_1 \leq x_3 \\ x_1 > x_2 > x_3 \qquad \mbox{otherwise} $$ Is there a way to get rid of the two conditions and ...
1
vote
1answer
29 views

Set up for matrix solutions

I've haven't touched linear algebra in a while so I'm sorry if this seems simple but I did a google search and I am still confused. I have to find a solution to the following set of equations: ...
1
vote
0answers
34 views

Modeling 4 people going to same place over 3 different places for at least 5 days

I'm trying to model a linear programming task with the condition 4 people going to the same place among 3 different places for at least 5 days. I have the variables for the time spend each person in ...
0
votes
1answer
79 views

Transform OR clause to algebraic equations (linear programming)

So basically my question is: does it exist a way to transform the clausure (a or b or c) into one or more algebraic equations giving as a result 0 or 1 AND that can be included in a linear programming ...
0
votes
1answer
39 views

Definition of an active hyperplane

We are learning about the Geometry of Duality in Linear Programming, and my prof uses the terminology active hyperplane. I'm wondering what the formal definition of this is. I can't seem to find any ...
0
votes
0answers
29 views

Finding dual of incredibly complex LP; any trick?

This is homework, so only hints please. This is about a LP relaxation of the minimum cost perfect matching problem, with another constraint that shrinks the solution space in a way that a lot of ...
0
votes
1answer
190 views

Weak form for Linear Dynamic Wave Equation of Dirichlet/Neumann's boundaries?

I have a linear problem with double derivate of space and time, which has Dirichlet boundary condition in $(1)_{2}$ and Neumann's boundary condition in $(1)_{3}$: \begin{equation} \frac{\delta^{2} ...
1
vote
0answers
64 views

Fitting a sine using linear regression

If I have two functions $s_1 = A_1 \sin(\theta+\phi)$ and $s_2 = A_2 \cos(\theta+\phi)$ is it possible to fit a sine or a cosine using linear regression? I usually have much less that a period ...
2
votes
0answers
56 views

convexity in oriented matroid theory

I would like to try to solve the following problems. If someone knows how to prove at least part (a), could you show me the proof? I am having a LOT of trouble understanding oriented matroid theory. ...
1
vote
0answers
65 views

computing dual LP in graph matchings

I'm having a trouble converting the following LP to a dual LP. Help on some starting steps would be greatly appreciated!
1
vote
0answers
20 views

elements of oriented matroids belonging either to positive circuits or positive cocircuits

I need to prove the following, which seems trivial because it follows from the Farkas lemma (you may know this as the 3 or 4 painting lemma). Can someone show me how to prove this, please? I'm a bit ...
1
vote
1answer
163 views

Solve linear programming given access to an oracle

This question is about designing a polynomial time algorithm for linear programming given access to an oracle outputs YES if and only if $\{\vec{x}\ |\ A\vec{x} = \vec{b}, \vec{x}\geqslant ...
1
vote
1answer
58 views

Linear Programming Convexity Proof

Suppose a linear programming problem in standard form has as constraints $A \underline{X} = b$ and $\underline{X} \geq \underline{0}$, where $\underline{A}$ is an $m \times n$ matrix and ...
0
votes
1answer
598 views

Finite optimal value for a linear program with unbounded feasible region.

I read this problem in CLRST : Show that a linear program can have finite optimal objective value even if the feasible region is not bounded. Now all the cases I could think of where such a thing ...
0
votes
0answers
26 views

String satisfying the condition

Given $N$, $A_0$, $B_0$, $L_0$, $A_1$, $B_1$ and $L_1$, find a sequence S consisting only of characters '$0$' and '$1$'(a total of N characters) such that: The number of '$0$'s in any consecutive ...
1
vote
0answers
9 views

Lp optimality proof [duplicate]

i have a general question. if there is a general LP problem $c^Tx$ s.t $A\cdot x \le b$, and $x \ge 0$ and assuming that the components of $c$ are non-zero entries then how can I prove that when $x$ ...
3
votes
1answer
344 views

Largest Circle in a Polygon

My polygon is given by $P=$$\left\{x\geq 0, y\geq 0, 3x-4y\leq 2, 4x+3y\leq 12\right\}$ Now trying to find the largest circle inscribed inside these half-planes. But whenever I formulate it as an LP ...
2
votes
1answer
192 views

Dimension of polyhedron defined by inequalities and rank of implied equalities

I'm looking at "Optimization Over Integers" by Bertsimas and Weismantel and I have a question about one of the examples in the book. I'm getting a conflicting answer and I'm not sure what I'm ...
2
votes
1answer
1k views

Taylor's theorem for vector valued functions

I'm reading about linear and nonlinear programming and on one page I have the following statment (I have highlighted the areas where I have problems and drawn questions for them in the bottom of it): ...
6
votes
1answer
118 views

Why is there n-1 different objects in a n by n matrix game like Bejeweled?

For games that consists of a grid, and is similar to the concept like bejeweled: has an n by n matrix and n-1 different objects. What is the reason for this? Why not have more than n-1 different ...
2
votes
1answer
83 views

What needs to be linear for the problem to be considered linear?

Harry Altman presented an excellent question in a comment here: What needs to be linear for the problem to be considered linear? So is it enough to a have linear objective function or other ...
0
votes
1answer
35 views

Help with a property of a convex function

I'm studying linear and nonlinear programming and on my book I bumped into the following statement: $$\lim_{\alpha \to 0} \displaystyle \frac{f(\textbf{x}+\alpha ...
1
vote
0answers
29 views

Linear programming: can someone explain how the time steps work here?

I'm reading a paper, "A Player Selection Heuristic for a Sports League Draft". In it, the authors have come up with a method to assist you in picking players for a fantasy sports league. I'm having ...
0
votes
1answer
61 views

Integer Programming

I've been having trouble getting started with this problem. Suppose $x_1,x_2,x_3$ are integers $\geq 0$, satisfying $$21.7x_1-18.2x_2-19.4x_3=5.3$$ Then show $$7x_1+8x_2+6x_3=3+10z_1$$. ...
1
vote
1answer
151 views

LP: how to understand Duality and simplex

I am learning about Linear Programming right now.. I learned that we can use simplex to solve linear program and I also learned that every linear problem has a dual problem because of duality.. I am ...