QBSolv求解二进制整数规划（BIP）未得到可行解求助

Let's break down the possible reasons why your QBSolv result is violating the original constraints, and walk through actionable steps to diagnose and fix this:

1. Insufficient Constraint Penalty Weights #

QBSolv minimizes the QUBO function, so for your maximization problem, you’ve likely converted the objective to its negative (to turn maximization into minimization). The critical issue here is that constraint penalty terms must be large enough to outweigh any potential gain from violating constraints.

Looking at your QUBO matrix, diagonal values for decision variables (like -2098.0, -4001.0) represent scaled objective terms, while slack variable diagonals (e.g., -214.0, -431.0) should map to positive penalty values (or their negatives if you’ve adjusted for minimization). If the penalty for breaking a constraint is smaller than the objective gain from ignoring it, the solver will prioritize the objective over feasibility.

Check: Calculate the maximum possible objective value your decision variables can produce, then ensure your constraint penalties are 10–100x larger than this value. This guarantees violating a constraint is far more "costly" than any objective benefit.

2. Incorrect Maximization-to-Minimization Conversion #

Since sample_qubo minimizes the QUBO function, your total QUBO should follow this formula:
QUBO = -Objective + Penalty_Terms
Where:

• -Objective converts your maximization goal into a minimization target
• Penalty_Terms are positive values that increase when constraints are violated (so the solver avoids them)

If you messed up the sign of either the objective or penalty terms, the solver might actively seek out constraint violations. For example, if penalty terms are negative, breaking a constraint would reduce the QUBO energy—something the solver will prioritize.

Check: Manually compute the QUBO energy for a known feasible solution and your current infeasible solution. If the infeasible solution has a lower energy, your penalty terms are either incorrectly signed or too small.

3. Errors in Slack Variable Modeling #

You added 8 slack variables per constraint, which suggests binary encoding (each slack variable represents a bit, covering values 0–255). If the QUBO terms for these slack variables don’t correctly enforce the constraint equation, the solver can’t use them to satisfy constraints.

For example, an inequality constraint like $\sum x_i \leq C$ would be modeled as $\sum x_i + \sum_{k=0}^7 2^k s_k = C$ (for 8 slack variables $s_k$). Expanding this into QUBO form requires specific cross-terms between decision variables and slack variables, as well as slack variable self-terms.

Check: Take one of your constraints, expand its QUBO form manually, then compare the coefficients to the corresponding rows/columns in your QUBO matrix. Look for mismatched signs or values in cross-terms between decision variables and slack variables.

4. Suboptimal QBSolv Solver Parameters #

The default parameters for QBSolv might not give the solver enough time or iterations to find a feasible solution. With 20 variables, increasing the number of repeats or timeout can help the solver explore more possible solutions.

Try adjusting your code:

# Increase repeats and timeout to allow more solution exploration
response = QBSolv().sample_qubo(Qubo, num_repeats=100, timeout=15)
# Print all samples with energy values to check for feasible solutions
for entry in response.data(['sample', 'energy', 'num_occurrences']):
    print(f"Sample: {entry.sample}, Energy: {entry.energy}, Occurrences: {entry.num_occurrences}")

If you see feasible solutions in the output but with higher energy, this confirms your penalty weights are too low—increase them so feasible solutions have lower energy than infeasible ones.

5. Verify QUBO Matrix Symmetry #

While you mentioned your matrix is upper triangular, QBSolv expects a symmetric QUBO matrix (since $x_i x_j$ is identical to $x_j x_i$). If you’re passing an upper triangular matrix, ensure the solver handles it correctly, or convert it to a full symmetric matrix by copying upper triangular values to the lower triangle.

内容的提问来源于stack exchange，提问作者Danu