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

learn more… | top users | synonyms

1
vote
1answer
44 views

Minimum distance of extreme points of polyhedra

Let $P = \{x \in \mathbb{R}_{\geq0}^n \colon Ax \leq b\}$ with $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R^m}$. Let $E \subseteq P$ be the extreme points of $P$. Can anything be said about ...
0
votes
0answers
30 views

Approximation of optimum for two linear programs

Suppose you got two linear programs. They are the same except that one has a shifted objective by a positive constant (1) $$\min c^Tx$$ (2) $$\min c^Tx + d$$ For (2) there exists a ...
3
votes
1answer
35 views

Trouble seeing why this is the dual of an LP

$A$ is an $m \times n$ matrix. Using the notation $x=(x_1, \ldots, x_n)$, $z=(z_1, \ldots, z_m)$, and $y=(y_1, \ldots, y_m)$, I'm reading that if the primal LP is $$ \min 0x_1 + 0x_2 + \cdots + 0x_n ...
0
votes
0answers
16 views

Perturbation factor terminology

This is a question about usage of English. I have an inequality $a^\textsf{T}x \leq b$, where $a$, $b$, and $x$ are vectors in $\mathbb{R}^n$. Now, I want to perturb this inequality by a small amount ...
2
votes
2answers
45 views

How can I calculate if a given point is wrapped inside a pentagon?

If I have a pentagon and I know the coordinates of it's nodes, how do I calculate if a point is wrapped inside it? An example to clarify what I mean: Assume that we know the coordinates of the ...
0
votes
0answers
18 views

Name search for special Linear Mixed Integer Programm

I am looking for a name for the following question in literature! (and if you know it, then it would be great) I couldn't find it and due to wide audience here, presumably you know more. Thank you ...
0
votes
0answers
7 views

Feasability of infinite number of linear inequalities

Consider a continuous function $f:A\to\mathbb{R}^N$ for a closed interval $A\subset \mathbb{R}$. Are there suffieint or necessary conditions for the existence of a solution $w\in\mathbb{R}^N$ such ...
0
votes
0answers
36 views

Prove solution does not exist for inequalities system

I have an inequalities sytem like the following: Example > x+y+z <= A > x+y <= B > x+z > C > y+z > D > x >= E Let A,B,C,D,E be any ...
0
votes
1answer
33 views

Projection onto Polyeder

I know how to projects onto a linear subspace of $\mathbb R^3$, but how to project a point $x$ onto an polyhedron given as the intersection of three halfspaces $$ \langle y_1, x \rangle \ge c_1 ...
0
votes
1answer
33 views

Can someone explain the effects of degenerate basic feasible solutions in the simplex algorithm?

