# Questions tagged [linear-programming]

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

1,628 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2k views

### Determining information in minimum trials (combinatorics problem)

A student has to pass a exam, with $k2^{k-1}$ questions to be answered by yes or no, on a subject he knows nothing about. The student is allowed to pass mock exams who have the same questions as the ...
1k views

### Blotto game variation

My smart friend ZWX challenged me to solve the "brainteaser" below, but to my surprise, the problem seems highly nontrivial as I took a closer look. Anyway, the question goes: In a game, both you ...
796 views

### Solving $Ax = b$ for non-negative $x$ given boolean matrix $A$ and non-negative $b$

I am trying to solve $Ax = b$ with the following properties: $A$ is a boolean (aka. logical, binary) matrix, i.e., each entry in $A$ is either $0$ or $1$ $A$ is of size $m \times n$ where $m \ll n$ ...
899 views

986 views

55 views

### Shortest Path Problem Minimization

I am asked to formulate shortest path problem as a min-cost flow problem. The textbook I am using is Gentle Intro to Optimization where it states the max netflow model for graph G with s, t ...
83 views

### On the Fundamental theorem of Linear Programming

A proof from An Introduction to Optimization By Edwin Chong and Zak Theorem 15.1 Fundamental Theorem of LPP. Consider a linear program in standard form. If there exists a feasible solution, then ...
800 views

### Prove that a convex polytope has finitely many extreme points.

$a)$ Prove that a convex polytope has finitely many extreme points. $b)$ Prove that the unit disc $S:=\{x\in\mathbb{R}^2:x_1^2+x_2^2\le1\}$ is not a convex polytope. Hint : what are the ...
94 views

### Showing a disc has infinitely many extreme points

EDIT: Stuck on a part of a problem for a Linear programming course. I want to show the unit disc is not a convex polytope and my strategy is to show that it has infinitely many extreme points. How ...
151 views

### Determining if a Vector is a member of a Convex Hull

Edit: Here is how the following sets are created: $S$ is the set of all $n$-dimensional, multilinear trinomials that are strictly greater than $0$ on the interval $[0,1]^n$. $T$ are all miltilinear ...
38 views

### Inverting Linear System of Inequalities

I have $6$ integral variables, $m,z,p, m',z',p'$. I have a set of three inequalities: $$m\leq m' \leq p+m$$ $$m \leq m'-z' \leq p+m$$ $$2p+2m+z \leq 2m'+p'\leq 2p+2m+z$$ (The last one is an equality)....
28 views

### linear program, why is there an outgoing arc such that $d(s,v) = w(s,v)$

If any other information is needed, please feel free to ask me. I'm beginning my learning in graph theory and in optimization. Let's call $D = (V,A)$ a directed graph. $w : A \to \mathbb R$, arc ...
96 views

### Reducing the Eulerian cycle problem in a mixed graph to a maximum flow problem

I'm completely stuck on this one. The obvious resemblance between the two that I see is that every vertex needs to have the same amounts going in and out, in the Eulerian cycle problem the amount is ...
53 views

### How to quickly determine if a linear program is feasible?

I have a series of linear programs in canonical form $$\begin{array}{ll} \text{maximize} & c^T \mathrm x\\ \text{subject to} & A x \leq b\\ & x \geq 0\end{array}$$ and I need to ...
97 views

### Why does the Canonical Form of linear programming have non-negativity?

Aren't the non-negativity constraints special cases of the general constraints? Isn't $$x_1 \ge 0$$ just $$-1 \cdot x_1 + 0 \cdot x_2 \le 0?$$ Then you could just summarize the general form of ...
145 views

### Can I obtain a unitary block matrix from any invertible matrix?

Suppose A is any square invertible complex matrix. Then $$C = \left[ \begin{array}{c|c} 0 & A \\ \hline A^{\dagger} & 0 \end{array} \right]$$ is a Hermitian matrix. My Question: Is ...
154 views

### Finding a point with maximum distance from a given point in a polyhedron

We are given the polyhedron $X=\{x:Ax\le b,x\ge 0\}$ and the point $y\in X$. We want to find a point $x \in X$ such that $d(x,y)$ is maximized. The function $d(x,y)$ represents the distance between ...
118 views

178 views

### Existence of solution of linear system with equality and inequality constraints

Given matrices $A$ ($n \times k$) and $C$ ($m \times$k), and vectors $b$ and $d$, I want to know if there is a value of $x$ that solves the two constraints below: \begin{array}{c} A x = b \\ ...
528 views

### Correctness of the artificial constraint method (dual simplex)

The artificial constraint method is used to find an intial basis to start executing the dual simplex algorithm to solve a linear programming programming problem (say we want to minimize $c^tx$). The ...
85 views

### Convex Polytope

My Linear Programmation book tells me to consider the closed and limited Convex Polytope defined as $$S=\left \{ \right.\bar{x}:A\bar{x}=\bar{b} ,\bar{x}\geq 0\left. \right \}$$ But , does this ...
93 views

### actually USING the lagrangian dual to solve a problem

I don't get the maximisation bit in the dual problem... Let's consider the standard form LP: minimise $c^\top x$ subject to $Ax = b, x \geq 0$ This has lagrangian \mathcal{L} = c^\top x +...
116 views

### How to linearize a not linear program with excel?

I want to use Excel solver to solve the following integer linear program: A company wants to select $p$ locations among a set of $m$ possible sites for constructing polluting plants in a ...