# Logical Design

## Objective and Prerequisites

In this example, you’ll learn how to solve a logical design problem, which involves constructing a circuit using the minimum number of NOR gates (devices with two inputs and  one output) that will perform the logical function specified by a truth table. We’ll show you how to formulate this problem as a binary optimization problem using the Gurobi Python API and then use Gurobi Optimizer to automatically find the optimal solution.

This model is example 12 from the fifth edition of Model Building in Mathematical Programming by H. Paul Williams on pages 266-267 and 320-321.

This example is at the intermediate level, where we assume that you know Python and the Gurobi Python API and that you have some knowledge of building mathematical optimization models.

**Download the Repository** <br /> 
You can download the repository containing this and other examples by clicking [here](https://github.com/Gurobi/modeling-examples/archive/master.zip). 

## Problem Description

Logical circuits have a given number of inputs and one output. Impulses may be applied to the inputs of a given logical circuit, and it will respond by giving either an output (signal 1) or no output (signal 0). The input impulses are of the
same kind as the outputs - 1 (positive input) or 0 (no input).

In this example, a logical circuit is to be built up of NOR gates. A NOR gate is a device with two inputs and one output. It has the property that there is positive output (signal 1) if and only if neither input is positive, that is, both inputs have the value 0. By connecting such gates together with outputs from one gate possibly being inputs into another gate, it is possible to construct a circuit to perform any desired logical function. For example, the circuit illustrated in the following figure will respond to the inputs A and B in the way indicated by the truth table.


The objective is to construct a circuit using the minimum number of NOR gates that will perform the logical function specified by the following  truth table.

| A | B | Output |
| --- | --- | --- | 
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

‘Fan-in’ and ‘fan-out’ are not permitted. That is, more than one output from a NOR gate cannot lead into one input nor can one output lead into more than one input. It may be assumed throughout that the optimal design is a ‘subnet’ of the ‘maximal’ net shown in the following figure.


## Model Formulation

### Sets and Indices

$i \in \text{Gates}=\{1,...,7\}$

$i \in \text{G47}=\{4,...,7\}$

$r \in \text{Rows}=\{1,...,4\}$

### Parameters

$\text{valueA}_{i,r} \in \{0,1 \}$: Value of the external input A in row  $r$ of the truth table for gate $i$.

$\text{valueB}_{i,r} \in \{0,1 \}$: Value of the external input B in row  $r$ of the truth table for gate $i$.

### Decision Variables

$\text{NOR}_{i} \in \{0,1 \}$: This binary variable is equal to 1, if NOR gate $i$  is selected, 0 otherwise.

$\text{inputA}_{i} \in \{0,1 \}$: This binary variable is equal to 1, if external input A is an input to NOR gate $i$ , and 0 otherwise.

$\text{inputB}_{i} \in \{0,1 \}$: This binary variable is equal to 1, if external input B is an input to NOR gate $i$ , and 0 otherwise.

$\text{output}_{i,r} \in \{0,1 \}$: This binary variable is the output from gate $i$ for the combination of external input signals specified  in row $r$  of the truth table.

### Constraints

**External input**: A NOR gate can only have an external input if it exists.

\begin{equation}
\text{NOR}_{i} \geq \text{inputA}_{i}  \quad \forall i \in \text{Gates}
\end{equation}

\begin{equation}
\text{NOR}_{i} \geq \text{inputB}_{i}  \quad \forall i \in \text{Gates}
\end{equation}

**NOR gates**:If a NOR gate has one (or two) external inputs leading into it, only one (or no) NOR gates can feed into it. 

\begin{equation}
\text{NOR}_{2} + \text{NOR}_{3} + \text{inputA}_{1} + \text{inputB}_{2} \leq 2
\end{equation}

\begin{equation}
\text{NOR}_{4} + \text{NOR}_{5} + \text{inputA}_{2} + \text{inputB}_{2} \leq 2
\end{equation}

\begin{equation}
\text{NOR}_{6} + \text{NOR}_{7} + \text{inputA}_{3} + \text{inputB}_{3} \leq 2
\end{equation}

These constraints are based on the circuit shown in the figure of the ‘maximal’ net. 

**Output signals**: The output signal from NOR gate $i$ must be the correct logical function (NOR) of the input signals into gate $i$, if gate $i$ exists. 

\begin{equation}
\text{output}_{2,r} + \text{output}_{1,r} \leq 1 \quad \forall r \in \text{Rows}
\end{equation}

\begin{equation}
\text{output}_{3,r} + \text{output}_{1,r} \leq 1 \quad \forall r \in \text{Rows}
\end{equation}

\begin{equation}
\text{valueA}_{i,r}*\text{inputA}_{i} + \text{output}_{i,r} \leq 1 \quad \forall i \in \text{Gates}, r \in \text{Rows}
\end{equation}

\begin{equation}
\text{valueB}_{i,r}*\text{inputB}_{i} + \text{output}_{i,r} \leq 1 \quad \forall i \in \text{Gates}, r \in \text{Rows}
\end{equation}

\begin{equation}
\text{valueA}_{i,r}*\text{inputA}_{i} + \text{valueB}_{i,r}*\text{inputB}_{i} + 
\text{output}_{i,r} - \text{NOR}_{i}  \geq 0 \quad \forall i \in \text{G47}, r \in \text{Rows}
\end{equation}

\begin{equation}
\text{valueA}_{1,r}*\text{inputA}_{1} + \text{valueB}_{1,r}*\text{inputB}_{1} + 
\text{output}_{2,r} + \text{output}_{3,r} + \text{output}_{1,r} - \text{NOR}_{1}  \geq 0 
\quad \forall r \in \text{Rows}
\end{equation}

\begin{equation}
\text{valueA}_{2,r}*\text{inputA}_{2} + \text{valueB}_{2,r}*\text{inputB}_{2} + 
\text{output}_{4,r} + \text{output}_{5,r} + \text{output}_{2,r} - \text{NOR}_{2}  \geq 0 
\quad \forall r \in \text{Rows}
\end{equation}

\begin{equation}
\text{valueA}_{3,r}*\text{inputA}_{3} + \text{valueB}_{3,r}*\text{inputB}_{3} + 
\text{output}_{6,r} + \text{output}_{7,r} + \text{output}_{3,r} - \text{NOR}_{3}  \geq 0 
\quad \forall r \in \text{Rows}
\end{equation}

**Gate 1**: For NOR gate 1, the output variables are fixed at the values specified in the truth table. 

\begin{equation}
\text{output}_{1,1} = 0, \text{output}_{1,2} = 1, \text{output}_{1,3} = 1,  \text{output}_{1,4} = 0   
\end{equation}

To avoid a trivial solution containing no NOR gates, it is necessary to impose a constraint that selects NOR gate 1.

\begin{equation}
\text{NOR}_{1} \geq 1  
\end{equation}

**Gates and output**: If there is an output signal of 1 from a particular NOR gate for any combination of the input signals, then that gate must exist.

\begin{equation}
\text{NOR}_{i} - \text{output}_{i,r} \geq 0 \quad \forall i \in \text{Gates}, r \in \text{Rows}
\end{equation}

### Objective Function

**Number of gates**: The objective is to minimize the number of NOR gates selected.

\begin{equation}
\text{Minimize} \quad  \sum_{i \in \text{Gates}} \text{NOR}_{i}
\end{equation}

## Python Implementation

We import the Gurobi Python Module.


```python
%pip install gurobipy
```


```python
import gurobipy as gp
from gurobipy import GRB

# tested with Python 3.7.0 & Gurobi 9.0
```

## Input data

We define all the input data for the model.


```python
# List of NOR gates 1 to 7.

gates = ['1','2','3','4','5','6','7']

# List of NOR gates 4 to 7.

gates47 = ['4','5','6','7']

# List of rows of the truth-table in the range 1 to 4.

rows = ['1','2','3','4']

# Create a dictionary to capture the value of the external input A and B in the r row of the truth table, for each 
# NOR gate i.

gatesRows, valueA, valueB = gp.multidict({
    ('1','1'): [0,0],
    ('1','2'): [0,1],
    ('1','3'): [1,0],
    ('1','4'): [1,1],
    ('2','1'): [0,0],
    ('2','2'): [0,1],
    ('2','3'): [1,0],
    ('2','4'): [1,1],
    ('3','1'): [0,0],
    ('3','2'): [0,1],
    ('3','3'): [1,0],
    ('3','4'): [1,1],
    ('4','1'): [0,0],
    ('4','2'): [0,1],
    ('4','3'): [1,0],
    ('4','4'): [1,1],
    ('5','1'): [0,0],
    ('5','2'): [0,1],
    ('5','3'): [1,0],
    ('5','4'): [1,1],
    ('6','1'): [0,0],
    ('6','2'): [0,1],
    ('6','3'): [1,0],
    ('6','4'): [1,1],
    ('7','1'): [0,0],
    ('7','2'): [0,1],
    ('7','3'): [1,0],
    ('7','4'): [1,1]
})

```

## Model Deployment

We create a model and the variables. The main decision is to determine the $\text{NOR}_{i}$ variables that selects the NOR gates to consider in the logical circuit. The rest of the variables ensure that the circuit generates the output of the truth table.


```python
model = gp.Model('logicalDesign')

# Decision variables to select NOR gate i.
NOR = model.addVars(gates, vtype=GRB.BINARY, name="NORgate" )

# In order to avoid a trivial solution containing no NOR gates, it is necessary to impose a constraint 
# that selects NOR gate 1.

NOR['1'].lb = 1

# Variables to decide if external input A is an input to NOR gate i.
inputA = model.addVars(gates, vtype=GRB.BINARY, name="inputA")

# Variables to decide if external input B is an input to NOR gate i.
inputB = model.addVars(gates, vtype=GRB.BINARY, name="inputB")

# Output decision variables.
output = model.addVars(gatesRows, vtype=GRB.BINARY, name="output")

# For NOR gate 1, the output variables are fixed at the values specified in the truth table.

output['1','1'].ub = 0
output['1','2'].lb = 1
output['1','3'].lb = 1
output['1','4'].ub = 0
```

    Using license file c:\gurobi\gurobi.lic


A NOR gate can only have an external input if it exists.


```python
# External inputs constraints

externalInputsA = model.addConstrs( ( NOR[i] >= inputA[i]  for i in gates), name='externalInputsA')

externalInputsB = model.addConstrs( ( NOR[i] >= inputB[i]  for i in gates), name='externalInputsB')
```

If a NOR gate has one (or two) external inputs leading into it, only one (or no) NOR gates can feed into it. 


```python
# NOR gates constraints

NORgate1 = model.addConstr(NOR['2'] + NOR['3'] + inputA['1'] + inputB['1'] <= 2, name='NORgate1')

NORgate2 = model.addConstr(NOR['4'] + NOR['5'] + inputA['2'] + inputB['2'] <= 2, name='NORgate2')

NORgate3 = model.addConstr(NOR['6'] + NOR['7'] + inputA['3'] + inputB['3'] <= 2, name='NORgate3')
```

The output signal from NOR gate i must be the correct logical function (NOR) of the input signals into gate i, if gate i exists.


```python
# Output signal constraint.

outputSignals1_1 = model.addConstrs( (output['2',r] + output['1',r] <= 1 for r in rows), name='outputSignals1_1' )

outputSignals1_2 = model.addConstrs( (output['3',r] + output['1',r] <= 1 for r in rows), name='outputSignals1_2' )

outputSignals2_1 = model.addConstrs( (output['4',r] + output['2',r] <= 1 for r in rows), name='outputSignals2_1' )

outputSignals2_2 = model.addConstrs( (output['5',r] + output['2',r] <= 1 for r in rows), name='outputSignals2_2' )

outputSignals3_1 = model.addConstrs( (output['6',r] + output['3',r] <= 1 for r in rows), name='outputSignals3_1' )

outputSignals3_2 = model.addConstrs( (output['7',r] + output['3',r] <= 1 for r in rows), name='outputSignals3_2' )


outputSignals4 = model.addConstrs( (valueA[i,r]*inputA[i] + output[i,r] <= 1 for i,r in gatesRows), name='outputSignals4')

outputSignals5 = model.addConstrs( (valueB[i,r]*inputB[i] + output[i,r] <= 1 for i,r in gatesRows), name='outputSignals5')

outputSignals6 = model.addConstrs( (valueA[i,r]*inputA[i] + valueB[i,r]*inputB[i] + output[i,r] - NOR[i] >= 0 
                                    for i,r in gatesRows if i in gates47), name='outputSignals6')

outputSignals7 = model.addConstrs( (valueA['1',r]*inputA['1'] + valueB['1',r]*inputB['1'] 
                                    + output['2',r] + output['3',r] + output['1',r] - NOR['1'] >= 0
                                    for i,r in gatesRows), name='outputSignals7')

outputSignals8 = model.addConstrs( (valueA['2',r]*inputA['2'] + valueB['2',r]*inputB['2'] 
                                    + output['4',r] + output['5',r] + output['2',r] - NOR['2'] >= 0
                                    for i,r in gatesRows), name='outputSignals8')

outputSignals9 = model.addConstrs( (valueA['3',r]*inputA['3'] + valueB['3',r]*inputB['3'] 
                                    + output['6',r] + output['7',r] + output['3',r] - NOR['3'] >= 0
                                    for i,r in gatesRows), name='outputSignals9')
```

If there is an output signal of 1 from a particular NOR gate for any combination of the input signals, then that gate must exist.


```python
# Gate and output signals constraints

gateOutput = model.addConstrs( (NOR[i] - output[i,r] >= 0 for i,r in gatesRows) , name='gateOutput')
```

The objective is to minimize the number of NOR gates selected.


```python
# Objective function.

model.setObjective(NOR.sum(), GRB.MINIMIZE)
```


```python
# Verify model formulation

model.write('logicalDesign.lp')

# Run optimization engine

model.optimize()
```

    Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
    Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
    Optimize a model with 225 rows, 49 columns and 696 nonzeros
    Model fingerprint: 0x9adba516
    Variable types: 0 continuous, 49 integer (49 binary)
    Coefficient statistics:
      Matrix range     [1e+00, 1e+00]
      Objective range  [1e+00, 1e+00]
      Bounds range     [1e+00, 1e+00]
      RHS range        [1e+00, 2e+00]
    Presolve removed 225 rows and 49 columns
    Presolve time: 0.00s
    Presolve: All rows and columns removed
    
    Explored 0 nodes (0 simplex iterations) in 0.01 seconds
    Thread count was 1 (of 8 available processors)
    
    Solution count 1: 5 
    
    Optimal solution found (tolerance 1.00e-04)
    Best objective 5.000000000000e+00, best bound 5.000000000000e+00, gap 0.0000%



```python
# Output reports

print("\n\n_________________________________________________________________________________")
print(f"The optimal circuit design:")
print("_________________________________________________________________________________")
for i in gates:
    if (NOR[i].x > 0.5):
        if (inputA[i].x + inputB[i].x > 0.5):
            print(f"NOR gate {i} is active, with external inputs A and B values of {inputA[i].x} and  {inputB[i].x}.")
        else:
            print(f"NOR gate {i} is active.")


```

    
    
    _________________________________________________________________________________
    The optimal circuit design:
    _________________________________________________________________________________
    NOR gate 1 is active.
    NOR gate 2 is active, with external inputs A and B values of 1.0 and  1.0.
    NOR gate 3 is active.
    NOR gate 6 is active, with external inputs A and B values of 0.0 and  1.0.
    NOR gate 7 is active, with external inputs A and B values of 1.0 and  0.0.


## References

H. Paul Williams, Model Building in Mathematical Programming, fifth edition.

Copyright © 2020 Gurobi Optimization, LLC


```python

```

49842a861b1d849e01c8ea347886162f752d1829
ipynb
Jupyter Notebook
logical_design/logical_design_gcl.ipynb
anupamsharmaberkeley/Gurobi_Optimization
701200b5bfd9bf46036675f5b157b3d8e3728ff9
Apache-2.0
2019-07-11T15:08:37.000Z
2022-03-25T10:12:54.000Z
logical_design/logical_design_gcl.ipynb
anupamsharmaberkeley/Gurobi_Optimization
701200b5bfd9bf46036675f5b157b3d8e3728ff9
Apache-2.0
2020-10-29T12:34:13.000Z
2022-02-28T14:16:43.000Z
logical_design/logical_design_gcl.ipynb
anupamsharmaberkeley/Gurobi_Optimization
701200b5bfd9bf46036675f5b157b3d8e3728ff9
Apache-2.0
2019-11-11T17:04:54.000Z
2022-03-30T21:34:20.000Z
Qwen/Qwen-72B
1. YES
2. YES

