Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

1
vote
1answer
2k 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 = ...
2
votes
1answer
93 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 ...
0
votes
1answer
103 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 ...
1
vote
0answers
113 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 ...
1
vote
2answers
553 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 ...
4
votes
1answer
373 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 ...
4
votes
1answer
428 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} ...
3
votes
1answer
108 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 ...
2
votes
1answer
257 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 ...