View Javadoc

1   /*******************************************************************************
2    * SAT4J: a SATisfiability library for Java Copyright (C) 2004, 2012 Artois University and CNRS
3    *
4    * All rights reserved. This program and the accompanying materials
5    * are made available under the terms of the Eclipse Public License v1.0
6    * which accompanies this distribution, and is available at
7    *  http://www.eclipse.org/legal/epl-v10.html
8    *
9    * Alternatively, the contents of this file may be used under the terms of
10   * either the GNU Lesser General Public License Version 2.1 or later (the
11   * "LGPL"), in which case the provisions of the LGPL are applicable instead
12   * of those above. If you wish to allow use of your version of this file only
13   * under the terms of the LGPL, and not to allow others to use your version of
14   * this file under the terms of the EPL, indicate your decision by deleting
15   * the provisions above and replace them with the notice and other provisions
16   * required by the LGPL. If you do not delete the provisions above, a recipient
17   * may use your version of this file under the terms of the EPL or the LGPL.
18   *
19   * Based on the original MiniSat specification from:
20   *
21   * An extensible SAT solver. Niklas Een and Niklas Sorensson. Proceedings of the
22   * Sixth International Conference on Theory and Applications of Satisfiability
23   * Testing, LNCS 2919, pp 502-518, 2003.
24   *
25   * See www.minisat.se for the original solver in C++.
26   *
27   * Contributors:
28   *   CRIL - initial API and implementation
29   *******************************************************************************/
30  package org.sat4j;
31  
32  import java.io.PrintWriter;
33  
34  import org.sat4j.specs.ContradictionException;
35  import org.sat4j.specs.IOptimizationProblem;
36  import org.sat4j.specs.IProblem;
37  import org.sat4j.specs.TimeoutException;
38  
39  /**
40   * This class is intended to be used by launchers to solve optimization
41   * problems, i.e. problems for which a loop is needed to find the optimal
42   * solution.
43   * 
44   * This class is no longer used since 2.3.3
45   * 
46   * @see ILauncherMode
47   * 
48   * @author leberre
49   * 
50   */
51  @Deprecated
52  public abstract class AbstractOptimizationLauncher extends AbstractLauncher {
53  
54      /**
55  	 * 
56  	 */
57      private static final long serialVersionUID = 1L;
58  
59      private static final String CURRENT_OPTIMUM_VALUE_PREFIX = "o "; //$NON-NLS-1$
60  
61      private boolean incomplete = false;
62  
63      private boolean displaySolutionLine = true;
64  
65      @Override
66      protected void setIncomplete(boolean value) {
67          this.incomplete = value;
68      }
69  
70      @Override
71      protected void setDisplaySolutionLine(boolean value) {
72          this.displaySolutionLine = value;
73      }
74  
75      @Override
76      protected void displayResult() {
77          displayAnswer();
78  
79          log("Total wall clock time (in seconds): " //$NON-NLS-1$
80                  + (System.currentTimeMillis() - getBeginTime()) / 1000.0);
81      }
82  
83      protected void displayAnswer() {
84          if (this.solver == null) {
85              return;
86          }
87          System.out.flush();
88          PrintWriter out = getLogWriter();
89          out.flush();
90          this.solver.printStat(out, COMMENT_PREFIX);
91          this.solver.printInfos(out, COMMENT_PREFIX);
92          ExitCode exitCode = getExitCode();
93          out.println(ILauncherMode.ANSWER_PREFIX + exitCode);
94          if (exitCode == ExitCode.SATISFIABLE
95                  || exitCode == ExitCode.OPTIMUM_FOUND || this.incomplete
96                  && exitCode == ExitCode.UPPER_BOUND) {
97              if (this.displaySolutionLine) {
98                  out.print(ILauncherMode.SOLUTION_PREFIX);
99                  getReader().decode(this.solver.model(), out);
100                 out.println();
101             }
102             IOptimizationProblem optproblem = (IOptimizationProblem) this.solver;
103             if (!optproblem.hasNoObjectiveFunction()) {
104                 log("objective function=" + optproblem.getObjectiveValue()); //$NON-NLS-1$
105             }
106         }
107     }
108 
109     @Override
110     protected void solve(IProblem problem) throws TimeoutException {
111         boolean isSatisfiable = false;
112 
113         IOptimizationProblem optproblem = (IOptimizationProblem) problem;
114 
115         try {
116             while (optproblem.admitABetterSolution()) {
117                 if (!isSatisfiable) {
118                     if (optproblem.nonOptimalMeansSatisfiable()) {
119                         setExitCode(ExitCode.SATISFIABLE);
120                         if (optproblem.hasNoObjectiveFunction()) {
121                             return;
122                         }
123                         log("SATISFIABLE"); //$NON-NLS-1$
124                     } else if (this.incomplete) {
125                         setExitCode(ExitCode.UPPER_BOUND);
126                     }
127                     isSatisfiable = true;
128                     log("OPTIMIZING..."); //$NON-NLS-1$
129                 }
130                 log("Got one! Elapsed wall clock time (in seconds):" //$NON-NLS-1$
131                         + (System.currentTimeMillis() - getBeginTime())
132                         / 1000.0);
133                 getLogWriter().println(
134                         CURRENT_OPTIMUM_VALUE_PREFIX
135                                 + optproblem.getObjectiveValue());
136                 optproblem.discardCurrentSolution();
137             }
138             if (isSatisfiable) {
139                 setExitCode(ExitCode.OPTIMUM_FOUND);
140             } else {
141                 setExitCode(ExitCode.UNSATISFIABLE);
142             }
143         } catch (ContradictionException ex) {
144             assert isSatisfiable;
145             setExitCode(ExitCode.OPTIMUM_FOUND);
146         }
147     }
148 
149 }