Questions on optimization constrained to integer variables.
1
vote
1answer
25 views
HINT for summing digits of a large power
I recently started working through the Project Euler challenges, but I've got stuck on #16 (http://projecteuler.net/problem=16)
$2^{15} = 32768$ and the sum of its digits is $3 + 2 + 7 + 6 + 8 = ...
0
votes
0answers
24 views
formulate an ip to minimize cost
A car rental company has m branches. the number of cars currently available at branch i is vi. The company re-position its fleet at the beginning of every month to prepare for the demands of upcoming ...
1
vote
1answer
15 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 ...
-4
votes
0answers
52 views
formulate an ip to minimize the total distance …
Cook country needs to build two hospitals. There are 9 cities where the hospitals can be built.The number of hospital visits made annually by the inhabitants of each city and the $(x,y)$ coordinates ...
0
votes
1answer
37 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
46 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 < ...
0
votes
1answer
28 views
“Location to location” algorithm?
Lets say I have two locations, each one with X, Y, Z, and a int. Each location represents one cube in a 1000 x 1000 world. Lets say I had one location at 500, 343, 284, with an int 1. Another one at ...
0
votes
0answers
26 views
Is round(x/y) equal or approximately equal to (x+y\2)\y?
I need a formula to divide integers with the correct rounding and found this one:
(x+y/2)/y
But will this work even if integer division is used in the ...
1
vote
1answer
40 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
68 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 ...
0
votes
1answer
27 views
Finding a solution for quadratic inequality
Given $r$ and $t$, Is there a way to find the maximum positive integer $N$ such that:
$$2 N^2 + (2r+3)N + (2r+1) \leq t$$
I want to write a program to solve that inequality without brute-force. At ...
1
vote
0answers
25 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
69 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
20 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
35 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
40 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
84 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
67 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
57 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
21 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 ...
3
votes
5answers
53 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
30 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
29 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
99 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
34 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
...
1
vote
1answer
45 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 ...
0
votes
3answers
42 views
Binary Programming with nonlinear constraints
i have the following type of problem i'm interested to solve:
Minimize the objective function: $f(x_1,\ldots, x_8) = \sum_{i=1}^8 a_i x_i$ with $a_i \in [0, \infty)$ and $x_i \in \{0,1\}$ and given ...
2
votes
1answer
90 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
0answers
63 views
Binary optimization
Let me first make my background clear. I am a PhD student with not much knowledge in optimization but I need to do some optimization as a part of my research work. My problem is as follows:
There are ...
2
votes
1answer
74 views
Maximizing the number of non-crossing lines between a number of points
Suppose I have a number of points in 2-dimensional space. I want to draw as many lines between the points as possible such that no two lines cross.
Hoping for a polynomial time algorithm, I ...
0
votes
1answer
99 views
Integrating the step-wise integer function 1/[x]
I'm trying to find the integral, respective to $x$, of a function that utilizes the step-wise integer (or floor) function.
$$\displaystyle z = \int {1 \over [[x]*1.1^{[y]}]+1}$$
It's for modelling a ...
0
votes
1answer
47 views
integer programming formulation problem
Consider a problem with three variables: $u$, $\sigma_l$, and $\sigma_w$ where $\sigma_w > \sigma_l$. I want to represent the following relationship using integer programming.
\begin{equation}
u =
...
2
votes
3answers
75 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
55 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
105 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
34 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
47 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 < ...
4
votes
0answers
122 views
On the integer feasibility of polytopes defined by idempotent integer matrices
EDIT: I realized that while writing this question, I was reasoning about orthogonal projections. Thus, I forgot to transpose when forming the projection on to the space orthogonal to the image of $P$. ...
1
vote
1answer
60 views
$ A = x + y + z$, number of solutions in $Z$ if $x, y, z$ are bounded in intervals
For the equation $x + y = A$, it's easy, when you notice that when iterating over all possible $x$, the number of solutions for $y$ is $0$ at the beginning, then increases by $1$, then stays constant, ...
1
vote
0answers
42 views
Determining if data can be fit by a continuous piecewise integer-valued polynomial
This question concerns the sequence of integers which form the solution to a particular computational problem. See the bottom for the full formulation; basically, for some value n, $G(n)$ is the ...
1
vote
4answers
74 views
Procedures to find solution to $a_1x_1+\cdots+a_nx_n = 0$
Suppose that $x_1, \dots,x_n$ are given as an input. Then we want to find $a_1,\ldots,a_n$ that satisfy $a_1x_1 + a_2x_2+a_3x_3 + a_4x_4+\cdots +a_nx_n =0$. (including the case where such $a$ set does ...
1
vote
1answer
37 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 ...
4
votes
4answers
245 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 ...
0
votes
1answer
50 views
Converting loop to a closed form expression? [duplicate]
Possible Duplicate:
How to convert this loop into a closed form expression?
I have the following code in Python
...
2
votes
2answers
131 views
Prove or disprove a chessboard with diagonal corners removed, cannot be tiled with L shape pieces or size 2
I think this is impossible, but I don't know how to prove an integer solution doesn't exist for a given equation. Here's my approach:
First, observations:
The removed tile will be of the same color. ...
0
votes
1answer
23 views
Finding the solutions of $ax+by\le D$
Given parameters $a,b,D$, all integers, I want to find all the integer solutions $(x,y)$ of
$ax+by\le D$
Or at least a nice way to characterize them. Also, for a given $R$, it is actually enough for ...
2
votes
1answer
80 views
Unimodular matrix definition?
I'm a bit confused. Based on Wikipedia:
In mathematics, a unimodular matrix M is a square integer matrix
having determinant +1, 0 or −1. Equivalently, it is an integer matrix that is invertible ...
0
votes
0answers
31 views
How to formulate or statment in integer programming
I need to formulate below statement in integer linear programming.
if x+y=2 then (a+b<c or c+g<a)
Can you help me please?
7
votes
2answers
219 views
Mean and Median in a Classic River Crossing Problem
Consider the following classic problem:
Four people on the west side of a river wish to use their single boat to get to the east side of a river. Each boat ride can hold at most two people, and the ...
0
votes
1answer
55 views
Approximate rational number of radical combination
Suppose that there is a radical combination $a\sqrt{b}+c\sqrt{d}$ where a,b,c,d are natural. Each term part $\sqrt{b}$ cannot be transformed into the form of $s\sqrt{q}$.
The question is,
1) Suppose ...
