# Questions tagged [linear-programming]

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

3,591 questions
Filter by
Sorted by
Tagged with
390 views

### weak duality theorem

Studying duality theory I have not found clear this point considering the primal a minimize problem, if $x$ and $p$ are feasible solution to the primal and to the dual then $p^tb \leq c^tx$ for ...
3k views

### Finding the minimal cost edge cover for a bipartite graph

I have got two sets of elements and a pruned graph of bipartite edges with weights assigned to each edge. I need to find the minimal set of edged with the minimum cost covering all nodes from both ...
2k views

### Proving Helly's theorem

The problem is to prove Helly's theorem for the case, when the convex bodies are polytopes, by using linear programming duality. Helly's theorem Let $B_{1},...,B_{m}$ be a collection of convex ...
228 views

### Book recommendation to study topics of Linear Programming for self study

I need some reference book suitable for self-study with many solved examples and solutions preferably for exercise questions for following study. Need basic honours undergraduate level text , ...
234 views

### Max $P= 7x + 5y + 6z$ Subject to: $x + y − z ≤ 3 x + 2y + z ≤ 8 x + y ≤ 5 x ≥ 0, y ≥ 0, z ≥ 0$

Linear programming problem using the simplex method. Max $P= 7x + 5y + 6z$ Subject to: $$x + y − z \le 3 x + 2y + z \le 8 x + y ≤ 5$$ $x \ge 0, y \ge 0, z \ge 0$ My try: I know how to solve ...
5k views

### primal to dual solution conversion ??

i have an optimization problem $$\text{ maximize } z=3x+4y$$ $$\text{ such that: } x+y ≤ 450 \text{ and } 2x+y ≤ 600$$ the optimal solution to this problems comes to be $x=0$; $y=450$; $p=150$ (...
3k views

### How to solve system of equations with multiple constraints?

I have a system of equations that looks like this: $$\begin{array}{rl} a_1 b_1 c_1+a_2 b_2 c_2+a_3 b_3 c_3&=1000\\ a_1+a_2+a_3&=1\\ a_2&=0.6 \,a_1\\ b_1+b_2+b_3&=500 \end{array}$$ ...
34 views

### Rigorous global optimization

The work by Thomas Hales (see enter link description here) before the formal proof solves a number of global optimization problems that need to be solved exactly. The strategy relies on following ...
36 views

### Orders of coordinates in a linear subspace

Let $X$ be a linear subspace of $\mathbb{R}^n$. For how many permutations $p$ on ${1,...,n}$ does there exists $x$ in $X$ with $x_{p(1)} < x_{p(2)} < ... < x_{p(n)}$? We can test each ...
75 views

49 views

554 views

1k views

### Simplified nurse scheduling problem

I'm currently handling a project with a problem that is very similar to nurse scheduling problem in many respects. It is a part time workforce scheduling system whereby we need to determine which ...
2k views

### Find a nonnegative basis of a matrix nullspace / kernel

I have a matrix $S$ and need to find a set of basis vectors $\{\mathbf{x_i}\}$ such that $S\mathbf{x_i}=0$ and $\mathbf{x_i} \ge \mathbf{0}$ (component-wise, i.e. $x_i^k \ge 0$). This problem comes ...
186 views

### Membership problem for convex cones

Does anyone have a reference for the most efficient or some simple reasonably efficient algorithm for the membership problem for convex cones: Given a finite set of vectors $v_1, ..., v_n$ and a ...
974 views

406 views

### Equivalence of a binary linear program and its relaxation

We know that given a binary (0-1) linear program, we can find lower/upper bounds using its relaxation. But, there are instances (such as shortest path problem with non-negative cycles, bipartite ...
398 views

### What formulation for any 0-1 knapsack problem has the tightest LP relaxation?

Since the knapsack problem with integer variables can be reduced to a binary variable case, consider the problem $$\max\{cx:x\in K\}$$ $$K:=\left\{ x\in \{0,1\}^n: \sum_{i=1}^n a_ix_i\le b \right\}$$...
Preliminaries Let us define $\mathbb{N}_n=[1,n]\cap\mathbb{N}^+$ for all $n\in\mathbb{N}^+$. $\$ A polyhedron is an intersection of halfspaces, i.e., a set of the form \$\{x\in\mathbb{Q}^n\mid Ax\le ...