1
vote
0answers
48 views

Are there any known bounds on the value of solutions of linear integer programming?

Given a linear objective function and a system of linear constraints; are there any known bounds on the values of (positive) integral solutions in terms of the coefficient matrix of the constraints? ...
2
votes
2answers
111 views

Survey on Compared Running Time: Ellipsoid Method vs. Simplex Method

If you look through papers on the Ellipsoid Method, there is a large agreement, that the Ellipsoid Method, although theoretically polynomial, is in practice way slower than the Simplex Method. ...
1
vote
1answer
101 views

Deducing Linear Inequalities

Let $X_1,X_2,\ldots,X_n $ be indeterminates. Denote by $S$ the set of all linear inequalities of the form $X_{i_1}+X_{i_2}+\ldots+X_{i_k} \geq k,$ with $k \in \{ 1,2,\ldots,n \}$ and $1 \leq i_1< ...
6
votes
1answer
451 views

Inverse of a totally unimodular matrix

A unimodular matrix $M$ is a square integer matrix having determinant $+1$ or $−1$. A totally unimodular matrix (TU matrix) is a matrix for which every square non-singular submatrix is unimodular. A ...
2
votes
1answer
289 views

Maximizing supermodular functions

I have a real supermodular objective function which I want to maximize with constraint. The constraint is on the size, like |A|=k . I am wondering if anyone can give me more information about a ...