Questions on optimization constrained to integer variables.
1
vote
0answers
15 views
Integer vector decomposition on a degenerate integer vectors basis
Let's say I have a vector of integer numbers, and I would like to get a decomposition of that vector using a set of "basis" vectors (which are also integers), these vectors are arbitrary, i.e. they ...
3
votes
1answer
44 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
12 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 ...
0
votes
0answers
28 views
How to represent probability as Integer - Arithmetic coding
I am doing an assignment for a class in college where we have to write an arithmetic encoder / decoder in Java.
In this video, it shows how to set up / define all the variables required for the ...
2
votes
0answers
33 views
Clarification of variable values in Arithmetic Coding algorithm
I have been trying to follow this video to implement my own Arithmetic Coding algorithm in Java. I am having a bit of trouble figuring out what some of the variables in the video should be.
For ...
3
votes
0answers
81 views
How to minimize $\min_k k \frac{b^k/n}{\lfloor b^k/n \rfloor}$
This problem looks familiar, but I don't remember its solution:
$$ \min_k \ \ \frac{b^k/n}{\lfloor b^k/n \rfloor}k $$
subject to
$$ b^k \ge n \\ b,n,k \in \mathbb{N} $$
Does it have a name? What's ...
1
vote
1answer
48 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 ...
2
votes
1answer
48 views
Integer solutions to a hyperbola
Is there a way to find all integer solutions to a hyperbola equation? If it helps, I am specifically looking at "square" hyperbolas (i.e. of the form $\frac{x^2}{z} - \frac{y^2}{z}=1$), where z is an ...
0
votes
0answers
19 views
Finding “good” values with regards to split disjunctions
We've been given an assignment in a course on Mixed-Integer Optimization, and one of the questions is about split disjunctions, or more precisely, finding good values for a split disjunction in order ...
2
votes
0answers
28 views
Generation of unimodular matrices with bounded elements
Does anybody know what is the algorithm of generation of random unimodular matrices, i.e. integer matrices with the determinant +1 or -1 (whose elements do not exceed a given bound)? Such algorithm is ...
3
votes
5answers
51 views
Why is my procedure misleading?
Max: $ z = 10( x_1 + x_2)$
subject to constraints:
$$ 2x_1 + 5x_2 \leq 16 $$
$$ 6x_1 + 5x_2 \leq 30 $$
$$ x_1, x_2 \in \mathbb{Z^+} $$
I have the Integer Programming ...
0
votes
0answers
25 views
How do I find the set of integers solving a system of equations that contain outliers?
I have a system of $s$ equations that should (but won't) all equal some real unknown scalar value, $x$:
$x = v_1*k_1 + a_1*k_1*m = v_2*k_2 + a_2*k_2*m = ... = v_s*k_s + a_s*k_s*m$
where,
$k_i$ are ...
1
vote
1answer
22 views
Efficient MIP reformulation for binary integer problem
Consider an integer programming model where there is some term $x_ix_j$ where the variables $x_i,x_j \in \{0,1\}$
I want to reformulate this into an efficient mixed-integer programming (MIP) problem.
...
-1
votes
1answer
94 views
Finding sum of all integral parts
Moderator Note: This is a question in a current contest.
Given two numbers $M$ and $N$, Let $q_i$ be the integer part of $\frac{iN}{M}$. What is
$$
\sum_{i=0}^{M-1} q_i?
$$
The Sum is obviously ...
0
votes
1answer
31 views
Cutting plane in IP system
I am doing branch-and-bound for 5 decision binary variables. so Decision would be 0 and 1.
and I found sub-problem node Q with optimal value 5.4 (0.3, 0.2, 1, 0.5, 0.1)
my IP constraints are
...
