<jupyter_start><jupyter_text>Logical Design Objective and PrerequisitesThis problem is an example of 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. This problem is formulated as a binary optimization problem using the Gurobi Python API and solved with the Gurobi Optimizer.This model is example 12 from the fifth edition of Model Building in Mathematical Programming, by <NAME> 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**  You can download the repository containing this and other examples by clicking [here](https://github.com/Gurobi/modeling-examples/archive/master.zip). **Gurobi License**  In order to run this Jupyter Notebook properly, you must have a Gurobi license. If you do not have one, you can request an [evaluation license](https://www.gurobi.com/downloads/request-an-evaluation-license/?utm_source=3PW&utm_medium=OT&utm_campaign=WW-MU-EDU-OR-O_LEA-PR_NO-Q3_FY20_WW_JPME_LOGICAL_DESIGN_COM_EVAL_GitHub&utm_term=Logical_Design&utm_content=C_JPM) as a *commercial user*, or download a [free license](https://www.gurobi.com/academia/academic-program-and-licenses/?utm_source=3PW&utm_medium=OT&utm_campaign=WW-MU-EDU-OR-O_LEA-PR_NO-Q3_FY20_WW_JPME_LOGICAL_DESIGN_ACADEMIC_EVAL_GitHub&utm_term=Logical_Design&utm_content=C_JPM) as an *academic user*.  Problem DescriptionLogical 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 thesame 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.![circuit](circuit.PNG)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.![subnet](subnet.PNG)  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 ImplementationWe import the Gurobi Python Module.<jupyter_code>import gurobipy as gp
from gurobipy import GRB

# tested with Python 3.7.0 & Gurobi 9.0<jupyter_output><empty_output><jupyter_text>Input dataWe define all the input data for the model.<jupyter_code># 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]
})<jupyter_output><empty_output><jupyter_text>Model DeploymentWe 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.<jupyter_code>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<jupyter_output>Using license file c:\gurobi\gurobi.lic
Set parameter TokenServer to value SANTOS-SURFACE-<jupyter_text>A NOR gate can only have an external input if it exists.<jupyter_code># 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')<jupyter_output><empty_output><jupyter_text>If a NOR gate has one (or two) external inputs leading into it, only one (or no) NOR gates can feed into it.<jupyter_code># 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')<jupyter_output><empty_output><jupyter_text>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.<jupyter_code># 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')<jupyter_output><empty_output><jupyter_text>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.<jupyter_code># Gate and output signals constraints

gateOutput = model.addConstrs( (NOR[i] - output[i,r] >= 0 for i,r in gatesRows) , name='gateOutput')<jupyter_output><empty_output><jupyter_text>The objective is to minimize the number of NOR gates selected.<jupyter_code># Objective function.

model.setObjective(NOR.sum(), GRB.MINIMIZE)
# Verify model formulation

model.write('logicalDesign.lp')

# Run optimization engine

model.optimize()
# 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.")<jupyter_output>_________________________________________________________________________________
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.
{'fraction_non_alphanumeric': 0.15759471671880432, 'fraction_numerical': 0.029475147723322905, 'mean_word_length': 4.434831885153003, 'pattern_counts': {'":': 0, '<': 43, '<?xml version=': 0, '>': 41, 'https://': 3, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '173693', 'license': 'Apache-2.0', 'n_tokens_mistral': 4996, 'n_tokens_neox': 4740, 'n_words': 1576, 'path': 'logical_design/logical_design.ipynb', 'repo_name': 'jacksonwalters/modeling-examples', 'size': '14395'}