Questions tagged [linear-programming]

Question 1

Farkas Lemma: Let $A$ be an $m \times n$ matrix, $b \in \mathbb{R}^m$ and $$F = \{x \in \mathbb{R}^n: Ax = b, x \ge 0\}.$$ Then either $F \ne \emptyset$ or there exists $y \in \mathbb{R}^m$ such that ...

Question 2

In linear optimization, a solution that is not feasible can be so because it violates an equality constraint, isn't it? Be it an equality constraint from a non-standard polyhedron or an equality ...

Question 3

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} \;&...

Question 4

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$, ...

Question 5

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 &= ...

Question 6

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 ...

Question 7

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 ...

Question 8

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 ...

Question 9

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 ...

Question 10

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 ...

Question 11

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 ...

Question 12

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. ...

Question 13

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 ...

Question 14

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 \...

Question 15

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$, ...

Stack Exchange Network

Questions tagged [linear-programming]

How to find Farkas certificates?

Case where infeasibility comes from $Ax=b$ unmet in standard polyhedron not handled in this proof?

How to represent a standard linear program (LP) as a semidefinite program (SDP)?

Span of integer valued elements in $\ell_1(\mathbb{N})$

Simplex Method - How to know which basis to choose after the first iteration?

Linearization Question for max-min|x| Bi-level Optimization Problem

Book proves Weak Duality using Strong Duality and proves SD using WD ? Circular argument?

Winnability of an urn-ball game with restricted two-urn moves

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$?

Fourier-Motzkin Elimination for Single Vertex Computation

Book from Bertsimas suddenly switches from $(m+1)$ basic points to $m$ basic points in a problem that requires $(m+1)$ basic points

How many big and small marbles are not used?

Does the Interior Point Method Solve Klee-Minty Cubes adversarial instances in Polynomial Time?

Understanding changes in a polyhedron structure when there are perturbations on the restrictions vector

When do linear constraints form a compact? [closed]

Hot Network Questions