The integer-programming tag has no wiki summary.
4
votes
0answers
257 views
Matching a binary matrix
Given a MxN 0-1 matrix D, with the property that
both M and N are odd numbers
its row sums and column sums in the $\mathbb{Z}_2$ field are all equal to the same number (0 or 1).
How do we find M ...
4
votes
0answers
198 views
Domination in Nice Lattices
Let an integer vector be nice when it has only two nonzero components, which sum to zero. So (0, 0, 3, 0, -3) and (-1, 0, 1, 0, 0) are examples of nice vectors in $n=5$ dimensions.
Call a lattice ...
2
votes
0answers
74 views
existence of lattice point in polytope
This question was probably asked before but here goes. I have a convex polytope given by $Ax\leq b$ for a specific integer matrix $A$ and integer vector $b$. I need a simple method/result on how to ...
2
votes
0answers
94 views
Beating Kadane's Algorithm
I am seeking some reference on already existing work for the following problem.
Given an $n$-dimensional square matrix $A=DP$ where $D$ is a diagonal and $P$ is a permutation matrix (think of Gaussian ...
2
votes
0answers
273 views
0,1 solution to system of linear integer equations.
I have the following problem:
$A x = b$
where $A, b$ - $m \times n$-maxtrix and $m$-vector of nonnegative intgers (respectivelly).
$x \in \{0,1\}^n $ - vector of binary variables, which need to be ...
1
vote
0answers
38 views
LP constraint enconding
I have an objective function to be maximized
$obj(x) = \sum_i \gamma_i x_i$ with $x_i \in \mathbb{R}$
With multiple constraints of the form:
$\min_{y \in 0,1} (\sum_{i \in A} \alpha_i x_i + \sum_{i ...
1
vote
0answers
56 views
What is the solution to \min_k k \frac{b^k/n}{\lfloor b^k/n \rfloor}
(I've posted this question at Math.SE but got no answer, so I hope I can get a solution here.)
This problem looks familiar, but I don't remember its solution:
$$ \min_k \ \ \frac{b^k/n}{\lfloor ...
1
vote
0answers
134 views
Reference Request for Integer factorization with LP/ILP
Have there been attempts to factor integers with Linear Programming?
Searching the internet suggests that for Integer Factorization only Number Theoretic algorithms, like sieves, are taken into ...
0
votes
0answers
130 views
If-then-else on mixed linear integer programming
Hi all.
Let A,B and C be three real variables. I must write the following if-then-else condition with linear inequalities:
if A≤B then C=0 else C=B-A
Is this possible by adding a single binary ...
0
votes
0answers
133 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 ...
0
votes
0answers
127 views
$\ell_o$ Minimization (Minimizing the support of a vector)
I have been looking into the problem
$\min: \|x \|_0$ subject to$: Ax=b$. $\|x \|_0$ is not a linear function and can't be solved as a linear (or integer) program in its current form. Most of my time ...
0
votes
0answers
133 views
Maximum subset of set of Integers with minimum distance
Hi, i have a set of integers for example: {0,1,3,100,102} and i am looking for a maximum subset in which all elements have a minimum distance to all elements (or the "next" doesnt matter i guess) for ...
0
votes
0answers
111 views
Question on non-linear parametric mixed integer program
I am trying to solve a mixed integer minimization problem, where there are a number of parameters, and there are products of parameters with variables appearing in the objective function. I assume ...
0
votes
0answers
135 views
Knapsack Constraint
I'm trying to implement a recursive algorithm that I came up with that first solves the knapsack for a given objective and then cuts off the solution and then finds the next best solution.
However, I ...
