All Questions
5 questions
2
votes
0
answers
266
views
Inclusion of polytopes
Consider the following two system of linear (in)eqaulities:
$S = Ax \leq b;\; Cx = e$
$T = Dx \leq d;\; Gx = g$
How can I check if $S\cap \neg T=\emptyset$ where $\neg T$ is the complement of the ...
- 253
-5
votes
1
answer
320
views
Solving a system of linear inequations
Consider the following system of inequalities:
$Ax=b$;
$x\geq 0$;
A is a $m\times n$ (non-square) and sparse matrix in which some part of entries are rational. a) How feasibility of this system can ...
- 253
9
votes
1
answer
643
views
Efficiently solve a system of strict linear inequalities with all coefficients equal to 1 without using a general LP solver?
Per the title, other than using a general purpose LP solver, is there an approach for solving systems of inequalities over variables $x_i, \ldots, x_k$ where inequalities have the form $\sum_{i \in I} ...
- 747
9
votes
2
answers
692
views
Midpoint solutions to linear programs
There is a linear program for which I want not merely a solution but a solution that's as central as possible on the face of the polytope that assumes the minimal value.
A priori, we expect the ...
- 1,226
10
votes
1
answer
502
views
Finding a cutting plane that splits a polyhedron evenly
Say we have a polyhedron in standard form:
\begin{equation*}
\begin{array}{rl}
\mathbf{A}\mathbf{x} = \mathbf{b} \\\\
\mathbf{x} \ge 0
\end{array}
\end{equation*}
Are there any known methods for ...