# Questions tagged [linear-programming]

Optimization with a linear objective function, subject to linear equality and linear inequality constraints.

310 questions
Filter by
Sorted by
Tagged with
46 views

### Linear Programming Problem - what is feasible size for solution on a PC

I need to get feeling for the feasible size of a LPP, that can be solved on a PC. Say, its a good one (8 cores @ 3+GHz, 64GB RAM). We also assume that number of variables is close to the number of ...
37 views

### In a LP problem Ax = b, how to solve for A instead of x?

I have a multi-objective linear programming problem of the form Ax = b, where A is a matrix and x and b are vectors. x is known, and I'm looking to minimise each row of b by solving for A. Constraints ...
36 views

### Converting If-else integer equation to Linear Programming

I have an if-then-else condition with three binary variables A, B and C: if A + B = 1 then C = 0 How do I express this as an integer linear program with equality ...
33 views

### Gaussian Elimination: Check an assignment

This question is similar to Check if a row is in the span of a matrix Suppose I have a matrix $M$ over $GF(2)$ with rows that represent a system of linear equations: A xor B xor C = 1 A xor B xor ...
29 views

### more than one min cut in a net flow

I know the answer to the question, but I still can't understand. I have the max flow and I need to determine whether there is more than one min-cut. I know that I need to run BFS from s in the ...
30 views

### Writing a linear program to model balanced bin packing

Say we want to write a (MI)LP to model the following problem: Find a parking plan for a set of cars $K=\{1, ..., k\}$ with lengths $\lambda_i$. Parking is organised in lanes $P=\{1, ..., p\}$. ...
28 views

### Looking for fast LP solver algorithm for my Special case

I am interested to know what is the fastest algorithm (complexity wise) known to us to solve the following linear program. Due to its simplicity, I hope for a very fast algorithm. Your help is greatly ...
14 views

18 views

### Why maximum-matching algorithm falls into the category of fill-reducing algorithms?

My understanding is that "maximum matching" (or "maximum transversal") are algorithms to pre-order matrix to increase the numerical stability. In Timothy Davis' book Direct Methods for Sparse Linear ...
41 views

### Determine aproximation factor in a greedy algorithm

Suppose we have n food dishes associated to a cost c, and we have i guests such that each one of them has a certain number of preferences. We want to choose a menu such that we minimize the cost and ...