Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

2
votes
2answers
3k 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 = ...
1
vote
2answers
1k views

$\ell_0$ 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 has ...
3
votes
1answer
120 views

XORing consecutive integers has an interesting property. Does anyone know why?

I hesitated to post on StackOverflow but I think the problem has little to do with programming and more to do with mathematics. So, here it is: I wanted to compute the function $ f(n) = 0 \oplus 1 ...
2
votes
1answer
100 views

Find known number of missing natural numbers

Given a set $S$ of distinct natural numbers, we know that a subset $T$ that is $S$ with at most $k$ number of elements missing. Let $M_k := \big\{m_j\big|d_j = \sum_{i\in T}i^j, j\in ...
1
vote
2answers
60 views

Eliminating non-integer solutions to $ab / (2\sqrt{ab} + a + b)$

I am writing a program to output all $a,b \in \mathbb{N}$, where $a \le b \le n$ (for a given $n \in \mathbb{N}$), such that $$ \frac{ab}{2\sqrt{ab}+a+b}=c\in \mathbb{N} $$ For example, $a=9$, ...
0
votes
1answer
115 views

How to minimize cost of group of items given that weights of item sums up to fixed value and atmost 'n' number of items are allowed?

Given that we have a set of items :- { (c1, w1) , (c2, w2), (c3, w3) , ... } where (ci, wi) are the respective cost and weight of the ith item. Its required to minimize total cost of items C such ...
5
votes
1answer
638 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} ...
4
votes
1answer
132 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 ...
1
vote
0answers
129 views

Why these two problems lead to same answers?

Suppose these two problems: Problem 1: $$\min_{X,P} \quad\max_{1\leq l\leq L-1} \quad {|\sum_{1\leq i\leq N_p}^{N_p}x_ie^{\frac{2\pi l}{N}p_i}| \over {\sum_{i=1}^{N_p} x_i^2}} \quad \equiv \quad ...
4
votes
1answer
516 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
3answers
445 views

How to divide natural number N into M nearly equal summands?

How to divide natural number N into M nearly equal summands? For example, to divide 20 by 13, in geometric representation, I should get How to generate the sequence above? What is the name of ...
2
votes
1answer
415 views

Minimize $\|Ax-b\|$ where $x$ is a binary vector

For a software project I'm involved on, I have a situation where I have a large vector that is the sum of some smaller vectors. I know all the possible small vectors, and I know that no two of them ...
2
votes
1answer
893 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 ...
1
vote
1answer
76 views

Efficient (time complexity) algorithm for Linear Programming problems

I have an inequality of the form: $$\sum_{i=1}^n a_i\cdot x_i \ge a_0$$ where $a_i\gt 0$ for all $i$. Subject to this and $x_i\ge 0$ for all $i$, I have to minimize the expression: $$\sum_{i=1}^n ...
0
votes
1answer
46 views

Is there any algorithm to find all the solutions of the following special linear Diophantine system?

Consider the following system. 1) $a_{11}x_1 + a_{21}x_2 + \cdots + a_{m1}x_m=d_1$ 2) $a_{12}x_1 + a_{22}x_2 + \cdots + a_{m2}x_m=d_2$ $\vdots$ n) $a_{1n}x_1 + a_{2n}x_2 + \cdots + a_{mn}x_m=d_n$ ...
0
votes
1answer
77 views

Is this matrix totally unimodular? [closed]

Is this matrix totally unimodular? Thank you in advance! $A=\begin{pmatrix} -1& 0& 0& 0& -1\\ 0& 1& 1& 0& 0\\ 1& 0& 0& 1& 0\\ 0& ...
0
votes
1answer
32 views

Integer Points in Simplex

Let $$A_w(d,q):=\left\{{\bf k} \in \mathbb{N}_0^d: \sum_{j=1}^d w_j k_j \leq q\right\}$$ denote the number of non-negative integer points in the $\ell_1$-ellipse with semi-axes of length ...