CP-SAT - Steel Mill Slab

import { CpSat, setWorkerBridgeEnabled, type SatParameters } from 'or-tools-wasm/cp-sat';

type Order = { width: number; color: number };
type Column = { orders: number[]; load: number; loss: number };
type CpModelInput = {
  name: string;
  variables: Array<{ name: string; domain: number[] }>;
  constraints: Array<{ name?: string; linear: { vars: number[]; coeffs: number[]; domain: number[] } }>;
  objective: { vars: number[]; coeffs: number[] };
};

const capacities = [0, 17, 44];
const orders: Order[] = [
  { width: 4, color: 1 },
  { width: 22, color: 2 },
  { width: 9, color: 3 },
  { width: 5, color: 1 },
  { width: 8, color: 2 },
  { width: 3, color: 3 },
];

function lossForLoad(load: number) {
  const capacity = capacities.find((value) => value >= load) ?? capacities[capacities.length - 1];
  return capacity - load;
}

function enumerateColumns(): Column[] {
  const maxCapacity = Math.max(...capacities);
  const columns: Column[] = [];
  const visit = (nextOrder: number, selected: number[], load: number, colors: Set<number>) => {
    columns.push({ orders: [...selected], load, loss: lossForLoad(load) });
    for (let orderId = nextOrder; orderId < orders.length; ++orderId) {
      const order = orders[orderId];
      const nextColors = new Set(colors).add(order.color);
      if (load + order.width > maxCapacity || nextColors.size > 2) continue;
      visit(orderId + 1, [...selected, orderId], load + order.width, nextColors);
    }
  };
  visit(0, [], 0, new Set());
  return columns.filter((column) => column.orders.length > 0);
}

function buildSteelMillModel(): CpModelInput {
  const columns = enumerateColumns();
  const variables = columns.map((_, index) => ({ name: `use_column_${index}`, domain: [0, 1] }));
  const constraints = orders.map((_, orderId) => {
    const coveringColumns = columns
      .map((column, columnId) => (column.orders.includes(orderId) ? columnId : -1))
      .filter((columnId) => columnId >= 0);
    return {
      name: `cover_order_${orderId}`,
      linear: {
        vars: coveringColumns,
        coeffs: Array(coveringColumns.length).fill(1),
        domain: [1, 1],
      },
    };
  });

  return {
    name: 'steel_mill_slab',
    variables,
    constraints,
    objective: {
      vars: columns.map((_, index) => index),
      coeffs: columns.map((column) => column.loss),
    },
  };
}

setWorkerBridgeEnabled(true);
const model = await CpSat.createModel(buildSteelMillModel());
const validation = await CpSat.validate(model);
if (!validation.ok) throw new Error(validation.message);

const params: SatParameters = { numWorkers: 4, logSearchProgress: true };
const result = await CpSat.solve(model, params);
console.log(result.response?.objectiveValue, result.response?.solution);