001package org.cpsolver.ifs.solver;
002
003import java.util.ArrayList;
004import java.util.HashMap;
005import java.util.List;
006import java.util.Map;
007import java.util.concurrent.locks.Lock;
008
009import org.cpsolver.ifs.assignment.Assignment;
010import org.cpsolver.ifs.assignment.DefaultParallelAssignment;
011import org.cpsolver.ifs.assignment.DefaultSingleAssignment;
012import org.cpsolver.ifs.assignment.InheritedAssignment;
013import org.cpsolver.ifs.model.Model;
014import org.cpsolver.ifs.model.Neighbour;
015import org.cpsolver.ifs.model.Value;
016import org.cpsolver.ifs.model.Variable;
017import org.cpsolver.ifs.solution.Solution;
018import org.cpsolver.ifs.solution.SolutionListener;
019import org.cpsolver.ifs.util.DataProperties;
020import org.cpsolver.ifs.util.JProf;
021import org.cpsolver.ifs.util.Progress;
022import org.cpsolver.ifs.util.ToolBox;
023
024
025/**
026 * Multi-threaded solver. Instead of one, a given number of solver threads are created
027 * (as defined by Parallel.NrSolvers property) and started in parallel. Each thread
028 * works with its own assignment {@link DefaultParallelAssignment}, but the best solution
029 * is shared among all of them.<br>
030 * <br>
031 * When {@link DefaultSingleAssignment} is given to the solver, only one solution is used.
032 * A neighbour is assigned to this (shared) solution when it does not create any conflicts
033 * outside of {@link Neighbour#assignments()}.
034 * 
035 * @see Solver
036 * 
037 * @version IFS 1.3 (Iterative Forward Search)<br>
038 *          Copyright (C) 2014 Tomas Muller<br>
039 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
040 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
041 * <br>
042 *          This library is free software; you can redistribute it and/or modify
043 *          it under the terms of the GNU Lesser General Public License as
044 *          published by the Free Software Foundation; either version 3 of the
045 *          License, or (at your option) any later version. <br>
046 * <br>
047 *          This library is distributed in the hope that it will be useful, but
048 *          WITHOUT ANY WARRANTY; without even the implied warranty of
049 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
050 *          Lesser General Public License for more details. <br>
051 * <br>
052 *          You should have received a copy of the GNU Lesser General Public
053 *          License along with this library; if not see <a href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>.
054 *
055 * @param <V> Variable
056 * @param <T> Value
057 **/
058public class ParallelSolver<V extends Variable<V, T>, T extends Value<V, T>> extends Solver<V, T> {
059    private SynchronizationThread iSynchronizationThread = null;
060    private int iNrFinished = 0;
061    
062    public ParallelSolver(DataProperties properties) {
063        super(properties);
064    }
065    
066    /** Starts solver */
067    @Override
068    public void start() {
069        int nrSolvers = Math.abs(getProperties().getPropertyInt("Parallel.NrSolvers", 4));
070        if (nrSolvers == 1) {
071            super.start();
072        } else {
073            iSynchronizationThread = new SynchronizationThread(nrSolvers);
074            iSynchronizationThread.setPriority(THREAD_PRIORITY);
075            iSynchronizationThread.start();
076        }
077    }
078    
079    /** Returns solver's thread */
080    @Override
081    public Thread getSolverThread() {
082        return iSynchronizationThread != null ? iSynchronizationThread : super.getSolverThread();
083    }
084    
085    /** Sets initial solution */
086    @Override
087    public void setInitalSolution(Model<V, T> model) {
088        int nrSolvers = Math.abs(getProperties().getPropertyInt("Parallel.NrSolvers", 4));
089        boolean updateMasterSolution = getProperties().getPropertyBoolean("Parallel.UpdateMasterSolution", false);
090        setInitalSolution(new Solution<V, T>(model, nrSolvers > 1 ? new DefaultParallelAssignment<V, T>(updateMasterSolution ? 1 : 0) : new DefaultSingleAssignment<V, T>(), 0, 0));
091    }
092    
093    /**
094     * Return a working (parallel) solution that contributed to the best solution last.
095     * @return working solution
096     */
097    protected Solution<V, T> getWorkingSolution() {
098        if (iSynchronizationThread != null && !hasSingleSolution()) {
099            int idx = currentSolution().getBestIndex();
100            if (idx < 0) idx = 0; // take the first thread solution if there was no best solution saved yet
101            if (idx < iSynchronizationThread.iSolvers.size())
102                return iSynchronizationThread.iSolvers.get(idx).iSolution;
103        }
104        return currentSolution();
105    }
106    
107    /**
108     * Synchronization thread
109     */
110    protected class SynchronizationThread extends Thread {
111        private int iNrSolvers;
112        private List<SolverThread> iSolvers = new ArrayList<SolverThread>();
113        
114        SynchronizationThread(int nrSolvers) {
115            iNrSolvers = nrSolvers;
116        }
117        
118        @Override
119        public void run() {
120            iStop = false;
121            iNrFinished = 0;
122            setName("SolverSync");
123            
124            // Initialization
125            iProgress = Progress.getInstance(currentSolution().getModel());
126            iProgress.setStatus("Solving problem ...");
127            iProgress.setPhase("Initializing solver");
128            initSolver();
129            onStart();
130            
131            double startTime = JProf.currentTimeSec();
132            if (isUpdateProgress()) {
133                if (currentSolution().getBestInfo() == null) {
134                    iProgress.setPhase("Searching for initial solution ...", currentSolution().getModel().variables().size());
135                } else {
136                    iProgress.setPhase("Improving found solution ...");
137                }
138            }
139            sLogger.info("Initial solution:" + ToolBox.dict2string(currentSolution().getInfo(), 2));
140            if ((iSaveBestUnassigned < 0 || iSaveBestUnassigned >= currentSolution().getAssignment().nrUnassignedVariables(currentSolution().getModel())) && (currentSolution().getBestInfo() == null || getSolutionComparator().isBetterThanBestSolution(currentSolution()))) {
141                if (currentSolution().getAssignment().nrAssignedVariables() == currentSolution().getModel().variables().size())
142                    sLogger.info("Complete solution " + ToolBox.dict2string(currentSolution().getInfo(), 1) + " was found.");
143                currentSolution().saveBest();
144            }
145
146            if (currentSolution().getModel().variables().isEmpty()) {
147                iProgress.error("Nothing to solve.");
148                iStop = true;
149            }
150            
151            if (!iStop) {
152                for (int i = 1; i <= iNrSolvers; i++) {
153                    SolverThread thread = new SolverThread(i, startTime);
154                    thread.setPriority(THREAD_PRIORITY);
155                    thread.setName("Solver-" + i);
156                    thread.start();
157                    iSolvers.add(thread);
158                }
159            }
160            
161            int timeout = getProperties().getPropertyInt("Termination.TimeOut", 1800);
162            double start = JProf.currentTimeSec();
163            while (!iStop && iNrFinished < iNrSolvers) {
164                try {
165                    Thread.sleep(1000);
166                    double time = JProf.currentTimeSec() - start;
167                    
168                    // Increment progress bar
169                    if (isUpdateProgress()) {
170                        if (currentSolution().getBestInfo() != null && currentSolution().getModel().getBestUnassignedVariables() == 0) {
171                            if (!"Improving found solution ...".equals(iProgress.getPhase()))
172                                iProgress.setPhase("Improving found solution ...");
173                            iProgress.setProgress(Math.min(100, (int)Math.round(100 * time / timeout)));
174                        } else if (currentSolution().getModel().getBestUnassignedVariables() > 0 && (currentSolution().getModel().countVariables() - currentSolution().getModel().getBestUnassignedVariables() > iProgress.getProgress())) {
175                            iProgress.setProgress(currentSolution().getModel().countVariables() - currentSolution().getModel().getBestUnassignedVariables());
176                        } else if (iSolvers.get(0).iAssignment.nrAssignedVariables() > iProgress.getProgress()) {
177                            iProgress.setProgress(iSolvers.get(0).iAssignment.nrAssignedVariables());
178                        }
179                    }
180                } catch (InterruptedException e) {}
181            }
182            
183            boolean stop = iStop; iStop = true;
184            for (SolverThread thread: iSolvers) {
185                try {
186                    thread.join();
187                } catch (InterruptedException e) {}
188            }
189            
190            // Finalization
191            iLastSolution = iCurrentSolution;
192
193            iProgress.setPhase("Done", 1);
194            iProgress.incProgress();
195
196            iSynchronizationThread = null;
197            if (stop) {
198                sLogger.debug("Solver stopped.");
199                iProgress.setStatus("Solver stopped.");
200                onStop();
201            } else {
202                sLogger.debug("Solver done.");
203                iProgress.setStatus("Solver done.");
204                onFinish();
205            }
206        }
207    }
208    
209    /**
210     * Create a solution that is to be used by a solver thread of the given index
211     * @param index solver thread index
212     * @return new solution to work with
213     */
214    protected Solution<V, T> createParallelSolution(int index) {
215        Model<V, T> model = iCurrentSolution.getModel();
216        Assignment<V, T> assignment = new DefaultParallelAssignment<V, T>(index, model, iCurrentSolution.getAssignment());
217        model.createAssignmentContexts(assignment, true);
218        Solution<V, T> solution = new Solution<V, T>(model, assignment);
219        for (SolutionListener<V, T> listener: iCurrentSolution.getSolutionListeners())
220            solution.addSolutionListener(listener);
221        return solution;
222    }
223    
224    /**
225     * Returns true if the solver works only with one solution (regardless the number of threads it is using)
226     * @return true if the current solution is {@link DefaultSingleAssignment}
227     */
228    @Override
229    public boolean hasSingleSolution() {
230        return iCurrentSolution.getAssignment() instanceof DefaultSingleAssignment;
231    }
232    
233    /**
234     * Solver thread
235     */
236    protected class SolverThread extends Thread {
237        private double iStartTime;
238        private int iIndex;
239        private boolean iSingle;
240        private Model<V, T> iModel;
241        private Solution<V, T> iSolution;
242        private Assignment<V, T> iAssignment;
243        
244        public SolverThread(int index, double startTime) {
245            iIndex = index;
246            iStartTime = startTime;
247            iSingle = hasSingleSolution();
248            iModel = iCurrentSolution.getModel();
249            iSolution = (iSingle || iCurrentSolution.getAssignment().getIndex() == index ? iCurrentSolution : createParallelSolution(iIndex));
250            iAssignment = iSolution.getAssignment();
251        }
252        
253        @Override
254        public void run() {
255            try {
256                while (!iStop) {
257                    // Break if cannot continue
258                    if (!getTerminationCondition().canContinue(iSolution)) break;
259                    
260                    // Create a sub-solution if needed
261                    Solution<V, T> current = (iSingle ? new Solution<V, T>(iModel, new InheritedAssignment<V, T>(iSolution.getAssignment()), iSolution.getIteration(), iSolution.getTime()) : iSolution);
262
263                    // Neighbour selection
264                    Neighbour<V, T> neighbour = null;
265                    try {
266                        neighbour = getNeighbourSelection().selectNeighbour(current);
267                    } catch (Exception e) {
268                        sLogger.warn("Failed to select a neighbour: " + (e.getMessage() == null ? e.getClass().getSimpleName() : e.getMessage()));
269                    }
270                    for (SolverListener<V, T> listener : iSolverListeners) {
271                        if (!listener.neighbourSelected(iAssignment, iSolution.getIteration(), neighbour)) {
272                            neighbour = null;
273                            continue;
274                        }
275                    }
276
277                    double time = JProf.currentTimeSec() - iStartTime;
278                    if (neighbour == null) {
279                        sLogger.debug("No neighbour selected.");
280                        // still update the solution (increase iteration etc.)
281                        iSolution.update(time, false);
282                        continue;
283                    }
284                    
285                    if (iSingle) {
286                        Map<V, T> assignments = null;
287                        try {
288                            assignments = neighbour.assignments();
289                        } catch (UnsupportedOperationException e) {
290                            sLogger.error("Failed to enumerate " + neighbour.getClass().getSimpleName(), e);
291                        }
292                        if (assignments == null) {
293                            sLogger.debug("No assignments returned.");
294                            // still update the solution (increase iteration etc.)
295                            iSolution.update(time, false);
296                            continue;
297                        }
298                        
299                        // Assign selected value to the selected variable
300                        Lock lock = iSolution.getLock().writeLock();
301                        lock.lock();
302                        try {
303                            Map<V, T> undo = new HashMap<V, T>();
304                            for (V var: assignments.keySet())
305                                undo.put(var, iSolution.getAssignment().unassign(iSolution.getIteration(), var));
306                            boolean fail = false;
307                            for (T val: assignments.values()) {
308                                if (val == null) continue;
309                                if (iModel.inConflict(iSolution.getAssignment(), val)) {
310                                    fail = true; break;
311                                }
312                                iSolution.getAssignment().assign(iSolution.getIteration(), val);
313                            }
314                            if (fail) {
315                                for (V var: undo.keySet())
316                                    iSolution.getAssignment().unassign(iSolution.getIteration(), var);
317                                for (T val: undo.values())
318                                    if (val != null)
319                                        iSolution.getAssignment().assign(iSolution.getIteration(), val);
320                            }
321                            iSolution.update(time, !fail);
322                            if (fail) {
323                                for (SolverListener<V, T> listener : iSolverListeners)
324                                    listener.neighbourFailed(current.getAssignment(), iSolution.getIteration(), neighbour);
325                                continue;
326                            }
327                            
328                            onAssigned(iStartTime, iSolution);
329
330                            if ((iSaveBestUnassigned < 0 || iSaveBestUnassigned >= iSolution.getAssignment().nrUnassignedVariables(iModel)) && getSolutionComparator().isBetterThanBestSolution(iSolution)) {
331                                iSolution.saveBest();
332                            }
333                        } finally {
334                            lock.unlock();
335                        }
336                    } else {
337                        // Assign selected value to the selected variable
338                        Lock lock = iSolution.getLock().writeLock();
339                        lock.lock();
340                        try {
341                            neighbour.assign(iAssignment, iSolution.getIteration());
342                            iSolution.update(time);
343                        } finally {
344                            lock.unlock();
345                        }
346
347                        onAssigned(iStartTime, iSolution);
348                        
349                        if (iSaveBestUnassigned < 0 || iSaveBestUnassigned >= iAssignment.nrUnassignedVariables(iModel))
350                            iSolution.saveBestIfImproving(currentSolution(), getSolutionComparator());
351                    }
352                }
353
354            } catch (Exception ex) {
355                sLogger.error(ex.getMessage(), ex);
356                iProgress.fatal(getName() + " failed, reason:" + ex.getMessage(), ex);
357                if (iIndex == 0) {
358                    iProgress.setStatus("Solver failed.");
359                    onFailure();
360                }
361            }
362            Lock lock = currentSolution().getLock().writeLock();
363            lock.lock();
364            try {
365                iNrFinished ++;
366            } finally {
367                lock.unlock();
368            }
369        }
370        
371    }
372}