New answers tagged optimization
1
These days, the trend is to do optimization with the intermediate representation. Check out LLVM for example:
The LLVM Core libraries provide a modern source- and target-independent optimizer, along with code generation support for many popular CPUs (as well as some less common ones!) These libraries are built around a well specified code representation ...
0
No, I don't think your formalization is heading in a useful direction. It seems convoluted and focused on one particular algorithm, but there might be other optimization algorithms that you haven't considered.
I don't expect there to be a useful characterization of which objective functions can and can't be optimized effectively. It's a notoriously hard ...
0
If you consider each task as a node of a graph, and each conflict as an edge, this is a weighted maximum independent set problem.
It is NP-hard, but you should get good results with a mixed integer programming solver, such as CBC.
3
Some SAT solvers and SMT solvers offer an interface that lets you push clauses, and then later pop/retract them and push some new ones. You could explore to see whether this offers a speedup in your situation. There are no guarantees, and the only way to tell is to try it.
1
This is a discrete optimization problem. I think one possible approach would be to approximate the discrete elements with continuous, differentiable functions and then optimize the resulting substitute problem.
Consider the function $f(x)=1$ if $x\ge 0$, or $f(x)=0$ if $x<0$. This is a discrete function, which can be approximated by the sigmoid function ...
0
Let $a_{ij}$ represent member of matrix $A$. This can either be the constant $0$ if you want $a_{ij}$ to be $0$ in the solution matrix, or a variable for a linear programming problem. Then you want to add linear constraints:
\begin{alignat}{2}
&\!\min_{a} &\qquad& \sum_{i} s_i\\
&\text{subject to} & & \forall j \left(\sum_{...
1
Let the array consist of the numbers $a_0,\ldots,a_{n-1}$, and let the mask be $b_0,\ldots,b_{k-1}$. Define
$$
A = \sum_i a_i x^i, \quad
B = \sum_j b_j x^{k-1-j}.
$$
Notice that
$$
AB = \sum_{i,j} a_i b_j x^{i+k-1-j},
$$
and so the coefficient of $x^{i+k-1}$ in $AB$ is
$$
\sum_{j=i}^{i+k-1} a_j b_{j-i}.
$$
Therefore if you can calculate $AB$, you can solve ...
0
It's impossible to say without knowing the properties of your keys. Programming language symbol tables tend to need to store a bunch of strings that look like i, j, x1, x2, y1, y2, etc. Simple hash functions often don't disambiguate these well.
There are plenty of hash functions out there. PJW hash/ElfHash is popular for programming languages because it was ...
1
If you are able to find the least expensive picks in linear (or even polynomial) time then $P=NP$.
Your problem is a generalization of the set-cover problem: given a set $X$ of items and a collection $S = \{S_1, \dots, S_m \} \subseteq 2^X$ of subsets of $X$, find $S' \subseteq S$ such that $\cup_{S_i \in S'} S_i = X$ and $|S'|$ is minimized.
This is exactly ...
0
Your example is an unfortunate one. Since you are sorting integers, you can pose a specific requirement to sort, such as the value, if that is the only thing to sort on you can use the radix sort, which would put the complexity at O(#ofdigitsn) or O(kn) which is 99% of cases is much better than lg(n), the only reason is sorting alrogithm isn't used more ...
1
Your objective function is indeed not convex, but you can make it convex with the appropriate transformation, which means it is solvable in polynomial time. But applying this reformulation is complex: you should try a non-convex solver first and stop there if it works in practice.
The easy way: Non-convex quadratic model
As pointed in the comments, it is a ...
0
It's hard to know what to recommend, without more context.
One possible approach is to use hill-climbing, simulated annealing, or some other form of local search. A simple form of hill-climbing is to pick a random variable, determine whether increasing/decreasing it will improve your model, and if so, increase/decrease it; then repeat until no further ...
2
You ask if we could derive a more efficent way to compute even? Yes, we could of course. The point however is that compilers could not.
Having a compiler automatically perform very fancy optimization techniques is a hard problem. In fact, if you ask for too much the problem may become undecidable, and for almost all interesting cases at least extremely hard....
0
I'd propose this idea:
Let the algorithm run almost naturally, but if it encounters a shortest column that has no options left, do not backtrack immediately. Instead, ignore that column and pick another one. Do this up to four times per iteration. Once more than 4 columns have no options, do backtrack as you normally would.
This will eventually run until a ...
Top 50 recent answers are included
