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

learn more… | top users | synonyms

5
votes
1answer
429 views

Linear Programming with One Quadratic Equality Constraint

I have a problem which can be formulated as a Linear Programming with One Quadratic Equality Constraint: where variable x is n-dimensional vector and H is a Semi-Positive Definite n-by-n matrix. I ...
6
votes
1answer
1k views

Linear Programming: More variables or more constraints; which one is better?

This is more of a practical question, rather than Math question. I have an LP which has $n$ variables and $m$ constrains, where $ n << m $. If I convert this into its dual form, I will have ...
2
votes
1answer
71 views

Solutions of the LP problem

I am asked to find all the solutions of the following linear programming problem using the simplex method. $$\min(2x + 3y + 6z + 4w)$$ $$\begin{aligned} x+2y+3z+w &\geq 5\\ x+y+2z+3w ...
1
vote
1answer
38 views

Binary integer programming problem of a very specific form

The specificity of the problem lies in the fact that the objective function coincides with the left side of the only constraint. In other words: $$ \sum\limits_{i=0}^n a_i x_i \to \max, $$ $$ ...
0
votes
1answer
385 views

Choosing pivot row in Simplex - slack variables allowed?

I have a question concerning the Simplex method to solve linear optimization problems. I have the following problem: $$ f(x,y,z) = x+2y+3z$$ Constraints: $$x+y+z \leq 3$$ $$2x+2y+z \geq 4$$ So my ...
1
vote
0answers
92 views

Integral Farkas Lemma

The context of this question is commutative algebra, however the question itself is more related to convex geometry. All necessary information is given. In the proof of Lemma 3.1.1 in the book ...
1
vote
1answer
47 views

Minimise Total $x$, Maximum $x$ or $|x|$ in integer/linear programming

Suppose we have a linear program (it may be integer, it probably doesn't matter). Suppose the variables $t_j$ give the tardiness for job $j$, and we want to minimise something to do with this ...
0
votes
1answer
141 views

Maximize $ax + by + c$

Working on a problem of comparative advantage of the economist David Ricardo, I've gone into solving a more general case of that study in which I stumbled over this question : how do we maximize the ...
0
votes
1answer
518 views

feasible region of a linear programming problem convex and concave

will the feasible region of a linear programming problem with linear mathematical relations and linear constraints, always be a convex polygon? will concave feasible regions have optimal value at ...
1
vote
1answer
92 views

Solving a three variable LP graphically to show a case where there is no feasible solution

John will spend £5 of his Christmas money on plain and milk chocolates. He can buy boxes at £2 each. These contain 25 plain and 25 milk chocolates. He can buy single plain chocolates ...
0
votes
2answers
658 views

Minimizing the sum of absolute values with a linear solver

I need a linear program to minimize the sum of several absolute values, but the inclusion of an absolute value means the linear solver won't work. I know there are ways around using an absolute value, ...
1
vote
1answer
176 views

Fitting Vogel's formula for phyllotaxis to an actual plant.

A simple model for the arrangement of florets in a sunflower was given by Vogel: $r = c\sqrt{n}$ $\theta = 137.508 n$ Where $r$ and $\theta$ are polar coordinates, $c$ is some constant and $n$ is ...
0
votes
1answer
121 views

How to enforce a constraint that a decision variable can only take 1 of $k$ integer values?

How would you enforce the constraint that $x$, a decision variable, can only take values -3, 7, or 19? I think I probably need to introduce a binary variable here but not sure where to start. Thanks. ...
2
votes
0answers
188 views

Is simplex method weaker than other methods?

Given linear program: $$ \text{min } x_1 - x_2 + 2 x_3 $$ s.t.: $$ -3x_1 + x_2 + x_3 = 4 $$ $$ x_1 - x_2 + x_3 = 3 $$ $$ x_i \geq 0; i = \{1,2,3\} $$ solution by simplex method (with double pass) is ...
0
votes
2answers
2k views

Solving a 2*3 game with graphical method in game theory

Solve the following game. $$ \begin{pmatrix} 1 & 2& 3 \\ 4 & 2 & 1 \\ \end{pmatrix} $$ Since this is a $2\times3$ matrix I used the graphical method ...
0
votes
1answer
57 views

Designing an algorithm to determine if a linear combination of k-1 sets is contained in the k-th set .

I am trying to solve the following problem - given $k$ sets : $A_1,A_2,...,A_k$ containing $O(n)$ integers each I need to design an algorithm that will determine if there is such a group of elements ...
3
votes
1answer
232 views

Solving special boolean equation set

I have boolean equation sets that look like this (where ^ means xor): eq 1: x1^x3^x5^x6^x9^x10^x11^x13^x17^x18 = 0 eq 2: 1^x1^x3^x10^x12^x17 = 0 eq 3: 1^x2^x3^x5^x8^x10^x14^x16 = 0 ...
0
votes
1answer
181 views

Linear programing: Multiple slack variables

I have to convert folloving problem: $$ min\{|x_1| + |x_2| + |x_3|\ |\ \text{conditions..}\} $$ to linear program (if it is possible). Since $|x_1| = max\{x_1,-x_1\}$, i have: $$ x_1 \leq z_1 $$ $$ ...
0
votes
2answers
87 views

A linear programming to obtain “canonical basis of convex cone”

In my research a I need to solve the linear equation (getting its null space) under some constraints. The matrix is given below: The constraints shall be (x1...x[16]>0, x[17]...x[20] arbitary...) ...
2
votes
0answers
82 views

Higher dimensional Euclidean geometry problem

In my engineering/physics research, I am facing one math problem which I believe should be well established in mathematics... I have a linearly spanned space given by the column vectors of the ...
0
votes
0answers
256 views

linear program-Simplex method-Dual problem

At an exercise I am asked to solve a linear program using the simplex method(in Matlab).Then I have to formulate the dual of this problem and read off an optimal solution of the dual problem from the ...
2
votes
1answer
99 views

How to show two linear programs are equivalent?

We know that 1-norm is defined as $\|v \|_1 = |v_{1}| + \dots + |v_{n}|$ for the vector $v = \left(v_1, \dots, v_n\right)^T$. Suppose we have program (a) $$ \min\limits_{x} \|Ax-b\|_1 $$ and ...
4
votes
1answer
102 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
87 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
543 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
61 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
1answer
525 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
180 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
98 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
247 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
117 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
79 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
308 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
46 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
70 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
209 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
316 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
30 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
35 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 ...