All Questions
7 questions
4
votes
1
answer
866
views
When is a triangular matrix totally unimodular?
I have a {0,1}, invertible, triangular matrix, that I would like to show is totally unimodular. Are there any known results on the total unimodularity of classes of triangular matrices?
0
votes
0
answers
108
views
Solutions to matrix equations in the non-negative integers
For an integer matrix $S$, and an integer vector $y$, I'm looking for solutions to $xS = y$ where the entries in $x$ are in the non-negative integers.
I've been doing this with Sage's mixed integer ...
0
votes
0
answers
369
views
Finding a point in the relative interior of the convex hull of a set of integer-valued vectors
Let $X \subset \mathbb{Z}^n$ be the set of integer-valued vectors satisfying a system of linear constraints. We can suppose that $X$ is the set of integral points in a given polyhydral set $Y \subset \...
2
votes
0
answers
80
views
Making a polyhedron integral by selecting value for a specific co-ordinate of constraint vector
I am currently trying to solve a binary integer programming(maximization) problem, where the first row of the constraint matrix corresponds to the constraints on the total number of 1's in the vector ...
0
votes
0
answers
68
views
A seemingly easy integer programming question
Let $k, m \in \mathbb{Z}_{ > 1}$. Let $a \in \mathbb{Z}_{> 0}^m$ and $t \in \mathbb{Z}^k$. Let $\varepsilon = (\varepsilon_{i,j})_{1 \leq i \leq m \\1 \leq j \leq k}$ be a matrix with entries in ...
6
votes
1
answer
1k
views
Speed up Linear programming
I have a linear programming problem like this:
minimize $c^t X$
under the constraint that $AX \ge b$.
I will need to solve this linear programming problem online many times. I need it to be as fast ...
2
votes
1
answer
143
views
Find base of kernel with as many 0 as possible
I have a 400x132 rectangular matrix with only 0 and 1.
I am looking for the linear combinations of the columns of the matrix that sum to 0.
For example C1 + C2 - C3 = 0.
I want to find the linear ...