5

The convergence of classical iterative solvers for linear systems is determined by the spectral radius of the iteration matrix, $\rho(\mathbf{G})$. For a general linear system, it is difficult to determine an optimal (or even good) SOR parameter due to the difficulty in determining the spectral radius of the iteration matrix. Below I have included many ...


5

You will typically get the most significant steps forward if you can concisely state a problem in terms of mathematics. When you have a concise formulation in terms of what the free variables are what the objective function is what the constraints are then the next step is to find algorithms that are well-suited to the problem at hand (e.g., can you show ...


5

The following paper S. D. Prestwich, "Local search and backtracking vs non-systematic backtracking," in AAAI 2001 Fall Symp. Uncertainty Computation, 2001. Alternative link to a PDF. has a thorough comparison of local search vs. backtracking-like algorithm. In the introduction, it even features a question: "What is the essential difference between local ...


2

Doing a fast search in GitHub you can find A MATLAB implementation; A Python implementation; and A C implementation.


2

Established methodologies for benchmarking optimization software can be found in publications such as Benchmarking Optimization Software with Performance Profiles, Benchmarking Derivative-Free Optimization Algorithms, and Derivative-free optimization: a review of algorithms and comparison of software implementations. Generally speaking, algorithms are ...


1

Yes, you are optimizing a knapsack problem. The objects, or "items" in most knapsack problem (KP) definitions, in your case is a set $S=\{s_{00}, s_{01}, ..,s_{0n}, s_{10}, .. s_{kn}\}$, which contains composite keyword-bid pairs, so $s_{ij}$ denotes an object labeled "keyword $i$ bid $j$". The reason you should think of your items as composite this way ...


1

The algorithm described by Rashedi et al in the paper you mentioned is not strictly a gravitational search algorithm. In their equation (7), the magnitude of the force of attraction is inversely proportional to the distance between agents. Rashedi et al claim that they get better results with equation (7) instead of the (classically) correct inverse square ...


1

The running time of the algorithm is the sum of its subcomponents. Thus, the complexity is the asymptotically worst case complexity of the subcomponents. Experimentally, you just run the algorithms at different problem sizes (or numbers of constraints, or both) and plot/fit the resulting data. You need to make sure that you run the problem out to a large ...


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