Tagged Questions
1
vote
1answer
17 views
Minimizing deviations from threshold value from a given group of numbers
Given a set of numbers $a_n$, a threshold level $t$, how do I find the combination of numbers that will sum to at least the threshold with minimum deviation? Added: That is, they must always exceed ...
0
votes
1answer
40 views
Partial linear relaxation yields an integer solution
Consider a binary integer program
\begin{align}
\min \quad &\sum _{j \in J}f_j x_j +\sum _{i \in I} c_i y_i \notag \\
\mbox{s.t.} \quad &\sum _{j \in N_i} x_j \ge 1-y_i, \quad \forall i\in I ...
1
vote
1answer
48 views
Strict inequality in MILP
I have a problem with the following constraint. There are 2 variables
$p \in [0,1] \subseteq \mathcal{R}$
$\sigma \in [0,1] \subseteq \mathcal{Z}$
The constraint over the variables is
$c - p < ...
1
vote
1answer
45 views
How tell if a polyhedron contains a lattice point
So given a polyhedron
$Ax \le b$
Is there an Algorithm or formula to determine whether said polyhedron contains a lattice point (integer point)
I was thinking a couple things:
brute force ...
1
vote
1answer
72 views
Linear programming vs. Integer programming
I was trying to solve a problem where I want to choose which items to choose where each item has a number b_i associated with it and a reward r_i associated with it. I need to choose items that ...
3
votes
1answer
81 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 ...
0
votes
0answers
26 views
Examples of exp. sized LPs that can be solved in polynomial time by the GLS variant of the ellipsoid method?
The GLS (grötschel lovasz schrijver) variant of the ellipsoid method is a method that can solve LP with exponentially many facets or variables (by considering the dual LP) in polynomial time if the LP ...
1
vote
1answer
68 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
49 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 ...
2
votes
1answer
98 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
78 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 ...
3
votes
1answer
57 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 ...
4
votes
1answer
108 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}
...
2
votes
1answer
39 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?
...
1
vote
1answer
49 views
Linear Integer Programming: consecutive/adjacent variables constraint
Given a set of binary variables $x_{ij} \in X,\ i=0,..,N,\ j=0,..,M$ how do I model an adjacency constraint on $i$'s such that:
$\sum_i^N\sum_j^Mx_{ij} = \alpha, \;\text{with }\ 0 < \alpha < ...
