Academic
Publications
Combining multiple heuristics on discrete resources

Combining multiple heuristics on discrete resources,10.1109/IPDPS.2009.5160879,Marin Bougeret,Pierre-françois Dutot,Alfredo Goldman,Yanik Ngoko,Denis

Combining multiple heuristics on discrete resources   (Citations: 1)
BibTex | RIS | RefWorks Download
In this work we study the portfolio problem which is to find a good combination of multiple heuristics to solve given instances on parallel resources in minimum time. The resources are assumed to be discrete, it is not possible to allocate a resource to more than one heuristic. Our goal is to minimize the average completion time of the set of instances, given a set of heuristics on homogeneous discrete resources. This problem has been studied in the continuous case in (18). We first show that the problem is hard and that there is no constant ratio polynomial approximation in the general case. Then, we design several approximation schemes for a restricted version of the problem where each heuristic must be used at least once. These results are obtained by using oracle with several guesses, leading to various tradeoff between the size of required information and the approximation ratio. Some additional results based on experiments are finally reported using a benchmark of instances on SAT solvers.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...In the first approach, we improve a problem introduced in [7, 4] such as to reduce the number of unsolved SAT instances...
    • ...This problem can be informally recalled as follows: given a set of opportunities, an amount of possible investments on the set of opportunities and the payoff obtained when investing an amount on each opportunity, what is the best amount of investment to make on each opportunity in order to maximize the sum of the payoffs? This scheme can be adapted to algorithms using the algorithm portfolio approach [2, 1, 7, 4]. A portfolio of ...
    • ...Morever the interest to allocate for every instance to solve the adequate resources on more than one algorithm is that we may not know which is the best suited SAT solver for each instance before actually solving it. Our proposed approaches aim at improving those introduced in [7, 4] from the observation that they do not focus on the necessity to provide an answer for all the considered instances...
    • ...In [7, 3, 4] the authors study how resources can be shared for SAT solvers such as to efficiently solve instances closed to those of a predefined benchmark...
    • ...The first model has been suggested in [4] and is based on a general problem (discrete Resource Sharing Scheduling Problem, dRSSP) that we improve for the case of SAT...
    • ...In Section 3, we consider the CBALapproach when there exists a benchmark of instances and propose an algorithm based on the discrete Resource Sharing Problem (dRSSP) introduced in [4]...
    • ...Given a set of algorithms A and a set of instances I, one interesting property here is that the optimal solution using the CBALis always at least as good as the best algorithm a opt ∈A executed on the set of instances in I. A particular case using the CBAL approach consists in considering the MA (Mean Allocation) algorithm [4] which given a resource decomposition m = qk + r (where 0 ≤ r<k ) allocates q +1 resources to r algorithms ai, 1 ...
    • ...The first model is based on thedRSSP problem presented in [4]...
    • ...Theorem 3.1. dRSSP with linear cost assumption is NP-Complete and it is not approximable unless P = NP [4]...
    • ...We refer the reader to [4] for the details...
    • ...In [4], many approximation schemes are provided for dRSSP using an oracle based approach...
    • ...MA G2 (x) proposed in [4] to solve dRSSP .G ivenk candidate algorithms and a value x, this scheme produces a k/xapproximation of the optimal solution where each candidate algorithm has at least one resource...
    • ...The first model extends the dRSSP introduced in [4] to combine in such a way to take into account the cutoff time...

    Yanik Ngokoet al. Combining SAT solvers on discrete resources

Sort by: