001package org.cpsolver.ifs.solver;
002
003import java.util.ArrayList;
004import java.util.Collection;
005import java.util.HashMap;
006import java.util.List;
007import java.util.Map;
008import java.util.concurrent.ArrayBlockingQueue;
009import java.util.concurrent.BlockingQueue;
010import java.util.concurrent.TimeUnit;
011import java.util.concurrent.locks.Lock;
012
013import org.cpsolver.ifs.assignment.Assignment;
014import org.cpsolver.ifs.assignment.DefaultParallelAssignment;
015import org.cpsolver.ifs.assignment.DefaultSingleAssignment;
016import org.cpsolver.ifs.assignment.context.CanHoldContext;
017import org.cpsolver.ifs.model.LazyNeighbour;
018import org.cpsolver.ifs.model.LazyNeighbour.LazyNeighbourAcceptanceCriterion;
019import org.cpsolver.ifs.model.Model;
020import org.cpsolver.ifs.model.Neighbour;
021import org.cpsolver.ifs.model.Value;
022import org.cpsolver.ifs.model.Variable;
023import org.cpsolver.ifs.solution.Solution;
024import org.cpsolver.ifs.solution.SolutionListener;
025import org.cpsolver.ifs.util.DataProperties;
026import org.cpsolver.ifs.util.JProf;
027import org.cpsolver.ifs.util.Progress;
028import org.cpsolver.ifs.util.ToolBox;
029
030
031/**
032 * Multi-threaded solver. Instead of one, a given number of solver threads are created
033 * (as defined by Parallel.NrSolvers property) and started in parallel. Each thread
034 * works with its own assignment {@link DefaultParallelAssignment}, but the best solution
035 * is shared among all of them.<br>
036 * <br>
037 * When {@link DefaultSingleAssignment} is given to the solver, only one solution is used.
038 * A neighbour is assigned to this (shared) solution when it does not create any conflicts
039 * outside of {@link Neighbour#assignments()}.
040 * 
041 * @see Solver
042 * 
043 * @version IFS 1.3 (Iterative Forward Search)<br>
044 *          Copyright (C) 2014 Tomas Muller<br>
045 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
046 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
047 * <br>
048 *          This library is free software; you can redistribute it and/or modify
049 *          it under the terms of the GNU Lesser General Public License as
050 *          published by the Free Software Foundation; either version 3 of the
051 *          License, or (at your option) any later version. <br>
052 * <br>
053 *          This library is distributed in the hope that it will be useful, but
054 *          WITHOUT ANY WARRANTY; without even the implied warranty of
055 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
056 *          Lesser General Public License for more details. <br>
057 * <br>
058 *          You should have received a copy of the GNU Lesser General Public
059 *          License along with this library; if not see <a href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>.
060 *
061 * @param <V> Variable
062 * @param <T> Value
063 **/
064public class ParallelSolver<V extends Variable<V, T>, T extends Value<V, T>> extends Solver<V, T> {
065    private SynchronizationThread iSynchronizationThread = null;
066    private int iNrFinished = 0;
067    
068    public ParallelSolver(DataProperties properties) {
069        super(properties);
070    }
071    
072    /** Starts solver */
073    @Override
074    public void start() {
075        int nrSolvers = Math.min(Math.abs(getProperties().getPropertyInt("Parallel.NrSolvers", 4)), CanHoldContext.sMaxSize - 1);
076        if (nrSolvers == 1) {
077            super.start();
078        } else {
079            iSynchronizationThread = new SynchronizationThread(nrSolvers);
080            iSynchronizationThread.setPriority(THREAD_PRIORITY);
081            iSynchronizationThread.start();
082        }
083    }
084    
085    /** Returns solver's thread */
086    @Override
087    public Thread getSolverThread() {
088        return iSynchronizationThread != null ? iSynchronizationThread : super.getSolverThread();
089    }
090    
091    /** Sets initial solution */
092    @Override
093    public void setInitalSolution(Model<V, T> model) {
094        int nrSolvers = Math.min(Math.abs(getProperties().getPropertyInt("Parallel.NrSolvers", 4)), CanHoldContext.sMaxSize - 1);
095        boolean updateMasterSolution = getProperties().getPropertyBoolean("Parallel.UpdateMasterSolution", true);
096        setInitalSolution(new Solution<V, T>(model, nrSolvers > 1 ? new DefaultParallelAssignment<V, T>(updateMasterSolution ? 1 : 0) : new DefaultSingleAssignment<V, T>(), 0, 0));
097    }
098    
099    /**
100     * Return a working (parallel) solution that contributed to the best solution last.
101     * @return working solution
102     */
103    protected Solution<V, T> getWorkingSolution() {
104        if (iSynchronizationThread != null && !hasSingleSolution()) {
105            int idx = currentSolution().getBestIndex();
106            if (idx < 0) idx = 0; // take the first thread solution if there was no best solution saved yet
107            if (idx < iSynchronizationThread.iSolvers.size())
108                return iSynchronizationThread.iSolvers.get(idx).iSolution;
109        }
110        return currentSolution();
111    }
112    
113    /**
114     * Synchronization thread
115     */
116    protected class SynchronizationThread extends Thread {
117        private int iNrSolvers;
118        private List<SolverThread> iSolvers = new ArrayList<SolverThread>();
119        private AssignmentThread iAssignmentThread = null;
120        
121        SynchronizationThread(int nrSolvers) {
122            iNrSolvers = nrSolvers;
123        }
124        
125        @Override
126        public void run() {
127            iStop = false;
128            iNrFinished = 0;
129            setName("SolverSync");
130            
131            // Initialization
132            iProgress = Progress.getInstance(currentSolution().getModel());
133            iProgress.setStatus("Solving problem ...");
134            iProgress.setPhase("Initializing solver");
135            initSolver();
136            onStart();
137            
138            if (isUpdateProgress()) {
139                if (currentSolution().getBestInfo() == null) {
140                    iProgress.setPhase("Searching for initial solution ...", currentSolution().getModel().variables().size());
141                } else {
142                    iProgress.setPhase("Improving found solution ...");
143                }
144            }
145            sLogger.info("Initial solution:" + ToolBox.dict2string(currentSolution().getInfo(), 2));
146            if ((iSaveBestUnassigned < 0 || iSaveBestUnassigned >= currentSolution().getAssignment().nrUnassignedVariables(currentSolution().getModel())) && (currentSolution().getBestInfo() == null || getSolutionComparator().isBetterThanBestSolution(currentSolution()))) {
147                if (currentSolution().getAssignment().nrAssignedVariables() == currentSolution().getModel().variables().size())
148                    sLogger.info("Complete solution " + ToolBox.dict2string(currentSolution().getInfo(), 1) + " was found.");
149                currentSolution().saveBest();
150            }
151
152            if (currentSolution().getModel().variables().isEmpty()) {
153                iProgress.error("Nothing to solve.");
154                iStop = true;
155            }
156            
157            BlockingQueue<Neighbour<V, T>> queue = null;
158            if (hasSingleSolution() && iNrSolvers > 1 && getProperties().getPropertyBoolean("ParallelSolver.SingleSolutionQueue", false))
159                queue = new ArrayBlockingQueue<Neighbour<V, T>>(2 * iNrSolvers);
160            
161            if (!iStop) {
162                for (int i = 1; i <= iNrSolvers; i++) {
163                    SolverThread thread = new SolverThread(i, queue);
164                    thread.setPriority(THREAD_PRIORITY);
165                    thread.setName("Solver-" + i);
166                    thread.start();
167                    iSolvers.add(thread);
168                }
169            }
170            
171            if (queue != null) {
172                iAssignmentThread = new AssignmentThread(queue);
173                iAssignmentThread.start();
174            }
175            
176            int timeout = getProperties().getPropertyInt("Termination.TimeOut", 1800);
177            double start = JProf.currentTimeSec();
178            while (!iStop && iNrFinished < iNrSolvers) {
179                try {
180                    Thread.sleep(1000);
181                    double time = JProf.currentTimeSec() - start;
182                    
183                    // Increment progress bar
184                    if (isUpdateProgress()) {
185                        if (currentSolution().getBestInfo() != null && currentSolution().getModel().getBestUnassignedVariables() == 0) {
186                            if (!"Improving found solution ...".equals(iProgress.getPhase()))
187                                iProgress.setPhase("Improving found solution ...");
188                            iProgress.setProgress(Math.min(100, (int)Math.round(100 * time / timeout)));
189                        } else if (currentSolution().getModel().getBestUnassignedVariables() > 0 && (currentSolution().getModel().countVariables() - currentSolution().getModel().getBestUnassignedVariables() > iProgress.getProgress())) {
190                            iProgress.setProgress(currentSolution().getModel().countVariables() - currentSolution().getModel().getBestUnassignedVariables());
191                        } else if (iSolvers.get(0).iAssignment.nrAssignedVariables() > iProgress.getProgress()) {
192                            iProgress.setProgress(iSolvers.get(0).iAssignment.nrAssignedVariables());
193                        }
194                    }
195                } catch (InterruptedException e) {}
196            }
197            
198            boolean stop = iStop; iStop = true;
199            for (SolverThread thread: iSolvers) {
200                try {
201                    thread.join();
202                } catch (InterruptedException e) {}
203            }
204            if (iAssignmentThread != null) {
205                try {
206                    iAssignmentThread.join();
207                } catch (InterruptedException e) {}
208            }
209            
210            // Finalization
211            iLastSolution = iCurrentSolution;
212
213            iProgress.setPhase("Done", 1);
214            iProgress.incProgress();
215
216            iSynchronizationThread = null;
217            if (stop) {
218                sLogger.debug("Solver stopped.");
219                iProgress.setStatus("Solver stopped.");
220                onStop();
221            } else {
222                sLogger.debug("Solver done.");
223                iProgress.setStatus("Solver done.");
224                onFinish();
225            }
226        }
227    }
228    
229    /**
230     * Create a solution that is to be used by a solver thread of the given index
231     * @param index solver thread index
232     * @return new solution to work with
233     */
234    protected Solution<V, T> createParallelSolution(int index) {
235        Model<V, T> model = iCurrentSolution.getModel();
236        Assignment<V, T> assignment = new DefaultParallelAssignment<V, T>(index, model, iCurrentSolution.getAssignment());
237        model.createAssignmentContexts(assignment, true);
238        Solution<V, T> solution = new Solution<V, T>(model, assignment);
239        for (SolutionListener<V, T> listener: iCurrentSolution.getSolutionListeners())
240            solution.addSolutionListener(listener);
241        return solution;
242    }
243    
244    /**
245     * Returns true if the solver works only with one solution (regardless the number of threads it is using)
246     * @return true if the current solution is {@link DefaultSingleAssignment}
247     */
248    @Override
249    public boolean hasSingleSolution() {
250        return iCurrentSolution.getAssignment() instanceof DefaultSingleAssignment;
251    }
252    
253    /**
254     * Solver thread
255     */
256    protected class SolverThread extends Thread {
257        private double iStartTime;
258        private int iIndex;
259        private boolean iSingle;
260        private Model<V, T> iModel;
261        private Solution<V, T> iSolution;
262        private Assignment<V, T> iAssignment;
263        private BlockingQueue<Neighbour<V, T>> iQueue;
264        
265        public SolverThread(int index, BlockingQueue<Neighbour<V, T>> queue) {
266            iIndex = index;
267            iSingle = hasSingleSolution();
268            iModel = iCurrentSolution.getModel();
269            iSolution = (iSingle || iCurrentSolution.getAssignment().getIndex() == index ? iCurrentSolution : createParallelSolution(iIndex));
270            iAssignment = iSolution.getAssignment();
271            iQueue = queue;
272        }
273        
274        @Override
275        public void run() {
276            iStartTime = JProf.currentTimeSec();
277            try {
278                boolean neighbourCheck = getProperties().getPropertyBoolean("ParallelSolver.SingleSolutionNeighbourCheck", false);
279                boolean tryLazyFirst = getProperties().getPropertyBoolean("ParallelSolver.SingleSolutionTryLazyFirst", false);
280                
281                while (!iStop) {
282                    // Break if cannot continue
283                    if (!getTerminationCondition().canContinue(iSolution)) break;
284                    
285                    // Create a sub-solution if needed
286                    Solution<V, T> current = iSolution;
287                    if (iSingle) {
288                        current = new Solution<V, T>(iModel, iModel.createInheritedAssignment(iSolution, iIndex), iSolution.getIteration(), iSolution.getTime());
289                        current.addSolutionListener(new SolutionListener<V, T>() {
290                            @Override
291                            public void solutionUpdated(Solution<V, T> solution) {
292                            }
293
294                            @Override
295                            public void getInfo(Solution<V, T> solution, Map<String, String> info) {
296                            }
297
298                            @Override
299                            public void getInfo(Solution<V, T> solution, Map<String, String> info, Collection<V> variables) {
300                            }
301
302                            @Override
303                            public void bestCleared(Solution<V, T> solution) {
304                            }
305
306                            @Override
307                            public void bestSaved(Solution<V, T> solution) {
308                            }
309
310                            @Override
311                            public void bestRestored(Solution<V, T> solution) {
312                                iSolution.restoreBest();
313                            }
314                        });
315                    }
316
317                    // Neighbour selection
318                    Neighbour<V, T> neighbour = null;
319                    try {
320                        neighbour = getNeighbourSelection().selectNeighbour(current);
321                    } catch (Exception e) {
322                        sLogger.warn("Failed to select a neighbour: " + (e.getMessage() == null ? e.getClass().getSimpleName() : e.getMessage()));
323                    }
324                    for (SolverListener<V, T> listener : iSolverListeners) {
325                        if (!listener.neighbourSelected(iAssignment, iSolution.getIteration(), neighbour)) {
326                            neighbour = null;
327                            continue;
328                        }
329                    }
330
331                    double time = JProf.currentTimeSec() - iStartTime;
332                    if (neighbour == null) {
333                        sLogger.debug("No neighbour selected.");
334                        // still update the solution (increase iteration etc.)
335                        iSolution.update(time, false);
336                        continue;
337                    }
338                    
339                    if (iSingle) {
340                        if (iQueue != null) {
341                            do {
342                                if (iQueue.offer(neighbour, 1000, TimeUnit.MILLISECONDS)) break;
343                            } while (!iStop && getTerminationCondition().canContinue(iSolution));
344                            continue;
345                        }
346                        
347                        Map<V, T> assignments = null;
348                        try {
349                            assignments = neighbour.assignments();
350                        } catch (UnsupportedOperationException e) {
351                            sLogger.error("Failed to enumerate " + neighbour.getClass().getSimpleName(), e);
352                        }
353                        if (assignments == null) {
354                            sLogger.debug("No assignments returned.");
355                            // still update the solution (increase iteration etc.)
356                            iSolution.update(time, false);
357                            continue;
358                        }
359                        
360                        if (tryLazyFirst && neighbour instanceof LazyNeighbour) {
361                            LazyNeighbour<V, T> lazy = (LazyNeighbour<V, T>)neighbour;
362                            double before = current.getModel().getTotalValue(current.getAssignment());
363                            neighbour.assign(current.getAssignment(), current.getIteration());
364                            double after = current.getModel().getTotalValue(current.getAssignment());
365                            if (!lazy.getAcceptanceCriterion().accept(current.getAssignment(), lazy, after - before))
366                                continue;
367                        }
368                        
369                        // Assign selected value to the selected variable
370                        Lock lock = iSolution.getLock().writeLock();
371                        lock.lock();
372                        try {
373                            LazyNeighbourAcceptanceCriterion<V,T> lazy = null;
374                            double before = 0, value = 0;
375                            if (neighbour instanceof LazyNeighbour) {
376                                before = iSolution.getModel().getTotalValue(iSolution.getAssignment());
377                                lazy = ((LazyNeighbour<V, T>)neighbour).getAcceptanceCriterion();
378                            } else if (neighbourCheck) {
379                                before = iSolution.getModel().getTotalValue(iSolution.getAssignment());
380                                value = neighbour.value(current.getAssignment());
381                            }
382                            Map<V, T> undo = new HashMap<V, T>();
383                            for (V var: assignments.keySet())
384                                undo.put(var, iSolution.getAssignment().unassign(iSolution.getIteration(), var));
385                            boolean fail = false;
386                            for (T val: assignments.values()) {
387                                if (val == null) continue;
388                                if (iModel.inConflict(iSolution.getAssignment(), val)) {
389                                    fail = true; break;
390                                }
391                                iSolution.getAssignment().assign(iSolution.getIteration(), val);
392                            }
393                            if (!fail) {
394                                if (lazy != null) {
395                                    double after = iSolution.getModel().getTotalValue(iSolution.getAssignment());
396                                    if (!lazy.accept(iSolution.getAssignment(), (LazyNeighbour<V, T>) neighbour, after - before))
397                                        fail = true;
398                                } else if (neighbourCheck) {
399                                    double after = iSolution.getModel().getTotalValue(iSolution.getAssignment());
400                                    if (before + value < after && before < after && !getSolutionComparator().isBetterThanBestSolution(iSolution))
401                                        fail = true;
402                                }
403                            }
404                            if (fail) {
405                                for (V var: undo.keySet())
406                                    iSolution.getAssignment().unassign(iSolution.getIteration(), var);
407                                for (T val: undo.values())
408                                    if (val != null)
409                                        iSolution.getAssignment().assign(iSolution.getIteration(), val);
410                            }
411                            iSolution.update(time, !fail);
412                            if (fail) {
413                                for (SolverListener<V, T> listener : iSolverListeners)
414                                    listener.neighbourFailed(current.getAssignment(), iSolution.getIteration(), neighbour);
415                                continue;
416                            }
417                            
418                            onAssigned(iStartTime, iSolution);
419
420                            if ((iSaveBestUnassigned < 0 || iSaveBestUnassigned >= iSolution.getAssignment().nrUnassignedVariables(iModel)) && getSolutionComparator().isBetterThanBestSolution(iSolution)) {
421                                iSolution.saveBest();
422                            }
423                        } finally {
424                            lock.unlock();
425                        }
426                    } else {
427                        // Assign selected value to the selected variable
428                        Lock lock = iSolution.getLock().writeLock();
429                        lock.lock();
430                        try {
431                            neighbour.assign(iAssignment, iSolution.getIteration());
432                            iSolution.update(time, currentSolution());
433                        } finally {
434                            lock.unlock();
435                        }
436
437                        onAssigned(iStartTime, iSolution);
438                        
439                        if (iSaveBestUnassigned < 0 || iSaveBestUnassigned >= iAssignment.nrUnassignedVariables(iModel))
440                            iSolution.saveBestIfImproving(currentSolution(), getSolutionComparator());
441                    }
442                }
443
444            } catch (Exception ex) {
445                sLogger.error(ex.getMessage(), ex);
446                iProgress.fatal(getName() + " failed, reason:" + ex.getMessage(), ex);
447                if (iIndex == 0) {
448                    iProgress.setStatus("Solver failed.");
449                    onFailure();
450                }
451            }
452            Lock lock = currentSolution().getLock().writeLock();
453            lock.lock();
454            try {
455                iNrFinished ++;
456            } finally {
457                lock.unlock();
458            }
459        }
460        
461    }
462    
463    /**
464     * Solver thread
465     */
466    protected class AssignmentThread extends Thread {
467        private double iStartTime;
468        private Solution<V, T> iSolution;
469        private BlockingQueue<Neighbour<V, T>> iQueue;
470        
471        public AssignmentThread(BlockingQueue<Neighbour<V, T>> queue) {
472            setName("Assignment");
473            setPriority(1 + THREAD_PRIORITY);
474            iSolution = iCurrentSolution;
475            iQueue = queue;
476        }
477        
478        @Override
479        public void run() {
480            iStartTime = JProf.currentTimeSec();
481            try {
482                boolean neighbourCheck = getProperties().getPropertyBoolean("ParallelSolver.SingleSolutionNeighbourCheck", false);
483                
484                while (!iStop) {
485                    // Break if cannot continue
486                    if (!getTerminationCondition().canContinue(iSolution)) break;
487                    
488                    // Create a sub-solution if needed
489                    Neighbour<V, T> neighbour = iQueue.poll(1000, TimeUnit.MILLISECONDS);
490                    
491                    if (neighbour == null) continue;
492
493                    double time = JProf.currentTimeSec() - iStartTime;
494                    
495                    Map<V, T> assignments = null;
496                    try {
497                        assignments = neighbour.assignments();
498                    } catch (UnsupportedOperationException e) {
499                        sLogger.error("Failed to enumerate " + neighbour.getClass().getSimpleName(), e);
500                    }
501                    if (assignments == null) {
502                        sLogger.debug("No assignments returned.");
503                        // still update the solution (increase iteration etc.)
504                        iSolution.update(time, false);
505                        continue;
506                    }
507                    
508                    // Assign selected value to the selected variable
509                    Lock lock = iSolution.getLock().writeLock();
510                    lock.lock();
511                    try {
512                        LazyNeighbourAcceptanceCriterion<V,T> lazy = null;
513                        double before = 0, value = 0;
514                        if (neighbour instanceof LazyNeighbour) {
515                            before = iSolution.getModel().getTotalValue(iSolution.getAssignment());
516                            lazy = ((LazyNeighbour<V, T>)neighbour).getAcceptanceCriterion();
517                        } else if (neighbourCheck) {
518                            before = iSolution.getModel().getTotalValue(iSolution.getAssignment());
519                            value = neighbour.value(iSolution.getAssignment());
520                        }
521                        Map<V, T> undo = new HashMap<V, T>();
522                        for (V var: assignments.keySet())
523                            undo.put(var, iSolution.getAssignment().unassign(iSolution.getIteration(), var));
524                        boolean fail = false;
525                        for (T val: assignments.values()) {
526                            if (val == null) continue;
527                            if (iSolution.getModel().inConflict(iSolution.getAssignment(), val)) {
528                                fail = true; break;
529                            }
530                            iSolution.getAssignment().assign(iSolution.getIteration(), val);
531                        }
532                        if (!fail) {
533                            if (lazy != null) {
534                                double after = iSolution.getModel().getTotalValue(iSolution.getAssignment());
535                                if (!lazy.accept(iSolution.getAssignment(), (LazyNeighbour<V, T>) neighbour, after - before))
536                                    fail = true;
537                            } else if (neighbourCheck) {
538                                double after = iSolution.getModel().getTotalValue(iSolution.getAssignment());
539                                if (before + value < after && before < after && !getSolutionComparator().isBetterThanBestSolution(iSolution))
540                                    fail = true;
541                            }
542                        }
543                        if (fail) {
544                            for (V var: undo.keySet())
545                                iSolution.getAssignment().unassign(iSolution.getIteration(), var);
546                            for (T val: undo.values())
547                                if (val != null)
548                                    iSolution.getAssignment().assign(iSolution.getIteration(), val);
549                        }
550                        iSolution.update(time, !fail);
551                        if (fail) {
552                            for (SolverListener<V, T> listener : iSolverListeners)
553                                listener.neighbourFailed(iSolution.getAssignment(), iSolution.getIteration(), neighbour);
554                            continue;
555                        }
556                        
557                        onAssigned(iStartTime, iSolution);
558
559                        if ((iSaveBestUnassigned < 0 || iSaveBestUnassigned >= iSolution.getAssignment().nrUnassignedVariables(iSolution.getModel())) && getSolutionComparator().isBetterThanBestSolution(iSolution)) {
560                            iSolution.saveBest();
561                        }
562                    } finally {
563                        lock.unlock();
564                    }
565                }
566
567            } catch (Exception ex) {
568                sLogger.error(ex.getMessage(), ex);
569                iProgress.fatal(getName() + " failed, reason:" + ex.getMessage(), ex);
570            }
571            Lock lock = currentSolution().getLock().writeLock();
572            lock.lock();
573            try {
574                iNrFinished ++;
575            } finally {
576                lock.unlock();
577            }
578        }
579        
580    }
581
582}