# Tag Info

Accepted

### What is this discrete optimization problem called?

This can be represented as an integer quadratic program, particularly with binary variables. Your problem (with slight tweaking of notation) is: \begin{align} &\min_{k_i \in \lbrace 1, \cdots, m\...
• 3,673

### Discrete-time Algebraic Riccati Equation (DARE) solver in C++

If you want a ten-line solution that is decently fast and stable, you can implement yourself the structured doubling algorithm: set up the coupled iteration $A_0 = A, G_0 = G = BR^{-1}B^T, H_0 = Q$ ...
• 8,610
Accepted

### A 95% minimal rectangle problem

Your problem reads Given $N$ points in, say, two dimensions, find an axes-parallel rectangle of minimal area that encloses at least 95% of the points. This is essentially equivalent to the ...
• 2,106

Applying the transformation you suggested, we get: $$\min_{y \in\{0,1\}^n} (\mathbf{1}-y)^TP(\mathbf{1}-y)$$ $$\mathrm{s.t.}\;\;w^T(\mathbf{1}-y)\geq c\, ,$$ where $n$ is the dimension where $x$ ...
• 131

### Constrained simulated annealing

Simulated annealing comes from computations in statistical mechanics. When I think of simulated annealing, I very much think in terms of physics: I want to minimize some potential energy function that ...
• 543

### Hypergraph matching -> adjacency matrix?

Edges are represented as sets of vertices. With classical graphs, an edge can be represented by the set containing its 2 endpoints. With hypergraphs, they are represented by a set containing more than ...
• 121

### Find index for submatrix with maximum sum

This is a binary knapsack problem which is known to be NP-hard. No efficient algo exists yet, but there are algos that can solve problem up to size of 400 variables (according to a paper published in ...
• 408
1 vote

### Linearize problem with absolute value

I don’t have any to mind, but you can use a family of functions which are parameterized and smooth with absolute value as their limit. Then you can solve for multiple, usually shrinking, values of the ...
• 10.8k
1 vote

It appears that SNOPT requires a paid license, even for single-use by an academic. According to the linked-to website, SNOPT would cost you a single payment of $416. Have you considered using free, ... 1 vote Accepted ### Knapsack problem with fixed number of elements? I don't know if this exactly works for you, but will give the relaxed version a shot: Preliminaries: Correlation matrix can be seen as the covariance matrix of the standardized random variables$X_{...
• 2,139

Only top scored, non community-wiki answers of a minimum length are eligible