# Questions tagged [linear-programming]

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

304 questions
Filter by
Sorted by
Tagged with
15 views

### Scheduling problem with performance based selection

I would like to solve a scheduling problem where, I am able to maximize the number of consecutive shifts a employee may have, therefore minimizing the likelihood of them not showing up for a single, ...
155 views

### 2-approximation edge-cover algorithm using primal-dual method

The problem Given an undirected graph $G=\left(V, E\right)$ and positive edge weights $w_e$, design a 2-approximation algorithm based on the primal-dual principle. So far I managed to represent the ...
59 views

### Adding linear constraint to continuos LP to improve performance

Consider a standard LP minimization problem of the form $$\begin{array}{ll} \text{minimize} & c^\top x\\ \text{subject to} & A x = b\\ & x \geq 0\end{array}$$ Should I expect, on average,...
252 views

### Warm starting LP solver at non-basic feasible solution

I'm approaching some continuous optimization problems by considering discrete approximations of them at different resolutions. Those discrete approximations can be solved with linear programming ...
4k views

### Converting if-then-else condition to integer linear programming with equality constraints

I have an if-then-else condition with three binary variables $A$, $B$ and $C$: if A = 1 then B = 1 else B = C How do I express this as an ...
66 views

### Debugging the issues on Megiddo's algorithm

I have done code for the algorithm to obtain the Optimal Basis but as I calculate the optimal solution $Xb=B^{-1}b$, I only get the correct value for some of the variables. For some variables, $Xb_i$ ...
258 views

### Maximize pairings subject to distance constraint

I have a list of people's locations on a world map and want to pair nearby people up such that the number of pairs is maximized. For example, subject to the constraint that paired people are within ...
87 views

### Simplex algorithm experimental complexity

For a school project I am doing on linear programming, I've implemented the simplex algorithm in Python. I was hoping to check the complexity on a number of matrices. Preferably, they would have ...
109 views

### Transform Standard-Dual program to Canonical-Dual program

Say I have the following Standard-Dual linear program: $$max<\vec b, \vec y>$$ $$s.t.:A^Ty \le \vec c$$ $$\vec y \ge \vec 0$$ Is there a way to transform it to a Canonical-Dual and equivalent ...
67 views

### Column Generation - Worst dual bound when adding various columns per iteration

I'm implementing a Column Generation algorithm. The pricing problem, in general, find more than one column with negative reduced costs(the master is a min problem). If i add only the most negative ...
138 views

### Simplest linear programming solver? [closed]

In a programming contest I've encountered a problem which is for sure a linear programming problem. I know quite a lot about LP (the simplex method, its exponential complexity, interior point methods, ...
169 views

474 views

### Minimum spanning tree formulation as integer program

The minimum spanning tree problem can be solved in polynomial time via Kruskal's or Prim's algorithm. However, every integer program I have seen that corresponds to the MST problem require a ...
852 views

### Is knapsack a Linear Programming problem? [closed]

Since Knapsack give Optimal solution as LP so is it also a LP or not ?
165 views

### Why is my Forrest-Tomlin update worse than recomputing LU?

I wrote a simple C++ implementation of the revised simplex method that recomputes the LU decomposition of the basis from scratch on each iteration. I have to solve problems with many variables but few ...
6k views

68 views

### Minimum covering problem formulation

Shouldn't I post this question on mathematics.stackexchange.com? Let be an airlaine company which has to affect its aircrew to several flights. We group som flights in subset, every flights of a ...
268 views

### Given 2 sets of n points: minimize sum of traveled distances

I am given two sets $S, T$ each of $n$ points in $\mathbb{R}^k$, I want to find a bijection $a : S \rightarrow T$, such that $$\sum_{s \in S} d(s, a(s))$$ gets minimized, with $d$ being the Euclidean ...