Как починить модель упорядочивания в AMPL+HiGHS: alldiff, границы и цель

Почему модель AMPL+HiGHS для упорядочивания с затратами переналадки становилась недопустимой, и как получить рабочую версию с alldiff и корректными границами.

Сокращение переналадок форм кажется простым на первый взгляд: у вас есть набор заданий, каждое привязано к форме, и матрица стоимостей перехода от одной формы к другой. Цель — найти порядок заданий, минимизирующий суммарные затраты на смену формы. На практике достаточно одной крошечной ошибки в модели, чтобы решатель объявил задачу недопустимой или даже не запустился. Ниже — компактный разбор рабочей конфигурации AMPL+HiGHS и точных подводных камней, которые мешали получить допустимое решение.

Постановка задачи

Каждое задание требует ровно одну форму. Смена формы имеет стоимость, заданную матрицей переходов «форма→форма». Мы ищем перестановку заданий, которая минимизирует сумму затрат на смену формы между соседними заданиями.

Код, вызывающий проблему

Следующие фрагменты воспроизводят постановку и шаблон моделирования, из‑за которого запуск оказывался недопустимым. Основная проблема — в файле модели.

%pip install -q amplpy

ENGINE = "highs"

from amplpy import AMPL, ampl_notebook

am = ampl_notebook(
    modules=["highs"],
    license_uuid="default",
)

import pandas as pd

job_to_mold = pd.DataFrame(
    {
        "Job1": {"mold": 1},
        "Job2": {"mold": 2},
        "Job3": {"mold": 1},
        "Job4": {"mold": 3},
        "Job5": {"mold": 2},
        "Job6": {"mold": 3},
        "Job7": {"mold": 2},
    }
).T

mold_move_cost = pd.DataFrame(
    {
        "mold1": {"mold1": 0, "mold2": 2, "mold3": 4},
        "mold2": {"mold1": 2, "mold2": 0, "mold3": 4},
        "mold3": {"mold1": 7, "mold2": 1, "mold3": 0},
    }
).T

%%writefile MfgSequence.mod
set JOBSET;
set TOOLSET;
set jj within {JOBSET,JOBSET};
set mm within {TOOLSET,TOOLSET};
set TURNIDX;

param cost_job{jj};
param cost_mold{mm};
param nj;
param nm;
param nturns;

var pos{JOBSET} integer >=0,<nj

minimize obj:
    sum{k in TURNIDX, a in JOBSET, b in JOBSET}
        (if pos[k]==a and pos[k+1]==b then 1 else 0) * cost_job[a,b];

subject to no_ties{a in JOBSET, b in JOBSET}:
    (pos[a] > pos[b] or pos[a] < pos[b]);

def build_sequence_model(job_to_mold, mold_move_cost):
    mdl = AMPL()
    mdl.read("MfgSequence.mod")

    nj = len(job_to_mold)
    JOBSET = range(nj)
    TURNIDX = range(nj - 1)
    nturns = len(TURNIDX)
    jj_pairs = {(i, j) for i in JOBSET for j in JOBSET}

    mdl.param["nj"] = nj
    mdl.set["JOBSET"] = JOBSET
    mdl.set["TURNIDX"] = TURNIDX
    mdl.set["jj"] = jj_pairs
    mdl.param["nturns"] = nturns

    nm = len(mold_move_cost)
    TOOLSET = range(nm)
    mm_pairs = {(i, j) for i in TOOLSET for j in TOOLSET}

    mdl.param["nm"] = nm
    mdl.set["TOOLSET"] = TOOLSET
    mdl.set["mm"] = mm_pairs

    mcost = mold_move_cost.values
    mdl.param["cost_mold"] = mcost

    j2m = job_to_mold.values
    job_cost = {
        (i, j): mcost[(k, l)].tolist()
        for (i, j) in jj_pairs
        for (k, l) in mm_pairs
        if (j2m[i] - 1) == k and (j2m[j] - 1) == l
    }
    mdl.param["cost_job"] = job_cost

    return mdl

opt = build_sequence_model(job_to_mold, mold_move_cost)
opt.solve(solver=ENGINE)
print(opt.solve_result)
opt.display("pos")

Почему это не работает

Недопустимость возникает не из‑за математики целевой функции упорядочивания. Решению мешает само объявление модели. Первый стоп‑фактор — синтаксическая ошибка: в строке объявления переменной пропущена точка с запятой, поэтому AMPL так и не получает корректную модель для решения.

После исправления синтаксиса всплывает вторая проблема. Строгая верхняя граница для целочисленной переменной не позволяет HiGHS вывести пригодные границы. Область значений переменной задана строгим неравенством, и из‑за этого решатель не видит валидной верхней границы. Поскольку переменная целочисленная, верхнюю границу нужно задавать нестрого и равной «на единицу меньше количества». Иными словами, замените строгую верхнюю границу на нестрогую, уменьшенную на единицу.

Есть и более аккуратный способ гарантировать, что каждое задание встречается в последовательности ровно один раз. Вместо попарных неравенств через логическую дизъюнкцию используйте ограничение alldiff над переменными позиций. Оно напрямую выражает попарную различность и задаёт идею перестановки.

Исправление и компактная модель

Целевая функция целиком определяется переходами между соседними заданиями и связанными затратами на смену формы. Ниже — формулировка, которая устраняет синтаксическую ошибку, использует ограничение alldiff для перестановки и задаёт корректную нестрогую границу.

set JOBSET;
set TOOLSET;
set jj within {JOBSET,JOBSET};
set mm within {TOOLSET,TOOLSET};
set TURNIDX;

param cost_job{jj};
param cost_mold{mm};
param nj;
param nm;
param nturns;

var pos{JOBSET} integer >= 0, <= nj - 1;

minimize total_cost:
    sum{k in TURNIDX, a in JOBSET, b in JOBSET}
        if pos[k]==a and pos[k+1]==b then cost_job[a,b];

subject to visit_every_job:
    alldiff{k in JOBSET} pos[k];

С этой формулировкой остальная интеграция с Python остаётся прежней. Вы читаете файл модели, загружаете JOBSET, TURNIDX и матрицу стоимостей, выведенную из соответствий «задание→форма», и решаете задачу в HiGHS.

model = build_sequence_model(job_to_mold, mold_move_cost)
model.solve(solver=ENGINE, verbose=True)
assert model.solve_result == "solved", model.solve_result
sol = model.var['pos'].to_dict()
print(sol)

Для приведённых данных решение такое:

{0: 3, 1: 5, 2: 1, 3: 4, 4: 6, 5: 2, 6: 0}

Почему это важно

Модели упорядочивания чувствительны к мелочам в формулировке. Пропущенная точка с запятой не даёт AMPL даже разобрать модель. Строгое неравенство для целочисленной переменной превращается для решателя в отсутствие верхней границы. А выражать перестановку через alldiff и яснее, и менее подвержено ошибкам, чем вручную кодировать попарные неравенства логическими дизъюнкциями.

Итоги

Если модель упорядочивания неожиданно не имеет допустимых решений, начните с проверки синтаксиса и границ целочисленных переменных. Там, где нужно, замените строгие границы на нестрогие и используйте ограничение alldiff, чтобы утверждать уникальность каждой позиции. Сохраняйте цель напрямую через переходы между соседними заданиями — так формулировка остаётся компактной и естественно согласуется с матрицей стоимостей смен формы.