<p>Can this be reformulated as follows (careful, I am sleep-deprived with a cranky toddler in the room):</p>

<p>We are looking at a random graph <span class="math-container">$G$</span> with 6000 weighted nodes, a subgraph <span class="math-container">$G'$</span> induced by about 4000 edges, and 140.000 other weighted edges of positive weight but strictly smaller than the nodes they connect to.</p>

<p>A satisfying assignment for <span class="math-container">$C$</span> induces a bipartite subgraph of <span class="math-container">$G'$</span> (all nodes with assignment 1 plus their immediate neighbors with assignment 0). So you are looking to optimize over the set of bipartite subgraphs of <span class="math-container">$G'$</span>?</p>

<p>A few random thoughts:</p>

<ul>
<li>How structured are <span class="math-container">$G$</span> and <span class="math-container">$G'$</span>? I presume a random graph model is not a very good model? What is the distribution of degrees of nodes?</li>
<li>Are all nodes in <span class="math-container">$G'$</span>?</li>
</ul>

<p>Is there a way we can bound the sum of all <span class="math-container">$w_2$</span>-induced weights for given node? We know that the node weight <span class="math-container">$w_1(v)$</span> is bigger than the edge weight <span class="math-container">$w_2(v, \centerdot)$</span>, is there something to be said for <span class="math-container">$\sum_{v_2 \in V} w_2(v, v_2)$</span>? That could give some information about whether "switching a node on" is worth it...</p>

<p>If nodes have a tendency to outweigh the sum of their edges, would that hint at a bigger bipartite subgraph being always better than a smaller one, and at the problem becoming one of maximizing the size of the bipartite subgraph?</p>

CC BY-SA 4.0
2019-08-14T14:18:18.383Z
2019-08-14T14:18:18.383Z
rotaist
<p>It's certainly possible to simplify the presentation:</p>

<ul>
<li>A graph <span class="math-container">$G = (V, E)$</span></li>
<li>A weight function <span class="math-container">$w_1 : V \mapsto \mathbb{N}$</span></li>
<li>A weight function <span class="math-container">$w_2 : E \mapsto (\mathbb{N} \cup \{-\infty\})$</span>. This corresponds to your formulation of <span class="math-container">$w_2$</span> as a total function on <span class="math-container">$V \times V$</span>, where <span class="math-container">$w_2(x,y) = 0$</span> if <span class="math-container">$(x,y) \notin P$</span>, except that <span class="math-container">$w_2(x,y) = - \infty$</span> if <span class="math-container">$(x, y) \in C$</span></li>
</ul>

<p>Now, every vertex which doesn't have an edge weighted to negative infinity is automatically included in the subset which maximises the total induced weight, so the graph can be preprocessed to only contain vertices with at least one conflict.</p>

<p>The maximum independent set problem is trivially reduced to this one (set <span class="math-container">$P$</span> empty and <span class="math-container">$w_1$</span> constant), but there's a chance that your instances, by virtue of their sparsity, will decompose nicely.</p>

CC BY-SA 4.0
2019-08-21T06:35:13.413Z
This is a very deep answer, thank you. I'm going to have to contemplate it for a while.
Syzygy
CC BY-SA 4.0
2019-08-19T23:25:20.763Z
2019-08-19T23:25:20.763Z
Peter Taylor
<p>My scenario has various flavors of SAT, constrained quadratic pseudo-Boolean, and integer programming. My attempts to formalize and solve the problem with Z3's <code>QF_LIA</code> optimizer have fallen flat, which leads me to wonder if perhaps there is an alternative formulation of the problem, and a solver that might have better performance characteristics. Any advice is appreciated.</p>

<p><strong>I have</strong>:</p>

<ul>
<li>A set <span class="math-container">$V$</span> of Boolean variables: <span class="math-container">$V = \{v_i\}$</span>. For a "large" instance, <span class="math-container">$|V| \approx 6,000$</span>.</li>
<li>A set <span class="math-container">$P \subseteq V \times V$</span>. For the same "large" instance, <span class="math-container">$|P| \approx 140,000$</span>.</li>
<li>A set of constraints <span class="math-container">$C \subseteq V \times V$</span>: if <span class="math-container">$(x,y) \in C$</span>, then <span class="math-container">$x \wedge y \neq 1$</span>. For the same "large" instance, <span class="math-container">$|C| \approx 4,000$</span>.</li>
<li>A weight function <span class="math-container">$w_1 : V \mapsto \mathbb{N}$</span> (i.e., a total function on <span class="math-container">$V$</span>).</li>
<li>A weight function <span class="math-container">$w_2 : P \mapsto \mathbb{N}$</span>, which is mostly unrelated to <span class="math-container">$w_1$</span>, except that <span class="math-container">$\forall v_i,v_j. w_2(v_i,v_j) \leq min(w_1(v_i),w_1(v_j))$</span>. <span class="math-container">$w_2$</span> can be thought of as either:

<ul>
<li>A total function on <span class="math-container">$P$</span></li>
<li>A partial function on <span class="math-container">$V \times V$</span></li>
<li>A total function on <span class="math-container">$V \times V$</span>, where <span class="math-container">$w_2(x,y) = 0$</span> if <span class="math-container">$(x,y) \notin P$</span>.</li>
</ul></li>
</ul>

