# Questions tagged [linear-programming]

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

272 questions
Filter by
Sorted by
Tagged with
69 views

### Polynomial LP-based algorithm for cost minimization of DAG weights modification

Given a DAG $G=(V,E)$, with non-negative weights $w_e \, \forall e\in E$, we want to modify (increase/decrease) the weights such that: $\forall u,v\in V$ and $\forall p_1\neq p_2$ paths from $u$ to ...
1k views

### Converting If-else condition to Linear Programming

I have a constraint in a linear programming formulation with two variables: $X \ge Y$ To which I want to apply the following if-else conditions: ...
45 views

### Using Genetic Algorithms for volatile problems

Suppose I am looking at an optimization problem with a large number of interconnected constraints, but the solution is - in some regions - extremely volatile (With volatile I mean: small mutations ...
1k views

### Does linear programming admit a strongly polynomial-time algorithm?

The linear programming problem: find a strongly-polynomial time algorithm which for given matrix A ∈ Rm×n and b ∈ Rm decides whether there exists x ∈ Rn with Ax ≥ b. I know that Steve Smale's lists ...
110 views

### Performance gain by implementing streamlined simplex

I have to solve linear transportation problems for a research project. Ideally, I should design an application that will recieve the problem data as an input and then show some results. The size of ...
151 views

### Enumeration of corner points of a polytope [closed]

Given a linear program, is there any library or available code to enumerate all the corner points of a polytope ?. PS: Simplex method finds one corner point depending on the objective, but I need to ...
39 views

169 views

### Modeling $(x > 0 \wedge y > 0) \Leftrightarrow z > 0$ in a linear program: impossible?

In this question, we see how to model boolean logic in $0 - 1$ ILPs. Moving to a relaxation, modelling $(x > 0 \vee y > 0) \Leftrightarrow z > 0$ with $x,y,z \in [0,1]$ with linear ...