# Questions tagged [linear-programming]

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

3,592 questions
Filter by
Sorted by
Tagged with
1k views

### Lemke-Howson pivoting in degenerate bimatrix games

I'm working on an implementation of the Lemke-Howson algorithm for finding Mixed Nash Equilibria of bimatrix games, and I'm running into a roadblock when the algorithm is fed a degenerate game. For ...
2k views

### When change making problem has an optimal greedy solution?

A well-known Change-making problem, which asks how can a given amount of money be made with the least number of coins of given denominations for some sets of coins (50c, 25c, 10c, 5c, 1c) will ...
133 views

### Above what order of magnitude a pure cutting-plane algorithm must be forgotten in favour of branch-and-cut?

Crawling the web on the subject of the cutting-plane algorithm, I have seen everywhere that a pure cutting-plane method cannot be used for numerical instability reasons after some iterations. But do ...
569 views

### Help with formulating a linear programming problem

I have the following linear programming problem I would like to be verified: I have sketched the problem in the following picture: Here is my attempted solution: I figured that I have ten ...
3k views

### Linearizing min function Problem

How can I linearize $\min(x_1,x_2,x_3)$ in a maximization linear programming problem? Please help me. I've tried many things but I didn't solve.. My LP equations are as follows: Objective function is:...
10k views

### What does basic solution mean?

Linear programming: basic solution? If the matrix consists of $$\begin{bmatrix}1&-2&0&0&0\\-3&6&1&3&0\\0&0&2&6&-1\end{bmatrix},$$ how is it that there ...
1k views

### Developing Constraints for a linear programming based problem

Recently, I thought of developing a mathematical approach to a task I commonly do every week. Simply enough, it's a schedule. That said, I have a few questions regarding the process. I haven't ...
2k views

### Regarding complementary slackness condition

I have a question regarding complementary slackness, the answer should be true of false. The complementary slackness conditions connect pairs of optimal basic feasible solution of primal and dual ...
4k views

9k views

### What is the meaning of an “objective function” and “objective functionals”?

Right now I am in front of these expressions objective function objective functionals which seem to be very often used, but I've still not understood their meanings.
105 views

### Mappings preserving convex polyhedra

It is known that linear mappings between euclidean spaces map convex polyhedra to convex polyhedra. Can you give a characterization of the class of mappings that preserve convex polyhedra?
Do you know a proof for the fundamental theorem of linear inequalities, which does not employ an implicit use of the simplex algorithm? Let $a_1, \dots, a_n, b \in \mathbb R^m$. Then either $b$ is a ...