New answers tagged linear-programming
1
vote
Accepted
Mutually exclusive non-zero variables in Linear Programming, without using binary variables or objective function
The disjunction $a = 0 \lor b = 0$ is nonconvex, so you cannot enforce it with linear constraints.
- 47.4k
3
votes
Accepted
Path-following methods being a 1-phase method
Consider the standard primal dual pair:
$\min c^{T}x$
subject to
$Ax=b$, $x \geq 0$
and the dual
$\max b^{T}y$
subject to
$A^{T}y+z=c$,
$z\geq 0$.
In the "infeasible" version of the primal-...
- 10.9k
2
votes
Accepted
Does LP have optimal solution provided that the coefficients and variables are guaranteed to be nonnegative?
By the Fundamental Theorem of Linear Programming, a linear programming problem is either infeasible, unbounded (which for a minimization problem means it has feasible solutions with arbitrarily large ...
- 455k
1
vote
Accepted
Chvatal-Gomory integer rounding method to find facets of $\operatorname{conv}(S)$
Here's a systematic approach that uses LP duality. First write your constraints as \begin{align}
4x_1 + x_2 &\le 28 \tag1\label1\\
x_1 + 4x_2 &\le 27 \tag2\label2\\
x_1 - x_2 &\le 1 \...
- 47.4k
3
votes
Is the duality concept in linear programming related to category theory?
Here are 3-4 such attempts :
(1) "Linear programming duality and morphisms"
Winfried Hochstattler, Jaroslav Nesetril (1999)
The title says it all
Available @ https://cmuc.karlin.mff.cuni.cz/...
- 12.3k
2
votes
Accepted
0-1 Linear programming and non-optimal multidimensional knapsack
You want to enforce the logical implication
$$x(k,e) = 0 \implies \bigvee_{i=1}^n \left(\mathbf{s}_i(k)-\mathbf{c}_i(e) \le \sum_{d\in E}\mathbf{c}_i(d)\cdot x(k,d)-\epsilon\right)$$
Introduce binary ...
- 47.4k
Top 50 recent answers are included