Rodrigo de Azevedo
  • Member for 5 years, 7 months
  • Last seen this week
  • Europe
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
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
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
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
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
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
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
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
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
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
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
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
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
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