Questions tagged [discrete-optimization]

For questions about optimizations involving variables which can only take on a discrete set of values (e.g. integers, points on a lattice)

Filter by
Sorted by
Tagged with
2 votes
1 answer
59 views

Linearize problem with absolute value

Is there any method to linearize the following optimization problem? \begin{align} min_{x,y} &~~ c~[x; y] \\ st &~~ \sum x\leq \alpha_1 \\ &~~ \sum |y|\leq \alpha_2 \\ &~~ \sum y= 0 \\ ...
1 vote
0 answers
67 views

Help with CVXPY and Disciplined Convex Programming

I'm trying to recreate Figure 1 in this paper. This requires maximizing equation (19), which I have convinced myself is concave, but I am having trouble implementing it in CVXPY. Here is the code I ...
0 votes
0 answers
30 views

'Items in a bucket' optimizaiton problem?

Sorry for question's silly tittle. I don't quite know how to name my problem, that's why I'm here. Imagine you wish do add the collumns of you data ('1','2','3'...'30k' etc.) in such a way as to ...
4 votes
1 answer
2k views

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

I need to use a Discrete-time Algebraic Riccati Equation (DARE) solver for an embedded controller (with limited processing power) in a research project and sadly, I can't find any implementation of it ...
0 votes
0 answers
11 views

Optimal Time Series Weight for Quantile Estimation

Given a time series, $x_1$, $x_2$, ..., $x_t$, .... I want to solve for $$\mathrm{min}_{w_1, w_2, ..., w_m}\rho(x_t-\mathrm{Quantile}(q; x_{t-1}, x_{t-2}, ..., x_{t-m}; w_{t-1}, w_{t-2}, ..., w_{t-m}))...
1 vote
0 answers
34 views

Bipartite Euclidean Matching simple to implement approximate algorithm

I am looking for a simple to implement algorithm for the bipartite euclidean matching problem (or an implementation of any practical algorithm). I am aware of Agarwal's paper, but I would like to ...
1 vote
0 answers
91 views

N-dimensional optimization of moments of distribution function

Let's say I have a bag of marbles. Each marble has several attributes (color, diameter, surface roughness, weight). I know that there is a statistical relationship between various marble attributes ...
0 votes
0 answers
48 views

Balanced constraint

In several optimization problems, we found what we called the balanced constraint(c^T • x = z ) For exp: C^T • 1 = 0 (C is a binary Matrix) Can I have an intuitive explanation about the concept and ...
1 vote
0 answers
49 views

Binary data clustering by Matrix factorization [closed]

I have read an article talking about binary clustering using Matrix factorization(see attached), but i would like to understand some optimization concepts: Is it reasonable to use a Frobenius norm in ...
1 vote
0 answers
36 views

What is the generalization of the resource allocation problem I'm dealing with here?

I'm dealing with a problem as follows: I have a finite set of money 𝑚 to spend over 𝑟 different raffles, and I need to spend approximately to my budget, with the goal of maximizing my probability ...
5 votes
1 answer
118 views

Complementary quadratic knapsack problem

The quadratic knapsack problem (QKP) $$\max_x x^TPx$$ $$\mathrm{s.t.}\;\;w^Tx\leq c,\; x\in\{0,1\}$$ where $P\geq0, w\geq0$ elementwise, is well studied and has existing solvers. My problem below ...
2 votes
1 answer
45 views

Find index for submatrix with maximum sum

Given an N-dimensional matrix A, I want to find an M<N dimensional index array I such ...
0 votes
1 answer
119 views

Avalability of SNOPT optimization solver

I'd like to know if SNOPT solver is available free of cost for academic research in any of the optimization software packages. I came across a few softwares that have SNOPT, but those require a ...
3 votes
0 answers
192 views

Automatically generate constraints for trajectory optimization

This is a follow up to my previous post here I'm interested in performing trajectory optimization from the problem mentioned in abov link. I want to supply the following as dynamical constraints to ...
5 votes
0 answers
111 views

Minimum of quadratic assignment (QAP) with convex objective

Suppose $A,B\succeq0$ and $C\in\mathbb R^{n\times n}$. I am hoping to solve an instance of the following optimization problem: $$ \min_{\textrm{permutation matrices }P} \mathrm{tr}(BP^\top AP+C^\top ...
2 votes
1 answer
89 views

What is this discrete optimization problem called?

It feels like this problem should be commonplace, but I don't know what it's called: Minimize $$ \sum_{i=1}^{n}a^{(i)}_{k_i} + \sum_{i=1}^n\sum_{j=i+1}^n b^{(ij)}_{k_i k_j} $$ with respect to ...
4 votes
0 answers
69 views

Given a list of intervals, find region that is contained by the largest number of those intervals

Start with 1d case. Say I have lots of 1d intervals $[s_i, e_i]$ and I want to find an interval $[s^*, e^*]$ to maximise the count of interval $i$ such that $[s_i, e_i]\supseteq [s^*, e^*]$. 1d case ...
6 votes
1 answer
909 views

Constrained simulated annealing

Simulated annealing is a useful technique for finding near-optimal solutions to combinatorial problems. I have found a lot of tutorials on implementing the basic algorithm, but miss a general guide as ...
3 votes
2 answers
419 views

Knapsack problem with fixed number of elements?

I am looking at an optimization problem that looks like this: $$ \text{minimize}\;\; \mathbf{x}^TQ\mathbf x \;\;, \; \mathbf x \in \mathbb R^n, x_i \in \lbrace 0, 1 \rbrace\\ \text{subject to}\;\; ||...
0 votes
1 answer
420 views

Hypergraph matching -> adjacency matrix?

I need to do a matching on a hypergraph. I read that in the case of a hypergraph there is no adjacency matrix. How do I represent edges then?
4 votes
3 answers
150 views

A 95% minimal rectangle problem

In May, there was a question on Stackoverflow, 3 dimension prediction limit in R, a special form of the "smallest enclosing rectangle" problem. Because the problem has not been solved there, I would ...