<p><strong>I want</strong>: an assignment <span class="math-container">$Asg : V \mapsto \mathbb{B}$</span> such that:</p>

<ul>
<li>Satisfies all constraints: <span class="math-container">$\forall (v_i,v_j) \in C$</span>, <span class="math-container">$Asg(v_i) \wedge Asg(v_j) \neq 1$</span>.</li>
<li>Maximizes <span class="math-container">$\sum_{v_i \in V} Asg(v_i)*w_1(v_i) + \sum_{(v_i,v_j) \in P} Asg(v_i)*Asg(v_j)*w_2(v_i,v_j)$</span>

<ul>
<li>I.e., maximizes <span class="math-container">$w_1$</span> on <span class="math-container">$V$</span> and <span class="math-container">$w_2$</span> on <span class="math-container">$P$</span> simultaneously.</li>
</ul></li>
</ul>

<ds.algorithms><optimization>
Formalizing and optimizing constraints involving booleans, pairs of booleans, and integer sums
Syzygy
# Formalizing and optimizing constraints involving booleans, pairs of booleans, and integer sums

(Asked by: username_0 on 2019-08-14)

My scenario has various flavors of SAT, constrained quadratic pseudo-Boolean, and integer programming. My attempts to formalize and solve the problem with Z3's `QF_LIA` optimizer have fallen flat, which leads me to wonder if perhaps there is an alternative formulation of the problem, and a solver that might have better performance characteristics. Any advice is appreciated.

**I have**:

* A set $V$ of Boolean variables: $V = \{v\_i\}$. For a "large" instance, $|V| \approx 6,000$.
* A set $P \subseteq V \times V$. For the same "large" instance, $|P| \approx 140,000$.
* A set of constraints $C \subseteq V \times V$: if $(x,y) \in C$, then $x \wedge y \neq 1$. For the same "large" instance, $|C| \approx 4,000$.
* A weight function $w\_1 : V \mapsto \mathbb{N}$ (i.e., a total function on $V$).
* A weight function $w\_2 : P \mapsto \mathbb{N}$, which is mostly unrelated to $w\_1$, except that $\forall v\_i,v\_j. w\_2(v\_i,v\_j) \leq min(w\_1(v\_i),w\_1(v\_j))$. $w\_2$ can be thought of as either:
  + A total function on $P$
  + A partial function on $V \times V$
  + A total function on $V \times V$, where $w\_2(x,y) = 0$ if $(x,y) \notin P$.

**I want**: an assignment $Asg : V \mapsto \mathbb{B}$ such that:

* Satisfies all constraints: $\forall (v\_i,v\_j) \in C$, $Asg(v\_i) \wedge Asg(v\_j) \neq 1$.
* Maximizes $\sum\_{v\_i \in V} Asg(v\_i)\*w\_1(v\_i) + \sum\_{(v\_i,v\_j) \in P} Asg(v\_i)\*Asg(v\_j)\*w\_2(v\_i,v\_j)$
  + I.e., maximizes $w\_1$ on $V$ and $w\_2$ on $P$ simultaneously.

**Tags:** ds.algorithms, optimization


---

## 2 answers

### Answer by username_1 on 2019-08-14. Score: 1

Can this be reformulated as follows (careful, I am sleep-deprived with a cranky toddler in the room):

We are looking at a random graph $G$ with 6000 weighted nodes, a subgraph $G'$ induced by about 4000 edges, and 140.000 other weighted edges of positive weight but strictly smaller than the nodes they connect to.

A satisfying assignment for $C$ induces a bipartite subgraph of $G'$ (all nodes with assignment 1 plus their immediate neighbors with assignment 0). So you are looking to optimize over the set of bipartite subgraphs of $G'$?

A few random thoughts:

* How structured are $G$ and $G'$? I presume a random graph model is not a very good model? What is the distribution of degrees of nodes?
* Are all nodes in $G'$?

Is there a way we can bound the sum of all $w\_2$-induced weights for given node? We know that the node weight $w\_1(v)$ is bigger than the edge weight $w\_2(v, \centerdot)$, is there something to be said for $\sum\_{v\_2 \in V} w\_2(v, v\_2)$? That could give some information about whether "switching a node on" is worth it...

If nodes have a tendency to outweigh the sum of their edges, would that hint at a bigger bipartite subgraph being always better than a smaller one, and at the problem becoming one of maximizing the size of the bipartite subgraph?


---

### Answer by username_2 on 2019-08-19. Score: 1

It's certainly possible to simplify the presentation:

* A graph $G = (V, E)$
* A weight function $w\_1 : V \mapsto \mathbb{N}$
* A weight function $w\_2 : E \mapsto (\mathbb{N} \cup \{-\infty\})$. This corresponds to your formulation of $w\_2$ as a total function on $V \times V$, where $w\_2(x,y) = 0$ if $(x,y) \notin P$, except that $w\_2(x,y) = - \infty$ if $(x, y) \in C$

Now, every vertex which doesn't have an edge weighted to negative infinity is automatically included in the subset which maximises the total induced weight, so the graph can be preprocessed to only contain vertices with at least one conflict.

The maximum independent set problem is trivially reduced to this one (set $P$ empty and $w\_1$ constant), but there's a chance that your instances, by virtue of their sparsity, will decompose nicely.

> **Comments:**
> **username_0**: This is a very deep answer, thank you. I'm going to have to contemplate it for a while.  

---

