A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Questions tagged [linear-programming]

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

3,588 questions
Filter by
Sorted by
Tagged with
68 views

### Maximum number of vertices a polyhedron can have?

During my linear programming class we saw this theorem: Theorem: Let $A \in \mathbb{R}^{m \times n}$ where $\operatorname{rank}{(A)} = m \leq n$ and let $b \in \mathbb{R}^m-\{\bar{0}\}.$ Then ...
30 views

### Dual linear program in electric circuit

There are explanations of dual linear programs in terms of economics like Farmer example on Wikipedia. In a book Ten lectures on statistical and structural pattern recognition I've found a real-world ...
31 views

46 views

### Travelling salesman problem visiting different nodes different times [closed]

Hi I am trying to solve a more complicated travelling salesman problem (shortest path visiting all nodes in a directed graph), where (1) I need to revisit different nodes for different times, (2) I ...
57 views

### Linearize a constraint

I have intermediate knowledge of optimization and mathematical modeling I have this constraint. I know how to model it with integers (which leads to a mixed-integer linear program). However,I was ...
127 views

32 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)....
188 views

### Simplex method can't solve assignment problem?

The problem: I am trying to solve http://acm.timus.ru/problem.aspx?space=1&num=1076 , it's an online judge for programming problems. The problem could be solved by a simple application of an ...
17 views

### Runtime of source with varying resource consumption

This question is regarding a simple problem, which can be posed for different physical situations. I am posing for a particular physical situation, but the idea is to exposit the general mathematical ...
112 views

### Linear Programming and graphing (Mathematics in thw Modern World)

I need help with the #1 question. linear Programming is applied. 1. Consider the recipes below: ...
30 views

### Why do the conditions have to be smaller than in linear programming?

The basic problem in linear programming is: max $c^Tx$ $Ax \leq b$ $x \geq 0$ But why does the condition have to $\leq$ instead of $\geq$ ? In fact, when considering the dual problem, it ...
19 views

### relaxation of vertex enumeration problem?

The vertex enumeration problem is to find the vertices of a set defined by a set of inequalities $\{x \in \mathbb{R}^n: Ax \le b\}$. It is an open question whether, if this set is known to be bounded, ...
14 views

### finding coefficient of “Max Z = $ax_1 + bx_2 + cx_3 + dx_4 + ex_5$” given a similar constraint?

I was given a primal problem as follows: Max Z = $ax_1 + bx_2 + cx_3 + dx_4 + ex_5$ Subject To: $a_1x_1 + b_1x_2 + c_1x_3 + d_1x_4 + e_1x_5 \geq F$ $a_2x_1 + b_2x_2 + c_2x_3 + d_2x_4 + e_2x_5\geq G$...
133 views

### Simplification of a min-max problem

I have an optimisation problem to solve. The book I'm following says that the original problem can be rewritten in a simpler way by observing that one of the unknowns is a subset of the $Y-1$ ...
28 views

### Optimizing a linear sum under a system of linear constraints, does this identify legit subproblems?

A legit subproblem of a problem is loosely defined as a smaller sized problem than the original input, but if you solve this smaller problem first, then the original input becomes easier to solve ("...
28 views

28 views

### LP Problem Formulating

Gotham Motor Oil Company has three warehouses which it can ship products to its three retail outlets. The demand in cans for the product Super Blend is 100 at retail outlet 1; 250 at outlet 2; and 150 ...
35 views

### Trying to Determine if an Optimal Solution from an LP Solver is Indeed Optimal

Suppose we have the following LP problem: $$min\ C^Tx$$ $$s.t. \ Ax = b$$ $$x>=0$$ I am trying to confirm that an optimal solution $x^*$ obtained from an LP solver for such a problem is optimal. ...
65 views

### How to get linear or polynomial approximation of $\frac{1}{1-e^{-x}}$?

In mathematical program, one of the constraint has $\frac{1}{1-e^{-x}}$ term which can't be solved by the linear/quadratic solver. Can someone please provide a way to represent this term as a linear ...
56 views

### What linear programming problem do I have? [closed]

I have a number $W\in\mathbb{R}$ and a vector $w=\left[w_1,\dots,w_n\right]^T\in\mathbb{R}^n$ such that each $w_i=i\cdot g$ where $g=const$. Usually $n\leq4$. The goal is to find a vector \$c=\left[c_1,...