# Questions tagged [linear-programming]

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

3,561 questions
Filter by
Sorted by
Tagged with
319 views

### Linear inequalities to make a specific solution infeasible

Say we have a binary linear programming problem: \begin{equation*} \begin{aligned} & \underset{\mathbf{x}}{\text{minimize}} & & c\cdot\mathbf{x} \\ & \text{subject to} & &\...
229 views

### How many ${0, 1}$ solutions would this system of underdetermined linear equations have?

The problem: I have a system of N linear equations, with K unknowns; and K > N. Although the equations are over $\mathbb Z$, the unknowns can only take the values 0 or 1. Here's an example with N=11 ...
561 views

### Sudoku mathematically, MILP?

My homework contains a word (freely-translated) "target-function" that I should generate somehow for 9x9 sudoku solver with some MILP problem. But I am bit lost what they mean. I have sofar described ...
456 views

### Sensitivity analysis on non linear problems

First of all, I would like to apologize if this question does not fit into the "soft" category. I am quite a newbie around here, and maybe I can fail to get the feeling of what exactly is a "soft" ...
2k views

1k views

### How to set up a linear programming problem?

I'm not 100% sure if I set up the following problem right. Once I have the problem set up I know how to solve it. (this is a homework problem) The problem goes like this:"A company can use plastic, ...
8k views

### Understanding proof of Farkas Lemma

I've attached an image of my book (Theorem 4.4.1 is at the bottom of the image). I need help understanding what this book is saying. In the first sentence on p.113: "If (I) holds, then the primal ...
153 views

### binary variable question

I need to make a constraint for the following condition: Student 1 can only be on the team if students 2, 3, 4, and 5 are also on the team. I'm not sure how to model this using equations. The ...
6k views

### Help with binary variable

I need to make a constraint for the following condition: Among students 1, 2, 3, and 4, at least two of them must be on the team, if there are any on the team at all. I have defined Y1, Y2, Y3, and ...
18k views

### Primal and dual solution to linear programming

Lets say we are given a primal linear programming problem: \$\begin{array}{ccc} \text{minimize } & c^{T}x & &\\ \text{subject to: } & Ax & \ge & b \\ & x & \ge & ...
8k views

### Can a non-degenerate LP have multiple optimal solutions?

In linear programming, an LP can have multiple optimal solutions if it contains degenerate vertices, i.e. where one of the base-variables is 0. Can an LP also have multiple optimal solutions if it ...
132 views

### Basic linear problem solving

I have some LP problem and I'm willing to solve it (this is an exercise from some optimization-related book). Now, Mathematica tells me that the problem is unbounded and I want to make a generic ...
48 views

### How can I adapt my problem so that it is amenable to the simplex algorithm?

According to the Wikipedia article, the Simplex algorithm depends on constraining all the unknowns to be >= 0. I have a problem where one of my variables is highly likely to be negative in many cases....
20k views

### Linear Programming Books

Do you know of a good book on linear programming? To be more specific, i am taking linear optimization class and my textbook sucks. Teacher is not too involved in this class so can't get too much help ...
1k views

### In linear optimization, what does “AP” stand for?

I am learning algorithms, and there is a chapter which uses linear optimization methods to solve a matching problem. This is the problem definition: I find the abbreviations AP for the constraints ...