DialecticSearch¶
The Dialectic Search Solver uses a path search between two states representing the thesis and antithesis. A greedy search is used to reduce the energy by applying bit flips in an attempt to find the solution.
For the Dialectic Search Solver, if the target keyword is set, the max_iter keyword is ignored. If the timeout keyword is provided, the max_time keyword is ignored. However, both can be used as equivalents. Both options are available for a more convenient interaction over multiple different solvers expecting different parameter names, esentially tuning the same thing.
Note
The Dialectic Search algorithm operates through two distinct phases:
- Antithesis: Generates a complementary solution designed to explore different regions of the solution space
- Synthesis: Creates new solutions by exploring paths between thesis and antithesis
Each phase uses tabu search with potentially different parameter settings to guide the exploration process. This approach is particularly effective for problems with complex landscapes containing many local optima.
The algorithm uses D-Wave's backend technology to efficiently solve optimization problems. For more details on D-Wave solvers, see: https://docs.dwavesys.com/
Compatible Backends¶
The DialecticSearch algorithm supports the following backends:
DWave
By default,DialecticSearchuses theDWavebackend.
Initialization¶
The following section outlines the default configurations of DialecticSearch. You can also specify
other compatible backends for the algorithm. When backend=None is specified, the default backend
will be initialized automatically. In this case, if the backend requires a token, it will be taken
from the environment variables.
from luna_quantum.algorithms import DialecticSearch
from luna_quantum.solve.parameters.algorithms.base_params import (
Decomposer,
TabuSearchBaseParams
)
algorithm = DialecticSearch(
backend=None,
antithesis_tabu_params=TabuSearchBaseParams(
num_reads=None,
tenure=None,
timeout=100
),
synthesis_tabu_params=TabuSearchBaseParams(
num_reads=None,
tenure=None,
timeout=100
),
decomposer=Decomposer(
size=10,
min_gain=None,
rolling=True,
rolling_history=1.0,
silent_rewind=True,
traversal='energy'
),
max_iter=100,
max_time=5,
convergence=3,
target=None,
rtol=1e-05,
atol=1e-08,
max_tries=100
)
Parameter Details
For a complete overview of available parameters and their usage, see the DialecticSearch API Reference.
Usage¶
from luna_quantum import LunaSolve
LunaSolve.authenticate("<YOUR_LUNA_API_KEY>")
# Define your model and algorithm
model = ...
algorithm = ...
solve_job = algorithm.run(model, name="my-solve-job")
API Reference¶
Bases: LunaAlgorithm[DWave]
Parameters for the Dialectic Search optimization algorithm.
Dialectic Search is an iterative metaheuristic that uses a thesis-antithesis-synthesis approach to explore the solution space. It starts with a thesis (initial solution) and generates an antithesis (complementary solution). Then it performs a path search between them to synthesize improved solutions, using tabu search for all three phases.
Attributes:
| Name | Type | Description |
|---|---|---|
antithesis_tabu_params |
TabuSearchParams
|
Parameters for the antithesis phase of the search process. The antithesis deliberately explores contrasting regions of the solution space to ensure diversity and avoid getting trapped in local optima. This phase often uses different tabu parameters to promote exploration over exploitation. Default is a TabuSearchParams instance with default settings. |
synthesis_tabu_params |
TabuSearchParams
|
Parameters for the synthesis phase of the search process. The synthesis combines aspects of both thesis and antithesis to generate new candidate solutions, exploring the path between these solutions to find potentially better optima. This phase is critical for discovering high-quality solutions that neither thesis nor antithesis alone would find. Default is a TabuSearchParams instance with default settings. |
max_iter |
int | None
|
Maximum number of iterations for the solver. This limits the total number of dialectic cycles (thesis-antithesis-synthesis) that will be performed. Higher values allow for more thorough exploration but increase runtime. Default is 100. |
max_time |
int
|
Maximum time in seconds for the solver to run. Provides a hard time limit regardless of convergence or iteration status. Useful for time-constrained scenarios where some solution is needed within a specific timeframe. Default is 5. |
convergence |
int
|
Number of consecutive iterations without improvement before declaring convergence. Higher values ensure more stable solutions but may increase computation time unnecessarily if the algorithm has already found the best solution. Default is 3. |
target |
float | None
|
Target objective value that triggers termination if reached. Allows early stopping when a sufficiently good solution is found. Default is None, which means the algorithm will run until other stopping criteria are met. |
rtol |
float
|
Relative tolerance for convergence detection. Used when comparing objective values between iterations to determine if significant improvement has occurred. Default is DEFAULT_RTOL. |
atol |
float
|
Absolute tolerance for convergence detection. Used alongside rtol when comparing objective values to determine if the algorithm has converged. Default is DEFAULT_ATOL. |
max_tries |
int | None
|
Maximum number of synthesis attempts for each input state before moving to a new thesis. Controls how persistently the algorithm explores the path between thesis and antithesis before generating new starting points. Higher values allow for more thorough path exploration but may slow progress if paths are unproductive. Default is 100. Must be ≥1. |
decomposer |
Decomposer
|
Decomposer: Breaks down problems into subproblems of manageable size Default is a Decomposer instance with default settings. |
antithesis_tabu_params
class-attribute
instance-attribute
¶
antithesis_tabu_params: TabuSearchBaseParams = Field(
default_factory=TabuSearchBaseParams
)
backend
class-attribute
instance-attribute
¶
decomposer
class-attribute
instance-attribute
¶
decomposer: Decomposer = Field(default_factory=Decomposer)
model_config
class-attribute
instance-attribute
¶
synthesis_tabu_params
class-attribute
instance-attribute
¶
synthesis_tabu_params: TabuSearchBaseParams = Field(
default_factory=TabuSearchBaseParams
)
get_compatible_backends
classmethod
¶
get_default_backend
classmethod
¶
get_default_backend() -> DWave
Return the default backend implementation.
This property must be implemented by subclasses to provide the default backend instance to use when no specific backend is specified.
Returns:
| Type | Description |
|---|---|
IBackend
|
An instance of a class implementing the IBackend interface that serves as the default backend. |
run ¶
run(
model: Model | str,
name: str | None = None,
backend: BACKEND_TYPE | None = None,
client: LunaSolve | str | None = None,
*args: Any,
**kwargs: Any,
) -> SolveJob
Run the configured solver.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
model
|
Model or str
|
The model to be optimized or solved. It could be an Model instance or a string identifier representing the model id. |
required |
name
|
str | None
|
If provided, the name of the job. Defaults to None. |
None
|
backend
|
BACKEND_TYPE | None
|
Backend to use for the solver. If not provided, the default backend is used. |
None
|
client
|
LunaSolve or str
|
The client interface used to interact with the backend services. If not provided, a default client will be used. |
None
|
*args
|
Any
|
Additional arguments that will be passed to the solver or client. |
()
|
**kwargs
|
Any
|
Additional keyword parameters for configuration or customization. |
{}
|
Returns:
| Type | Description |
|---|---|
SolveJob
|
The job object containing the information about the solve process. |
Bases: BaseModel
Configuration for breaking down larger problems into subproblems for DWave QPUs.
Attributes:
| Name | Type | Description |
|---|---|---|
size |
int, default=10
|
Nominal number of variables in each subproblem. The actual subproblem can be
smaller depending on other parameters (e.g., |
min_gain |
Optional[float], default=None
|
Minimum required energy reduction threshold for including a variable in the subproblem. A variable is included only if flipping its value reduces the BQM energy by at least this amount. If None, no minimum gain is required. |
rolling |
bool, default=True
|
Controls variable selection strategy for successive calls on the same problem:
|
rolling_history |
float, default=1.0
|
Fraction of the problem size (range 0.0 to 1.0) that participates in the rolling selection. Once this fraction of variables has been processed, subproblem unrolling is reset. Min: 0.0, Max: 1.0 |
silent_rewind |
bool, default=True
|
Controls behavior when resetting/rewinding the subproblem generator:
|
traversal |
Literal["energy", "bfs", "pfs"], default="energy"
|
Algorithm used to select a subproblem of
|
Bases: BaseModel
Parameters for the Tabu Problem optimization algorithm.
Tabu Search is a metaheuristic that enhances local search by maintaining a "tabu list" of recently visited solutions to avoid cycling. It systematically explores the solution space by allowing non-improving moves when no improving moves exist, while preventing revisiting recent solutions.
This class extends the basic TabuSearch with additional parameters for fine-tuning the search process, including restart strategies and early termination conditions.
Attributes:
| Name | Type | Description |
|---|---|---|
num_reads |
int | None
|
Number of independent runs of the tabu algorithm, each producing one solution. Multiple reads increase the chance of finding the global optimum by starting from different initial states. If None, matches the number of initial states provided (or performs just one read if no initial states are given). |
tenure |
int | None
|
Length of the tabu list - the number of recently visited solutions that are forbidden. Larger values help escape deeper local minima but may slow exploration. Default is 1/4 of the number of variables up to a maximum of 20. A good tenure balances diversification (exploring new regions) with intensification (focusing on promising areas). |
timeout |
float
|
Maximum running time in milliseconds per read before the algorithm stops, regardless of convergence. Default is 100, which is suitable for small to medium-sized problems. For larger problems, consider increasing this value to allow sufficient exploration time. |