View Javadoc

1   /*******************************************************************************
2    * SAT4J: a SATisfiability library for Java Copyright (C) 2004-2008 Daniel Le Berre
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   *******************************************************************************/
28  package org.sat4j.opt;
29  
30  import org.sat4j.core.VecInt;
31  import org.sat4j.specs.IOptimizationProblem;
32  import org.sat4j.specs.ISolver;
33  import org.sat4j.specs.IVecInt;
34  import org.sat4j.specs.TimeoutException;
35  import org.sat4j.tools.SolverDecorator;
36  
37  /**
38   * Abstract class which adds a new "selector" variable for each clause entered
39   * in the solver.
40   * 
41   * As a consequence, an original problem with n variables and m clauses will end
42   * up with n+m variables.
43   * 
44   * @author daniel
45   * 
46   */
47  public abstract class AbstractSelectorVariablesDecorator extends
48  		SolverDecorator<ISolver> implements IOptimizationProblem {
49  
50  	/**
51  	 * 
52  	 */
53  	private static final long serialVersionUID = 1L;
54  
55  	protected int nborigvars;
56  
57  	private int nbexpectedclauses;
58  
59  	protected int nbnewvar;
60  
61  	protected int[] prevfullmodel;
62  
63  	/**
64  	 * @since 2.1
65  	 */
66  	protected int[] prevmodel;
67  	/**
68  	 * @since 2.1
69  	 */
70  	protected boolean[] prevboolmodel;
71  
72  	public AbstractSelectorVariablesDecorator(ISolver solver) {
73  		super(solver);
74  	}
75  
76  	@Override
77  	public int newVar(int howmany) {
78  		nborigvars = super.newVar(howmany);
79  		return nborigvars;
80  	}
81  
82  	@Override
83  	public void setExpectedNumberOfClauses(int nb) {
84  		nbexpectedclauses = nb;
85  		super.setExpectedNumberOfClauses(nb);
86  		super.newVar(nborigvars + nbexpectedclauses);
87  	}
88  
89  	public int getExpectedNumberOfClauses() {
90  		return nbexpectedclauses;
91  	}
92  
93  	@Override
94  	public void reset() {
95  		super.reset();
96  		nbnewvar = 0;
97  	}
98  
99  	public boolean admitABetterSolution() throws TimeoutException {
100 		return admitABetterSolution(VecInt.EMPTY);
101 	}
102 
103 	/**
104 	 * @since 2.1
105 	 */
106 	public boolean admitABetterSolution(IVecInt assumps)
107 			throws TimeoutException {
108 		boolean result = super.isSatisfiable(assumps, true);
109 		if (result) {
110 			prevboolmodel = new boolean[nVars()];
111 			for (int i = 0; i < nVars(); i++) {
112 				prevboolmodel[i] = decorated().model(i + 1);
113 			}
114 			prevfullmodel = super.model();
115 			int end = nborigvars - 1;
116 			while (Math.abs(prevfullmodel[end]) > nborigvars)
117 				end--;
118 			prevmodel = new int[end + 1];
119 			for (int i = 0; i <= end; i++) {
120 				prevmodel[i] = prevfullmodel[i];
121 			}
122 			calculateObjectiveValue();
123 		}
124 		return result;
125 	}
126 
127 	abstract void calculateObjectiveValue();
128 
129 	@Override
130 	public int[] model() {
131 		return prevmodel;
132 	}
133 
134 	@Override
135 	public boolean model(int var) {
136 		return prevboolmodel[var - 1];
137 	}
138 }