Rodrigo de Azevedo
  • Member for 5 years, 7 months
  • Last seen this week
  • Europe
Why is data in computer science considered to be discrete?
9 votes

Because: Digital computers cannot store arbitrary real numbers. Analog computers are plagued by thermal noise (if electronic), friction (if mechanical or hydraulic), disturbances, sensitivity to ...

View answer
Why can't we round results of linear programming to get integer programming?
7 votes

In $\mathbb R$, one can simply round down or round up to obtain an element of $\mathbb Z$. Only two choices! However, in $\mathbb R^n$, one has $2^n$ ways of rounding to obtain an element of the ...

View answer
How to reduce the low-rank matrix completion problem to integer programming?
4 votes

Simplifying the problem: Given a positive integer $r$ positive integers $m, n \geq 2$ a partial binary matrix $\mathrm A \in \{*, 0,1\}^{m \times n}$ (where $*$ denotes an unknown entry)...

View answer
Number of $n \times n$ binary matrices whose rows and columns sum to at most $m$
4 votes

Given $1 \leq m \leq n$, we want to determine the cardinality of the following set $$\{ \mathrm X \in \{0,1\}^{n \times n} \mid \mathrm X 1_n \leq m 1_n \,\land\, \mathrm 1_n^{\top} \mathrm X \leq m ...

View answer
Converting if-then-else condition to integer linear programming with equality constraints
Accepted answer
3 votes

We have three binary variables $x, y, z \in \{0,1\}$ and the following if-then-else (ITE) condition $$\text{if } x = 1 \text{ then } y = 1 \text{ else } y = z$$ If $x = 1$, then $y = 1$ but $z \in \{...

View answer
Cost of solving a matrix equation using the FFT
Accepted answer
3 votes

If $m \times m$ symmetric matrix $\rm H^{\top} H$ is circulant, then its spectral decomposition is $$\rm H^{\top} H = Q \Lambda Q^*$$ where the eigenvalues of $\rm H^{\top} H$ are given by the ...

View answer
Truth and lie in infomation theory: negative amount of information
3 votes

Suppose we have the following deck of cards $$\{\mbox{Ace}, 2, 3, 4, 5, 6, 7, 8\}$$ I shuffle the deck, pick a card, but do not show it to you. You are totally ignorant as to what card I picked. ...

View answer
Proving that $A \vee (\neg A \wedge B) \equiv A \vee B$
3 votes

$$a \lor (\neg a \land b) \equiv (\underbrace{a \lor \neg a}_{\equiv \text{True}}) \land (a \lor b) \equiv \text{True} \land (a \lor b) \equiv a \lor b$$

View answer
Approximate subset sum with two-dimensional vectors
2 votes

Let $\rm V$ be the $2 \times n$ matrix whose $i$-th column is vector $\rm v_i$. We have the Boolean optimization problem in $\mathrm z \in \{0,1\}^n$ $$\min_{\mathrm z \in \{0,1\}^n} \| \mathrm V \...

View answer
Expressing a logical constraint in integer programming
Accepted answer
2 votes

Let $x \in [-10,10] \cap \mathbb Z$ and $y \in \{0,1\}$. Suppose that $$y = \begin{cases} 1 & \text{if } x \geq 3\\ 0 & \text{if } x \leq 2\end{cases}$$ To ensure that $y \neq 0$ when $x \...

View answer
LQR optimal control of accumulator via dynamic programming
1 votes

$$ \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} = \underbrace{\begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 ...

View answer
Integer linear programming formulation of formula in DNF
1 votes

To complement the 2nd part of D.W.'s answer, we would like to find an $\mathcal H$-polytope (defined by the intersection of closed half-spaces) whose intersection with $\{0,1\}^4$ is $$\{ (1,1,0,0),(...

View answer
Are there any programming languages that support state machines in their standard library?
0 votes

Suppose that you have a (finite) list of Boolean values and that you would like to count the number of occurrences of True. This (infinite) state machine's state-transition function is $$ f (x, u) := \...

View answer
Given matrix $A$, find vector $x$ such that every entry of $Ax$ is nonzero
0 votes

Given $\mathrm A \in \mathbb{R}^{n \times n}$ with no zero rows, we would like to find $\mathrm x \in \mathbb{R}^n$ such that every entry of $\rm Ax$ is nonzero. Let $\mathrm b \in \mathbb{R}^n$ be a ...

View answer
Casting to boolean in integer linear programming
0 votes

Let $f : \{0,1,\dots,5\} \to \{0,1\}$ be defined by $$f (x) := \begin{cases} 0 & \text{if } x = 5\\ 1 & \text{if } x \neq 5\end{cases}$$ Let $ y = f (x)$. We would like to maximize $y$. Note ...

View answer