I was given this on an assignment sheet, and am now using it to revise from...I cannot remember the issues that arise from degeneracy of basic feasible solutions... Let $P$ =$\{x\in \mathbb{R}^n ...
1
vote
0answers
26 views

Why is this simplex procedure not working? $\min z = y - x + 1$

I have read of two ways to solve this program with the Simplex algorithm. One worked and the other didn't. The only difference is that, in the one that didn't work, I rewrote the function. I will ...
0
votes
1answer
10 views

Is there relations between earth mover's distance and vector norms?

Say I have two vectors $a$ and $b$. Can I estimate $\mbox{EMD}(a,b)$ via some combination of things like $\|a-b\|_p$ and such?
0
votes
1answer
12 views

Linear programming: Maximize minimum of linear functions

For a project I need something solved, it screams linear programming. If I get the problem in "standard" form I should be able to solve it using the simplex method. But I don't see how to get it in ...
2
votes
1answer
75 views

Linear Algebra 101 - Optimizing inequalities

I am considering the region contained in $\mathbb{R}^2$ consisting of all the points that satisfy all the following inequality: $-4 \leq y < 4 \\ -9 \leq 2x + y \leq 9 \\ -9 \leq x + 2y \leq 9 \\ ...
0
votes
0answers
14 views

Deterministic equivalent construction

I have a 4-stage scenario tree. At each stage , i have two branches. So in total I have 15 nodes. I solve this problem in its node-variable formulation and it takes a lot of time. Also the ...
1
vote
1answer
25 views

linear systems&normalize

suppose $f: \mathbb{R}^n \rightarrow \mathbb{R}^n$ be a linear function which can be represented by a $n \times n$ matrix. Then the jacobian of $f$ is the same as the function for $f$. But I now want ...
2
votes
0answers
20 views

The importance of the full-row-rank assumption for the simplex method

Consider a linear programming model in the usual form ready for applying the simplex method. I understand that having the constraint equations' coefficient matrix $A$ be of full row rank means not ...
0
votes
0answers
27 views

Union of all sets of optimal solutions to a perturbed linear programming problem

Please let me know if you have some ideas on how to approach this proof? I got stuck part-way through. The following linear program is a function of $\theta$, $ \begin{array}{ll} \min & c^\top x ...
1
vote
1answer
13 views

the differences and relationship between linear independent and affinely independent

When learning optimization, I heard the two related concepts on linear algebra: linearly independent and affinely independent. ...
0
votes
1answer
28 views

Linear Programming : Alternative to summation of absolutes in constraints

I am solving a placement problem, i.e. map $integers\ i\ from\ 0\ to\ 6$ to $(x_i,y_i)\ st\ 1 \le x_i,y_i\le 3$ such that : $ \sum\limits_{i=0}^6 \sum\limits_{j=0}^6 Cost(i,j)*(|x_i - x_j | + | y_i ...
0
votes
1answer
30 views

Need help with minimum cost network flow problems

Consider the tree solution for the following minimum cost network flow problem: The numbers on the tree arcs represent primal flows while numbers on the nontree arcs are dual slacks. (a) Using the ...
0
votes
2answers
40 views

Maximize $\ x+\frac32 y\ $ subject to…

I am stuck on the following problem: Consider the linear programming problem: Maximize $x+\frac32 y$ subject to $$2x+3y \le 16, \\ x+4y \le18,\\ x \ge 0,y \ge0.$$ If $S$ ...
0
votes
2answers
32 views

Game Theory - Setting Up Column Player's Optimal Stategy

Above is my question. Could someone please help me with the first part? I should be ok once I have set up the linear programming problem, but I don't even know what $x_1, x_2 \ \text{and} \ x_3$ are ...
1
vote
1answer
23 views

Linear Optimization Study Material

I've recently enrolled in a linear optimization course, and it's been a while since I've taken linear algebra. I do not yet have access to the book for the course or I would skim it to see what I need ...
0
votes
1answer
23 views

What's wrong with this linear program formulation?

You have two item factories, $A$ and $B$, and there are two clients that buy such item. Each client has a demand - the first one needs $400$, and the second $300$. Each factory has a ...
0
votes
0answers
14 views

Total Least Squares problem when some columns of data matrix have no error

I'm reading through Golub and Van Loan and they mention that to solve the total least-squares problem $(A + E)x = b + r$, where the first $s$ columns of E are zero, then we can solve the problem by ...
3
votes
1answer
30 views

Is a System of Linear Equations the Right Way to Solve This Optimization Problem?

This is kind of a high-level question, in that I'm not sure which mathematical approach might be best for solving my problem. I'm trying to automate a painful, error prone, and time consuming process ...
1
vote
2answers
40 views

What is wrong with this linear program $\max z = 3x_1+2x_2$?

I solved a linear program. It is wrong. The answer is that $(x_1,x_2) = (50,75)$ and the maximum value is $300$, but instead I am getting $(x_1,x_2) = (50,100)$ and the maximum being $350$. Why is ...
0
votes
0answers
13 views

Solving $\max z (3x_1 - x_2)$ linear program

I am trying to solve this linear programming exercise using the Simplex method. First of all, I detail every step, so it is pretty long, but the real question (the part where I'm stuck at) is at the ...
0
votes
0answers
18 views

Robust LP question using box uncertainty model

I am trying to solve this robust LP problem by writing it as a QP $$\min_x x^TSx : \mu \leq r^T x , Ax \leq b$$ Under Box uncertainty model: $$R = \{r : \| r - \hat{r}\|_\infty \leq \rho\}$$ Here ...
0
votes
0answers
17 views

Why do I have to solve a minimisation for an expanded maximisation linear program?

I'm learning about artifical variables with the Simplex method. There is an example where I'm getting a bit stuck at some point: Solving $$\max z = -2x_1 +x_2+1$$ subject to $$\begin{cases} ...
0
votes
0answers
35 views

Why does the Set Covering formulation perform worse?

For an assignment I have to allocate buses over bus trips such that all these trips are covered for a day, and minimize total costs. For this I have two different formulations, the Set Covering ...
0
votes
0answers
37 views

How to take partial derivative of summation?

This is about L$^1$ iteratively reweighted least squares. Where did the (-a$_i$$_k$) come from?
1
vote
0answers
27 views

How do we determine the saddle point in game theory?

I am a little confused of why this works. If a$_i$$_j$ is positive, row player pays the column, and vice versa. \begin{bmatrix} 3 & -5 & 6\\ -2 & 1 & 8 \\ 3 & -6 & ...
0
votes
1answer
70 views

Math Constraint Problems

This is a homework problem of mine. The professor said we can use any resource to help us solve and I cannot get up with anyone from class. Please help. I'm not looking for a direct answer, I ...
0
votes
1answer
36 views

How can I verify my linear program solutions?

I started solving linear programs with the Simplex algorithm, however it is unclear to me how can I verify my solutions. I have heard about geometrical solutions easy to check visually, but I'd ...
1
vote
1answer
18 views

What to do if the righthand of a constraint is a variable when solving Linear programs?

I'm starting to solve linear program exercises with the Simplex method. $$max \ (3x_1-x_2)$$ $$\begin{cases} x_1-x_2 \le 3\\ 2x_1\le x_2\\ x_1+x_2\ge 12\\ x_2 \le 10\\ x_1,x_2 \ge 0 \end{cases}$$ I ...
1
vote
1answer
39 views

Explicit solution of linear program: minimize $c^T x$ subject to $Ax = b$

This is the given question in a textbook I am following. I will paste the solution below which I do not understand: I am a little hazy on linear algebra theory, so I don't fully understand how the ...
1
vote
0answers
48 views

Formula for position in an upper triangular matrix

I'm currently working on the Travelling Salesman's Problem in a computer science module. I have implemented some linear programming techniques using the software lp_solve. I've ended up with an upper ...
0
votes
0answers
12 views

Linear Programming error bounds question

We have the LP problem: Maximize $P=3x+2y$ subject to $$-x+3y \leq 2+r_1$$ $$x+y \leq 8+r_2$$ $$2x-y \leq 10+r_3$$ What would be the formula for $P(r)$ in terms of $r=(r_1, r_2, r_3)$ for the ...
2
votes
2answers
45 views

Which mathematical programming method is good for solving the described problem?

I need to solve the following problem. Let's say that there are 3 clients with different time windows. For simplicity let's say that travel distance is always 10 minutes and service time is 30 ...
0
votes
1answer
10 views

Finding the corresponding constrained subspace under a over determined mapping Ax=b, where b is constrained

Suppose that $A$ is a $m\times n$ matrix with m>n, $Ax=b$, and $b$ is constrained in every component, $b_\min^i<b_i<b_\max^i$ for $i=1,\dots,m$. There should be a similar set of constraints for ...
1
vote
0answers
31 views

How to use the simplex method for linear programs?

I believe to be missing something important in the Simplex algorithm, because I can't get it to work. From what I gather, there are three steps per iteration, given a matrix for a linear program in ...
1
vote
0answers
22 views

Matrix multiplication in game theory doesn't add up? Min y^T*Ax

I'm studying game theory and something seems weird to me. My book says y is the probability of the row player and x is the probability of column player, both x and y are vectors. A = [a$_i$$_j$] is ...
0
votes
1answer
26 views

Semi-Infinite Linear Programming: Why is the infimum attained?

I have an optimization problem of the following form: $$\min c^T \lambda\\ \text{s.t. } f(x)^T \lambda \ge g(x) \text{ for all } x \in E,$$ where $E$ is an arbitrary set, $c \in \mathbb{R}^n, f ...
0
votes
0answers
18 views

Lagrange multiplier with linear constraints

See the figure below, We need to optimize $f_1$ under the constraint $f_2 \le B$. Clearly maximum and minimum are reached at the boundary points $(0, B)$ and $(B, 0)$ respectively. If we try a ...
0
votes
5answers
122 views

Ok, I know what does linear independence mean but why should I care?

I understand that for a set of vectors to be linearly independent, none of the vectors in the set should be a linear combination of some other vectors in that set. But why on earth should I care about ...
0
votes
1answer
25 views

Computation time

I am implementing a mixed-integer linear programming problem, and I am dealing with an huge number of constraints. Does anyone know what the linear relation is between the number of constraints of ...
3
votes
1answer
36 views

How to reformulate this Set covering problem?

I am trying to solve the following implementation of the set covering problem of a crew rostering problem. Here constraint (19), meant to create a 12-hour break between the different shifts taken by ...
0
votes
0answers
18 views

How to practically perform reinversion in PFI (Product Form of Inverse) Simplex.

While doing Revised Simplex using Product Form of Inverse. We have product of set of Eta Vectors(Elementary Matrix) to describe the Basis Inverse after certain number of steps in simplex. ...