New answers tagged combinatorial-optimization
0
votes
Enumerating the elements of cartesian products in ascending order of $\|\cdot\|_1$ norm
I share my "toy code" as an answer to make visually clear that at least a heuristic is available
...
- 11.1k
1
vote
Accepted
Longest path on directed acyclic graph when the weight is defined on the pair of edges
The quadratic shortest path problem (QSSP) can be reduced to the problem. Because QSSP is NP-hard [1], the problem in the question has no polynomial-time solution unless P = NP.
To remove the ...
- 191
0
votes
Enumerating the elements of cartesian products in ascending order of $\|\cdot\|_1$ norm
This problem is at least as hard as the subset sum problem, therefore NP-hard.
For an instance of the subset sum problem with positive integer items $a_1, \dots, a_n$ and the target $T$, let $X_i = \{ ...
- 191
2
votes
Fastest way to solve non-negative linear diophantine equations
Such problems are naturally expressed as finding integral points within a bounded polyhedron. There is a bunch of software available for this, e.g., Normaliz. Although my initial attempt to employ ...
- 26k
2
votes
Fastest way to solve non-negative linear diophantine equations
Consider constraint programming for this. On my laptop, the constraint programming solver in SAS finds all the solutions in one second.
Code:
...
- 3,770
Top 50 recent answers are included