Tagged Questions
4
votes
4answers
211 views
Good software for linear/integer programming
I never did any linear/integer programming so I am wondering the following two things
What are some efficient free linear programming solvers?
What are some efficient commercial linear programming ...
4
votes
1answer
99 views
Determining quickly whether this Integer Linear Program has any solution at all
I've got an integer linear program of the form
$$
\begin{aligned}
\text{Minimize}&& c &= x_1 + \cdots + x_m \\
\text{subject to}&& A\mathbf{x} &\geq \mathbf{b} \\
\text{where}
...
3
votes
1answer
53 views
A particular ILP where the existence of a relaxed solution implies the existence of an integer solution
This question emerged from a discussion on my previous question Determining quickly whether this Integer Linear Program has any solution at all, which I would like to elaborate separately.
I am ...
3
votes
1answer
47 views
Is the inverse of an invertible totally unimodular matrix also totally unimodular?
My question is learned from here. Let me restate it as follows:
A unimodular matrix $M$ is a square integer matrix having determinant $+1$ or $−1$. A totally unimodular matrix (TU matrix) is a matrix ...
3
votes
1answer
128 views
Efficiently solving a special integer linear programming with simple structure and known feasible solution
Consider an ILP of the following form:
Minimize $\sum_{k=1}^N s_i$ where
$\sum_{k=i}^j s_i \ge c_1 (j-i) + c_2 - \sum_{k=i}^j a_i$ for given constants $c_1, c_2 > 0$ and a given sequence of ...
3
votes
1answer
165 views
Connected graph solution from IP/LP
I have a problem on a graph (of maximum degree $c$) which looks for a connected subset of edges fulfilling some properties.
I have problems formulating the connectedness condition in an IP/LP.
The ...
2
votes
3answers
64 views
How to formulate Unique value constraint in Integer Programming?
Given the following integer programming formulation, how can I specify that the variables are unique and none of them has the same value as the other one. basically ...
2
votes
1answer
80 views
Linear programming problem with no objective function
I have a binary integer programming problem for which I only need a solution that meets all the constraints. I do not have an objective function that I am trying to minimize or maximize.
I've been ...
2
votes
3answers
130 views
Linear inequalities to make a specific solution infeasible
Say we have a binary linear programming problem:
\begin{equation*}
\begin{aligned}
& \underset{\mathbf{x}}{\text{minimize}}
& & c\cdot\mathbf{x} \\
& \text{subject to}
& ...
2
votes
1answer
27 views
Linear Programming: Breaking Variables Product
Given two sets of binary variables $x_{i...N} \in X$ and $y_{i...M} \in Y$ and another binary variable $\alpha$ how can I linearize the following constraint, i.e break the product of variables?
...
2
votes
0answers
65 views
Branch-and-Price algorithms for IP/MIP
I'm trying to do research into Branch-and-Price algorithms, which generally rely on Branch-and-Bound and column generation (typically Dantzig-Wolfe decomposition) to solve integer and mixed-integer ...
1
vote
1answer
33 views
Linear programming: expressing the fact that precisely $k$ variables are nonzero
Given some variables $x_1,\ldots,x_n$ is it possible to somehow express in a linear program the fact that precisely $k$ of them are non-zero?
I suspect this would already be enough to simulate ...
1
vote
1answer
185 views
LP relaxation for ILP\IP (integer linear programming)
I am familiar with LP relaxation for ILP (or IP). Assume we concern with integer minimization problem, which we formalize using ILP; we then relax the ILP into LP and we say that the LP provides a ...
1
vote
1answer
52 views
Linear Programming for Integer Solutions
Connsider the linear programming problem Max $z = 5x_1 + 6x_2$ st. $10x_1 + 3x_2 \leq 52,2x_1 + 3x_2 \leq 18$ and $x_1, x_2 \geq 0$ and integer.
How would one manipulate the resources so that the ...
1
vote
1answer
42 views
Are there 0-1-matrices that are not unimodular?
I am just wondering if there are matrices that only consists of $0$s and a few $1$s that are not totally unimodular (TU)? I cannot come up with an example but I am not very experienced with this ...