Logical Design: Constructing an Electronic System with a Minimum Number of Components

The following SET and READ statements declare the ARCS index set and then populate it by reading the arc_data data set:

proc optmodel;
   set <num,num> ARCS;
   read data arc_data into ARCS=[i j];

Each arc corresponds to a connection from one NOR gate to another in Figure 12.2, and the following SET statement declares and populates the index set GATES by taking a union over ARCS, as in previous examples:

   set GATES = union {<i,j> in ARCS} {i,j};

   var UseGate {GATES} binary;
   min NumGatesUsed = sum {gate in GATES} UseGate[gate];

   var AssignAGate {GATES} binary;
   var AssignBGate {GATES} binary;

The following CON statements declare the constraints that if input A or B is assigned to a gate, that gate must be used:

   con AssignAGate_def {gate in GATES}:
      AssignAGate[gate] <= UseGate[gate];
   con AssignBGate_def {gate in GATES}:
      AssignBGate[gate] <= UseGate[gate];

The following CON statement declares the constraint that each gate has at most two inputs:

   con At_most_two_inputs {gate in GATES}:
      sum {<pred,(gate)> in ARCS} UseGate[pred]
    + AssignAGate[gate] + AssignBGate[gate]
   <= 2;

The following statements declare the ROWS index set and several parameters and read the truth_data data set that contains the target output:

   set ROWS;
   num inputA {ROWS};
   num inputB {ROWS};
   num target_output {ROWS};
   read data truth_data into ROWS=[_N_] inputA=A inputB=B target_output=output;

The following VAR and FIX statements declare the Output variable and fix the output of Gate 1 to the desired values specified in target_output:

   var Output {GATES, ROWS} binary;
   for {row in ROWS} fix Output[1,row] = target_output[row];

The following CON statement declares the constraint that if any row has a positive Output, that gate must be used.

   con Output_link {gate in GATES, row in ROWS}:
      Output[gate,row] <= UseGate[gate];

The following CON statements declare the constraints that define each NOR gate:

   /* if inputA[row] = 1 and AssignAGate[gate] = 1, then
      Output[gate,row] = 0 */
   con NOR_def1 {gate in GATES, row in ROWS}:
      inputA[row] * AssignAGate[gate] <= 1 - Output[gate,row];

   /* if inputB[row] = 1 and AssignBGate[gate] = 1, then
      Output[gate,row] = 0 */
   con NOR_def2 {gate in GATES, row in ROWS}:
      inputB[row] * AssignBGate[gate] <= 1 - Output[gate,row];

   /* if Output[pred,row] = 1, then Output[gate,row] = 0 */
   con NOR_def3 {<pred,gate> in ARCS, row in ROWS}:
      Output[pred,row] <= 1 - Output[gate,row];

   /* if UseGate[gate] = 1 and Output[gate,row] = 0, then
      (inputA[row] = 1 and AssignAGate[gate] = 1)
      or (inputB[row] = 1 and AssignBGate[gate] = 1)
      or sum {<pred,(gate)> in ARCS} Output[pred,row] >= 1 */
   con NOR_def4 {gate in GATES, row in ROWS}:
      inputA[row] * AssignAGate[gate]
    + inputB[row] * AssignBGate[gate]
    + sum {<pred,(gate)> in ARCS} Output[pred,row]
   >= UseGate[gate] - Output[gate,row];

   solve;
   print UseGate AssignAGate AssignBGate;
   print Output;
   create data sol_data1 from [gate] UseGate AssignAGate AssignBGate;
   create data sol_data2 from [gate row] Output;
quit;

Figure 12.3 shows the output from the mixed integer linear programming solver. In this case, five gates are used in the optimal solution.