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