Questions tagged [heuristics]
A heuristic is a procedure that can apply generically to many problems (for example gradient descent, alternating optimization, simulated annealing) but will typically not have formal guarantees associated with its use.
51 questions
0
votes
0
answers
41
views
Implementing Lin-Kernighan algorithm for TSP
I'm looking for some guidance in implementing the Lin-Kernighan heuristic for the TSP. I have been trying on and off for a couple of weeks and I have read a bunch of papers, two of the better ones I ...
- 1
2
votes
1
answer
168
views
Efficient tools for checking SMT formulas with two quantifiers ($\exists\forall$)
I would like to check a sort of SMT formulas with two quantifiers where universal variables range over finite/bounded integer domains. An example formula is
$$\exists x \forall y ((y \ge 1 \land y \le ...
- 75
0
votes
0
answers
146
views
Matching of two weighted graphs allowing one-to-many mapping
I am looking for a heuristic for a graph matching problem as follows.
Given two graphs: $A$ (consisting of nodes $a_i$) and $B$ (consisting of nodes $b_i$). Typically the size of $B$ is larger than ...
- 1
0
votes
1
answer
165
views
Is it possible to prove that a general purpose integer factorization algorithm must contain a loop?
1)
Let $A$ be a (general purpose) algorithm that factors $n$. Suppose $A$ contains a loop (which is hard to imagine if not impossible that it does not.) If $A$ contains nested loops then these loops ...
user35803
1
vote
0
answers
36
views
Pass ordering for greedy local search algorithms
Apologies in advance for the slightly general question - I'm really looking for pointers to research / good keywords to look for.
I have a problem with the following setup: I have a (finite) totally ...
- 444
2
votes
0
answers
105
views
On the goal of learned clause database reduction in CDCL SAT solvers
Modern SAT solvers frequently reduce the size of their learned clause database in order to keep its size as manageable as possible. This has as effect not to slow down the speed of unit propagations.
...
- 321
9
votes
1
answer
674
views
Understanding performance of QFBV SMT solvers
SMT solvers such as Z3 or Boolector use a complex set of heuristics to solve problems. However, this also makes predicting the performance of such a solver for a given problem very hard. My question ...
- 193
9
votes
2
answers
963
views
List of NP-hard problems, where there is active research in practical heuristics
I am looking for list of NP-hard optimization problems, where there is active research in practical heuristic for solving them and there are common benchmarks, which people try to beat.
Examples ...
1
vote
1
answer
186
views
Practical/heuristic algorithm for multi set-cover
Consider a universe $N$ containing $n$ elements, and a collection of sets $\mathcal{C}$, over $N$. The $k$-multiset multicover (MSMC) problem is to cover all elements of the universe $N$ at least $k$ ...
- 791
60
votes
6
answers
4k
views
Theoretical explanations for practical success of SAT solvers?
What theoretical explanations are there for the practical success of SAT solvers, and can someone give a "wikipedia-style" overview and explanation tying them all together?
By analogy, the smoothed ...
- 38.5k
18
votes
2
answers
2k
views
Are there any heuristic-free NP complete problems?
Are there any NP complete problems with no infinite subset of instances $\Phi$ such that membership in $\Phi$ can be decided in polynomial time, and for all $x \in \Phi$, $x$ can be solved in ...
- 1,152
6
votes
2
answers
396
views
Finding smallest context free grammar that generates a set of sets
Are there any results known about the size of smallest context free grammar that generates a set of sets?
That is, I am given an alphabet $\Sigma$ as well as a set $S \subseteq \mathbb{P}(\Sigma)$ ...
- 338
1
vote
1
answer
238
views
Are there any heuristics that works solely on graphs?
I'm exploring heuristics in A* and apparently all heuristics require coordinates of all the locations to calculate a h-cost. This is fine if you are working on grids, but what if you need to work ...
- 113
0
votes
2
answers
906
views
Packing $n$ objects into $m$ bins whose size is variable
Assume we have $n$ fixed size objects with sizes $O_1$ to $O_n$. Also, assume we have $m$ bins with size $a \times B_1$ to $a \times B_m$ in which $a$ is a real number and $a\ge1$. We want to put ...
- 175
3
votes
0
answers
142
views
Complexity of minimizing monotone arithmetical formulas
Let's say that I have a multi-variate arithmetical expression $A(x_1, \ldots, x_n)$ that uses addition and multiplication operations and is also in a very simple form of sums of products, e.g., $A_1(...
- 338
1
vote
0
answers
73
views
Looking for reference proving polynomial-time bounds for A* search under specific conditions
In the textbook "Artificial Intelligence - A Modern Approach" (Russel, Norvig), it mentions that a sufficient criteria for the A* search algorithm to complete in polynomial time is for the heuristic ...
- 425
4
votes
1
answer
215
views
Pathfinding search over a space with known changing costs
I'm working on a research project which involves iterative pathfinding over a space whose cells have danger values that change over time.
More specifically, the danger values represent bad weather, ...
- 43
1
vote
1
answer
108
views
Approximations for the Stable Fixtures Problem
I have a set of N items, each with a subset of those items they can be paired with; each pair has a weight. I'd like to choose pairs to maximize the total weight, subject to each item being in at ...
- 113
2
votes
3
answers
334
views
Heuristic with worst-case exponential complexity
I have been working with some colleagues on a metaheuristic for an NP-Hard optimization problem. It is a genetic algorithm using a steady-state population replacement strategy (at each iteration a ...
- 52
0
votes
1
answer
157
views
TSP heuristics for limited distance information
this is my first question on Theoretical CS. :)
I've posted a similiar question on Mathoverflow and a friendly user advised me to post my question on this site.
Problem:
I'm looking for TSP ...
- 103
2
votes
0
answers
58
views
Hardness of Covering Arrays with $v=t=6$
A covering array is an $N \times k$ array with each entry as one of $v$ symbols, where for every $t$ columns all possible $v^t$ tuples appears at least once. The covering array number (CAN) is the ...
- 653
5
votes
2
answers
2k
views
Good algorithms to solve ATSP
What are some good neighborhood-based local search algorithms or strategies to solve the Asymmetric TSP ? I see many 2-OPT and K-opt based algorithms (e.g. Lin-Kernighan implementations), but I think ...
- 171
-3
votes
1
answer
96
views
Is this NP-Hard or does a known optimal polynomial time solution exist? [closed]
Suppose we have 10 items, each of a different cost
Items: {1,2,3,4,5,6,7,8,9,10}
Cost: {2,5,1,1,5,1,1,3,4,10}
and 3 customers
{A,B,C}.
Each customer has a requirement for a set ...
- 1
2
votes
1
answer
252
views
Literature for Generalized Load Balancing
i am looking for literature on this kind of problem.
$$
\begin{align}
\min_x \max_k &\quad \sum_{i,j} x_{ij}c_{ijk}\\
\text{subject to}&\\
&\sum_j x_{ij}=1,&& \forall i\in\mathcal ...
- 21
4
votes
1
answer
1k
views
Heuristics for tsp without triangle inequality
Every heuristic for the traveling salesman problem that I know of (Nearest-Neighbour, Christofides, Held-Karp, ...) assumes that the triangle inequality holds.
Are there heuristics to solve the tsp ...
- 227
5
votes
0
answers
203
views
Exploring a DFA, with no feedback
Let $M=(\Sigma,S,s_0,\delta)$ be an (unknown) deterministic finite-state automaton (DFA), with alphabet $\Sigma$, statespace $S$, start state $s_0 \in S$, and transition relation $\delta$. I want to ...
- 12.4k
19
votes
5
answers
2k
views
Fast treewidth algorithms
I would like to compute the treewidth of a graph. There are really good heuristics for other NP-hard graph problems such as VF2 for subgraph isomorphism, with code available in igraph for example. I ...
- 3,912
5
votes
1
answer
2k
views
Approximation for metric TSP: Worst case using nearest neighbor heuristic?
I'm looking at different heuristics that approximate solutions for a metric Traveling Salesman Problem. I was wondering if there is a worst case ratio of tours calculated by the nearest neighbor ...
- 153
6
votes
3
answers
596
views
Simplification of weighted NFA
What options does one have for the simplification (meaning reduction in the number of states) of weighted NFA over the probability semiring? From my understanding one can determinize, and then ...
- 81
4
votes
0
answers
160
views
Find index set partition that has large projections
I have a multiset $S$ of $n$-bit strings. Let $1_S(s)$ denote the number of times that string $s$ appears in $S$, i.e., the multiplicity of $s$ in $S$. I want to find a partition of $\{1,2,\dots,n\}$...
- 12.4k
4
votes
1
answer
133
views
Balanced partitioning of a set of axis-parallel 2D rectangles
Fix a constant $0<\alpha<1/2$. The problem is the following. Suppose there are $N$ axis-parallel rectangles on the 2D plane with weights $w_1, w_2,\ldots, w_N$ and with coordinates all in the ...
- 41
9
votes
2
answers
1k
views
Generating interesting combinatorial optimization problems
I'm teaching a course on meta-heuristics and need to generate interesting instances of classic combinatorial problems for the term project. Let's focus on TSP. We are tackling graphs of dimension $200$...
- 193
8
votes
3
answers
402
views
Find the nearest $d+1$ corners of a cube in $\mathbb{R}^d$
How can one find the $d+1$ corners of the unit cube in $\mathbb{R}^d$
nearest a point $x$ in the cube ?
Use the L1 metric, so that in 4d
|$x$ - 0000| = $\sum {x_i}$,
|$x$ - 0001| = $x_3 + x_2 + x_1 + ...
- 323
0
votes
0
answers
135
views
Tractability of mutual information-augmented ensemble classification algorithms
I am seeking to augment random forest classification using Shannon-Weaver mutual information as a metaheuristic to partition candidate datasets. Specifically, I am trying to determine if such an ...
- 163
6
votes
0
answers
480
views
Cheapest dissection of a grid polygon into rectangles with cost
My problem:
Dissect a grid polygon into rectangles. (A grid polygon is a rectilinear polygon all of whose vertices have integer coordinates.)
The rectangles must be taken from a predefined set (which ...
8
votes
0
answers
197
views
what is the best heuristic to solve 3AP with Euclidean costs?
As is well known, assignment problems for $n$-partite graphs, with $n$>2 are NP-hard, where as assignment problems on bipartite graphs can be solved in polynomial time using the Kuhn's Hungarian ...
- 81
7
votes
1
answer
510
views
Does this bin packing problem have a name?
My problem is related to the standard bin packing problem (where you have bins of capacity $1$, items of capacity $(0,1]$, and want to pack the items into as few bins as possible), but there are a ...
- 1,520
5
votes
2
answers
287
views
Self-organizing Sequential Search Heuristics
I've read the paper by Jon L. Bentley "Amortized analyses of self-organizing sequential search heuristics". It deals with different schemes for improving linear search. (such as after every access to ...
- 605
1
vote
0
answers
92
views
Resources to get started on fractional graph coloring algorithms
I'm interested in using fractional graph coloring algorithms/solvers to solve a problem, where is a good place to start? I'm looking to find basic/introductory to state-of-the-art algorithms more ...
- 11
13
votes
2
answers
586
views
Decentralized algorithm for determining influential nodes in social networks
In this paper by Kempe-Kleinberg-Tardos, the Authors propose a greedy algorithms based on submodular functions to determine the $k$ most influential nodes in a graph, with applications to social ...
- 203
5
votes
1
answer
168
views
Local Smoothness vs optimisation in combinatorial problems
Local smoothness is often mentioned in literature analysing different heuristics and meta-heuristics for combinatorial optimisation. What is meant precisely by local smoothness is often left out, but ...
- 835
13
votes
3
answers
1k
views
Successful application of branch-and-bound methods for NP-hard problems
Branch and bound is an effective heuristic for search problems, and Wikipedia lists a number of hard problems where branch-and-bound has been used. However, I haven't been able to find references to ...
- 32.2k
14
votes
4
answers
2k
views
Theoretical study of coordinate descent methods
I'm preparing some course material on heuristics for optimization, and have been looking at coordinate descent methods. The setting is here a multivariate function $f$ that you wish to optimize. $f$ ...
- 32.2k
4
votes
4
answers
672
views
A search problem and no algorithm for it
I would like to learn about the following search problem, in particular, which kind of algorithms exist for it.
Suppose we have a huge search space $S$. For each element $s \in S$, we have the weight ...
- 1,163
2
votes
3
answers
405
views
Heuristics for graph bisection
i'm trying to find an algorithm
that will divide my graph in 2 parts by telling me what connections should be broken
but the 2 parts should contain about the same number of nodes
its for a practical ...
- 169
9
votes
1
answer
348
views
Heuristics for Optimization
Since it's Friday, it's time for a CW question. I'm looking for heuristics that have wide use in optimization problems. To limit the scope to more 'theory-friendly' heuristics, here are the rules (...
7
votes
0
answers
161
views
Does the cohomological approach to Boolean complexity nicely model any BDD heuristics?
In this question, I learned that complexity theorists had considered using Grothendieck topologies to model Boolean circuits. This has not, apparently, led to any new lower bounds yet, but I'm not so ...
- 32.9k
26
votes
5
answers
11k
views
What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?
Stable Marriage Problem: http://en.wikipedia.org/wiki/Stable_marriage_problem
I am aware that for an instance of a SMP, many other stable marriages are possible apart from the one returned by the ...
- 363
7
votes
0
answers
356
views
Good MCMC methods for exploring the space of independent sets
Let $G$ be an edge-weighted graph, and let (S, V-S) be a feasible pair if S is a maximal independent set. The weight of a feasible pair is computed by finding for each element of V-S the lightest edge ...
- 32.2k
2
votes
2
answers
915
views
Ant colony optimization for traveling salesman problem with changing graph-nodes/vertices
Are there any publications focusing on solving TSP with ant colony optimization that consider small changes in the graph's nodes or vertices?
So what I have is:
a traveling salesman problem (TSP)
...
- 123