Questions tagged [linear-programming]
Questions on linear programming, the optimization of a linear function subject to linear constraints.
4,630
questions
0
votes
1
answer
42
views
Is my method equivalent to my lecturers?
In lectures we were shown how to 'breakdown' a piece-wise linear function so that it can be used as part of a linear program.
Now, my lecturer wrote the function as $a=f(x)=\max(0,55x-11000)$ and in ...
- 579
0
votes
1
answer
19
views
Is $\{ x \in \mathbb{R}^2 \mid x \ge 0, v^Tx \le 1 \quad (\forall v \in \mathbb{R}^2 : \lvert\lvert v \rvert\rvert = 1) \}$ a polyhedron?
I am working on the following exercise:
Consider $$P := \{ x \in \mathbb{R}^2 \mid x \ge 0, v^Tx \le 1 \quad (\forall v \in \mathbb{R}^2 : \lvert\lvert v \rvert\rvert = 1) \}$$
Is $P$ a polyhedron?
...
- 2,462
1
vote
0
answers
8
views
Is there a result on the maximum value of the dual variable for a parametric LP in terms of the parameters of the LP?
I am working with a linear program of the following kind:
\begin{array}[t]{l}
\min c^{\top} x\\
s.t.\\
\quad A x = b\\
\quad 0 \le x \le x^{u}
\end{array}
Can I find out the upper limit of the shadow ...
- 11
1
vote
1
answer
20
views
Theorem of Alternatives proof only one of the systems is solvable
Let $ A \in R^{nxm}$, $x \in R^n$, $c,y \in R^m$ show that, either
I) $Ax=c$
II) $A^Ty=0, c^Ty=1$
is solvable
I'm completely new to the theorem of alternatives, so my attempt is:
If I is solvable ...
1
vote
0
answers
29
views
The effect that slightly increasing a variable has on the optimal solution
I am going through a past exam paper that doesn't have a mark scheme provided. I am struggling to figure out how you would do part b. Can anyone explain how you would go about getting an answer for ...
- 579
1
vote
1
answer
51
views
how can I linearize a constraint of the form sum(min(x(i),y(i))) for a linear optimisation problem?
I have an linear optimisation problem and I'd like to impose a constraint of the following form:
$∑_{i=0}^N min(x_i,y_i)≥C$
where x_i,y_i are rational numbers greater or equal to 0.
how can I ...
- 11
2
votes
0
answers
21
views
In this simplex algorithm tableau, what are the basic variables?
At some point while running the simplex algorithm, we find this tableau:
Would I be correct in saying that at this stage, our basic variables are $x_4,x_3,x_6$ as they are the only ones not equal to ...
- 579
0
votes
1
answer
57
views
Proof that markov chain equilibrium using Farkas' lemma
Given a transition matrix for markov chain $ P \in \mathbb R^{dxd} $ such that $$ P_{i,j} \geq 0,\quad
1 \leq (i,j) \leq d, \quad
\sum_{j=1 \in d }P_{i,j} $$
and $i=1,....,d$.
Let $ x_{0}$ be ...
- 27
0
votes
0
answers
22
views
How to find such a Markov matrix?
Suppose $A$ is a $m\times n$ Markov matrix, and $C$ is a $m\times k$ Markov matrix. How to decide (analytically or numerically) whether there is a $n\times k$ Markov matrix such that $AB=C$? I feel ...
- 175
-3
votes
0
answers
36
views
code a program in matlab (or python) that: [closed]
generate 10 random values from 0 to 100
Place these 10 values (in order) on the diagonal of a square matrix that we will call A.
Generate a 10x10 matrix C with random values.
In the problem, each ...
0
votes
0
answers
22
views
a set of linear constraints defines a smaller and smaller set, to what extent?
Let's say I have a set of linear constraints over $x \in \mathbb{R}^d$ in the form of $Ax \le b$.
Is there a way to know the ``volume'' of the feasible set (in the sense that every two points in the ...
- 143
0
votes
0
answers
36
views
How to graph an interval of real numbers?
Assume that intergers $m$ and $n$ satisfy $2|m|+3|n-1|\leq 7$. $m+n$ is maximum when $(m,n) = (3,?), (?,?)$ and its maximum value is $?$
given the above question the first thing i tried was ...
- 47
1
vote
0
answers
17
views
Stochastic Portfolio Optimization with Recourse
I am given the following problem from a tutorial in my course:
(Portfolio Optimization with Recourse). You have £10,000 to invest (without short
selling) in a portfolio composed of eight leading ...
- 191
0
votes
2
answers
34
views
Finding containment between convex polytopes
Given 2 polytopes, either by their H-representations: $p_1: Ax\le b, p_2: Cx\le d$, where $b,d$ are real-valued vectors, $A,C$ are real-valued matrices, or by their V-representations: $p_1 = conv(p_{...
0
votes
1
answer
27
views
Find intersection of two lines
I have two lines and i have coordinates of starting point and ending point of both lines.
I need to find the intersection point on four different case.
These are the four cases:-
From image below, I ...
0
votes
1
answer
14
views
Integer linear Programming - CVRP
I am dealing with a CVRP with multiple vehicles. I am struggling to come up with a formula for the constraint that each node with a non zero demand must be visited by one vehicle, once.
Im trying to ...
- 1
0
votes
0
answers
28
views
How to find the dual of the curve fitting
I am given the following curve fitting function:
$b(a_{i1},...,a_{in}) = \Sigma_{i=1}^{n}a_ix_i$
so that for several inputs, the output $b(a_{i1},...,a_{in})$ is approximately equal to a given value $...
- 1
1
vote
1
answer
32
views
Computing the dual of an LP with equality constraints
I am having a linear program in the form :
\begin{cases}
\min_x\ \ -5x_1 + 27.5x_2 + 4.5x_3 + 12x_4\ \ \mathrm{s.t.}\ \\ \ \\
\qquad\qquad 0.25x_1 − 2.75x_2 − 1.25x_3 + 4.5x_4 + 0.5x_5 = 0\\
\...
- 605
0
votes
0
answers
31
views
Solving a linear programming problem with 26 variables - is it possible?
I need to minimise two equations with 26 variables relative to some constraints. I am not very familiar with linear programming, but understand that it is probably the correct way to approach my ...
- 11
0
votes
1
answer
45
views
Polyhedra intersection
If $A$ and $B$ are polyhedra, how do we show that the intersection $A ∩ B$ is a polyhedron.
Does the same apply if they are both polytopes, will the intersection $A ∩ B$ also be a polytope?
The ...
- 47
0
votes
0
answers
27
views
How to assign vertices to graph to minimize total weight?
I'll preface by saying this is probably an easy question, have mercy!
We have an unweighted simple graph $G \in (V, E)$ and a complete weighted graph $K \in (V', E')$ with the same number of nodes as $...
- 33
2
votes
1
answer
33
views
Convex hull and optimal solutions
Consider the LP problem:
$max$ $3x_1 + 2x_2+x_3$
$s.t$ $3x_1 + 4x_2 + x_3 ≤ 6 $
$2x_1+x_2 + 3x_3 ≤ 5 $
$x_1,x_2,x_3 ≥0$
I have solved the problem and found that the optimal value is 6 at $x=(2,0,0)$.
...
- 47
4
votes
2
answers
169
views
one linear programming problems and solutions
we have a linear programming problem with following constraint:
$x_1-x_4 \leq -1$
$x_2-x_1 \leq -4$
$x_2-x_3 \leq -9$
$x_3-x_1 \leq 5$
$x_4-x_3 \leq -3$
I solve this question until:
$1 \leq x_4-x_1 \...
- 41
0
votes
1
answer
30
views
fractional coloring of a matroid
Given a matroid $M$, a fractional coloring $f$ is a function from the collection $I(M)$ of independent sets of $M$ to non-negative real numbers such that for any $v$ in the ground set,
$$\sum_{A\in I(...
- 2,069
0
votes
0
answers
21
views
Looking for reference for minimax solution of 2p zero-sum game, NxN choices
The game in this wikipedia section https://en.wikipedia.org/wiki/Minimax#Example, also see here at Math.SE Minimax solution for Zero-Sum Game, is easily generalized to an NxN game. Let A be an NxN ...
- 23
0
votes
0
answers
35
views
$\min\{200x+100y\}$ such that $x+3y\geq12$, $3x+2y\geq12$, $x\geq0,y\geq0$
$\min\{200x+100y\}$ such that $2x+3y\geq12$, $3x+2y\geq12$, $x\geq0,y\geq0$
Attempt. I am using the lagrangian approach to attack this problem and I know the optimal solution is $(0,6)$, but I cannot ...
- 787
-2
votes
1
answer
18
views
Duality optimisation
enter image description here
Questions. what does that symbol mean between Ax and b?
he has moved the b to Ax-b in the subject too section is this because all constraints have to be on one side ? if ...
0
votes
1
answer
28
views
On the non-sufficiency of total unimodularity of the constraint matrix in the definition of an integer polytope
Crossposted at Operations Research SE
Is there an example of an $m\times n$ integer matrix $A$ and an integer vector $b\in \mathbb {Z}^{m}$ such that the polyhedron $P := \{ x\in \mathbb {R}^{n} \mid ...
- 698
1
vote
1
answer
147
views
Point in Polytope?
Context: This question is somewhat identical to this on MathOverflow, it’s different in that it only focuses on the formula of the solution to the underlying problem.
Suppose I have a convex hull $H$ ...
- 177
0
votes
0
answers
18
views
Simplex: LP with equality constraints : do I need slack variables?
I am confused about simplex method : I have read from various resources that I need my LP to be in standard form. Then when we have the standard form, we introduce slack variables to turn inequality ...
- 605
0
votes
1
answer
22
views
Excel Solver Linear Optimization : Formula Debugging
I am trying to get a optimization model to work correctly. The background is to use the solver to find a circuit (AC or DC) that would minimize cost. I am trying to use binary variables so the ...
- 1
2
votes
2
answers
51
views
L1 Objective as a Linear Program
I am trying to determine how the following simple L1 objective can be written as a linear program:
Minimize $(\| Mx - p \|_1) + (\| Mx - q \|_1)$ wrt to $x$ such that $\| x \|_1 = 1$ and all elements ...
0
votes
0
answers
15
views
Sign of last row in tableau
In a previous exam I have the question:
The solution given is:
Can someone please explain to me why the last row in the tableau is z, instead of -z?
I'm under the impression that if I leave the last ...
- 157
0
votes
0
answers
45
views
Discrete Optimization Problem: What is the optimal course schedule?
Linda Johansen, an incoming first-year MBA student, would like to determine her course schedule for her first two semesters of business school. Linda has created a list of twenty potential courses ...
0
votes
0
answers
24
views
Primal and Dual Linear Program
Consider the linear program (P) and its dual (D)
\begin{align*}
\text{(P) minimize} &\quad \textbf{c}^T\textbf{x} &\text{(D) maximize} &\quad \textbf{b}^T\textbf{y}\\
\text{subject to} &...
0
votes
1
answer
18
views
Why is $Ax \leq b$ is equivalent to $A'x' = b'$ and $x'\geq 0$
I am getting confused in LP conversion from one form to another. Say, I have an LP of the form $Ax\leq b$ and I want to convert it into the form $A'x'=b', x'\geq 0$, how to do this?
For example let's ...
- 106
2
votes
1
answer
27
views
Equivalent representation of a system of linear (in)equalities
I am reading about the equivalence between zero-sum games and LPs from Adler's 2012 paper.
Right after lemma 3, he writes that it is equivalent to represent
$$
(\mathsf{A}) := \{x:Ax=b\} = \{x:Ax\geq ...
- 2,370
0
votes
1
answer
22
views
How can I convert non-linear constraint to linear one?
Problem: Suppose I have $n$ finished products and each product has its own completion time, such as C$_i$ (C$_i$=completion time of product $i$, where $i=\{1,2,...,n\}$). These products will be ...
- 15
0
votes
0
answers
17
views
dual of a LP constraint
Consider the minimization problem
minax1+bx2
s.t:
x1(i,j)-sum(i,x1(i,j))<=0 for each j
that both varibales in the constraint is equivalent. so what is the constraint for x in the dual problem? how ...
0
votes
0
answers
24
views
Reduce minmax problem to linear problem
A is mxn matrix, c is n vector and b is m vector.
Convert following problem to linear problem
$$max_{x \ge 0} min_{y \ge 0} (c^Tx - y^TAx + b^Ty)$$
I think I can write min to max by just changing sign ...
- 153
1
vote
1
answer
60
views
Linear Programming - Motivation behind the Dual Simplex Method
I am trying to understand the motivation behind the Dual Simplex Method. However, I have run into some roadblocks while understanding the rationale behind the Dual Simplex Method. This is my current ...
- 8,444
3
votes
2
answers
61
views
How many slack variables need to be introduced?
So I was trying to solve this exercise (from DPV book)
I modeled the problem as such:
minimize : $4x_1 + x_2 + 2x_3 + 3x_4 $ s.t:
$ x_1 + x_2 = 8 $ (Mexico's production)
$ x_3 + x_4 = 15 $ (Cansa's ...
- 605
0
votes
1
answer
20
views
two linear programs, one unbounded, one feasible and bounded
I've been biting my teeth out, trying to find an example of the following. Is it even possible?
Consider two LPs
$$
(P1) \ \max \{c^Tx|Ax\leq b, x\geq 0\} \\
(P2)\ \max \{c^Tx|Ax\leq \tilde{b}, x\geq ...
- 99
0
votes
0
answers
14
views
Linear optimization problem with affine subspaces
I have this fun linear optimization problem for you!
Let $u$ and $v$ in ${\mathbb R^n}$ be two non-collinear vectors where $\|\vec u\|=1$ and $\|\vec v\|=1$ and let $\alpha$ and $\beta$ two real ...
- 1
0
votes
1
answer
20
views
Projection onto union of two affine subsets
Let $\ C_1=\{\ x\in {R^n} \ |\ \langle u,x\rangle\leq\alpha\ \}\ $ and $\ C_2=\{\ x\in {R^n} \ |\ \langle u,x\rangle\leq\beta\ \}. $
Give the orthogonal projection of $x\in{R^n}$ onto $\ C_1\cup C_2....
- 1
1
vote
2
answers
64
views
Minimize sum of absolute value with linear constraint
Consider a minimization problem:
$$
\begin{aligned}
& \min \sum_{i=1}^n |x_i|,\\
& A x = b,
\end{aligned}
$$
where $A$ is an $m\times n$ matrix of rank $m$.
I know that the minimum points ...
- 13
0
votes
0
answers
46
views
Representation theorem linear programming
What I have read is:
The General Representation Theorem states that every point in a convex set can be represented as a convex combination of extreme points, plus a nonnegative linear combination of ...
- 1,424
0
votes
0
answers
13
views
What is a general way to find Direction of unboundedness of a linear program.
One of the way I know is Ad=0 then d is direction of unboundedness where A is the constraint matrix and Ax=b. In my exam there was question, to first convert problem into standard form, determine 2 ...
- 153
0
votes
0
answers
26
views
1-norm maximization - is this a linear program?
I have two conditional probability distributions $\tilde{Q}_{Y|X}$ and $Q_{Y|X}$ and I am trying to find the probability distribution $P_X$ that maximizes the quantity below
$$\|(\tilde{Q}_{Y|X}(y|x) -...
- 1,528
0
votes
0
answers
44
views
Summation Linear programming Problem
Im trying to solve the following problem
First I write out the objective function with t=1=October,...,4=January:
$x_t=$ no. of units produced during month t
$i_t=$ the amount of inventory at the ...
- 13