Questions tagged [linear-programming]
Questions on linear programming, the optimization of a linear function subject to linear constraints.
5,216 questions
-2
votes
0
answers
42
views
Linear Programming Exercise [closed]
A company has 2 factories $U_1$ & $U_2$: the factory $U_1$ has $500$ units of a certain product and the factory $U_2$ has $300$ units of the same product. The company has three customers $E_1$, $...
0
votes
0
answers
17
views
How to represent a standard linear program (LP) as a semidefinite program (SDP)?
I'm trying to understand how to express a simple LP in the standard semidefinite programming (SDP) form.
In particular, consider the following linear program:
$$
\begin{aligned}
\min_{x_1, x_2} \;&...
- 241
1
vote
1
answer
73
views
Span of integer valued elements in $\ell_1(\mathbb{N})$
Consider the real Banach space $\ell_1(\mathbb{N})$, further denoted just $\ell_1$, consisting of all functions $x: \mathbb{N}\to\mathbb{R}$ such that $\|x\|:=\sum_{n=1}^\infty |x(n)|<\infty$, ...
- 828
2
votes
1
answer
88
views
Simplex Method - How to know which basis to choose after the first iteration?
I'm trying to understand how to correctly choose the next basis after the first iteration in the simplex method.
In my problem, I have the following minimization form:
$$
\begin{aligned}
\min z &= ...
- 241
1
vote
1
answer
47
views
Linearization Question for max-min|x| Bi-level Optimization Problem
I'm currently working on a bi-level optimization problem with the following structure:
max min |x|
I attempted to linearize this problem using the following approach:
Introduce an auxiliary variable ...
- 13
0
votes
0
answers
43
views
Book proves Weak Duality using Strong Duality and proves SD using WD ? Circular argument?
The proof of weak duality in my book starts with arguing that $p_i$ and $a_i' x -b_i$ have the same sign (and analogously that $x_j$ and $c_j - p' A_j$ have the same sign).
This observation is based ...
- 1,369
4
votes
1
answer
275
views
Winnability of an urn-ball game with restricted two-urn moves
My question is about a certain combinatorial game. The game works as follows. We have $n$ urns, each of which contains $m$ balls, where $m$ and $n$ are positive and satisfy $m < n$. A move consists ...
- 728
0
votes
0
answers
46
views
How to see $x_1\geq 0$ in the primal implies $p' A_1 \leq c_1$ in the dual, when there are no other constraints than just $x_1\geq 0$?
I understand why the constraint $x_1 \geq 0$ in the primal, implies $p'A_1 \leq c_1$ in the dual in the presence of a constraint involving an $A$ and a vector $b$ in the primal ($A_1$ being the first ...
- 1,369
0
votes
0
answers
18
views
Fourier-Motzkin Elimination for Single Vertex Computation
Given a convex polytope $P = \{ x \in \mathbb{R}^n \mid Ax \leq b \}$, I want to know whether we can use Fourier-Motzkin elimination (or an adaptation therefore) to compute one vertex of $P$ (or to ...
- 1
0
votes
1
answer
68
views
Book from Bertsimas suddenly switches from $(m+1)$ basic points to $m$ basic points in a problem that requires $(m+1)$ basic points
In the section $3.6$ of the book Introduction to Linear Optimization (Bertsimas and Dimitris), the column geometry of the simplex method is explored.
It starts with the fact that any bounded ...
- 1,369
0
votes
1
answer
98
views
How many big and small marbles are not used?
Translating to English from a non-English physics book about measurements:
Anif has $8$ big marbles and $15$ small marbles. The weight of the big and small marbles are $37.5$ and $12.5$ respectively. ...
- 2,501
2
votes
0
answers
23
views
Does the Interior Point Method Solve Klee-Minty Cubes adversarial instances in Polynomial Time?
I am a network engineer currently studying optimization problems. Out of curiosity, I was fascinated by the fact that the Simplex Method has an exponential worst-case complexity, a property famously ...
2
votes
0
answers
35
views
Understanding changes in a polyhedron structure when there are perturbations on the restrictions vector
I have the polyhedron
$$ P := \left\{ {\bf x} \in \mathbb{R}^{\binom{n}{k}} : {\bf A} {\bf x} = {\bf b} , \hspace{0.3em} {\bf 0} \leq {\bf x} \leq {\bf 1} \right\} $$
where the matrix ${\bf A} \in \...
- 33
1
vote
0
answers
25
views
When do linear constraints form a compact? [closed]
Given a list of constraints
$$
F_i = \{ x\in\mathbb{R}^n\mid L_i(x) \leq c_i \}
$$
where $L_i\in L(\mathbb{R}^n,\mathbb{R})$ and $c_i\in\mathbb{R}$ for every $i\in\{ 0,\dots,m \}$ with $m \geq n$, ...
- 123
0
votes
1
answer
49
views
Reference request: The formal definition of equivalent optimization problems.
I'm reading some materials in LP, where someone states that every LP is 'equivalent' to its standard form:
$$ \mbox{minimize } \ c^Tx, \mbox{ subject to } Ax=b, x\geq 0$$
by adding some slack ...
- 1,840