# Questions tagged [linear-programming]

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

3,587 questions
Filter by
Sorted by
Tagged with
19 views

### Proof of equivalence of definitions for a vertex of a polyhedron

In these lecture slides from Princeton University I found the following definition of a vertex of a (convex) polyhedron (p. 11). A point $x\in\mathbb{R}^n$ is a vertex of a polyhedron $P$ if 1)...
11 views

### Goal linear-programming in Matlab

$$0v_1 + 0.2v_2 + 0.4v_3 + 0.6v_4 + 0.8v_5 + 1v_6 + 0.8v_7 + 0.6v_8 + 0.4v_9 + 0.2v_{10} + 0v_{11} → 0.46$$ subject to $$v_1 + v_2 + ···+ v_{11} = 1$$ $$v_1, v_2, . . ., v_{11} ≥ 0$$ I couldn't ...
13 views

### Understanding linear optimization better?

I'm taking a linear optimization class, and I'm having a difficult time formulating an 'integer program' from a problem. My main problem is taking given information (often tables), how do I declare ...
10 views

### Using Matlab for linear programming with unknown objective function [closed]

I'm trying to find the optimal scalar (min) $u$ with an optimal vector $x\in \Re^{k}$ that satisfy: $A*x<=u*ones(d,1)$ $u>=-1$ Where A is a constraints matrix $A\in \Re^{d*k}$ and some other ...
16 views

### Hit-'n-Run Monte Carlo on convex polytope

So, I'm currently trying to implement a MCMC to uniformly sampling hyper-points from the polytope defined as $\mathbb{K}=\{x\in\mathbb{R}^{n}\;\;\text{s.t.}\;\; A\,x=b \}$ in the specific case where, ...
29 views

53 views

### Why does standard quadratic programming contain $\dfrac{1}{2}$ in the objective function?

Does the $\dfrac{1}{2}$ provide any of computation convenience?
12 views

### Algorithm to solve 'user optimum' 'polygamic' stable marriage problem: Optimally assign travellers to shared rides.

I am looking for inspiration to reformulate the classical assignment problem into something behaviourally richer (closer to Nash equilibrium or or stable marriage problem). I find it tricky to ...
61 views

54 views

### Prove that a polyhedron in the $\mathcal{H}$-representation is bounded

Given a polyhedron $P$ specified by a set of linear constraints $P=\{x \in \mathbb{R}^n \mid Ax \le b \}$, what are the conditions on the matrix $A$ such that $P$ is bounded? I have the following ...
39 views

### How to optimize in an assignment problem when the objective function is a quotient?

I know that if I had an assignment problem with an objective function that looked like this $${\max} \sum_{i=1}^m\sum_{j=1}^n c_{ij}\cdot x_{ij},$$ I could use linear programming to solve it. But ...
I'm interested in the following question: Determine if there exists a solution to linear system $A\vec{x} = \vec{b}$ that lies in region $R$. Is there a general procedure for doing so? Currently, ...