4 votes
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\...
user avatar
  • 3,673
4 votes

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$ ...
user avatar
3 votes
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 ...
user avatar
  • 2,106
3 votes

Complementary quadratic knapsack problem

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$ ...
user avatar
  • 131
3 votes

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 ...
user avatar
  • 543
2 votes

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 ...
user avatar
  • 121
2 votes

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 ...
user avatar
  • 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 ...
user avatar
  • 10.8k
1 vote

Avalability of SNOPT optimization solver

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, ...
user avatar
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_{...
user avatar
  • 2,139

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