ОптимДж

ОптимДж

Парадигма	объектно-ориентированный
Разработано	Атеджи
Впервые появился	2006  ( 2006 )
Веб-сайт	www.Ateji.com
Под влиянием
Ява

OptimJ — расширение для Java с поддержкой языка для написания оптимизационных моделей и абстракций для массовой обработки данных. Расширения и запатентованный продукт, реализующий эти расширения, были разработаны компанией Ateji, которая прекратила свою деятельность в сентябре 2011 года. OptimJ стремится предоставить четкую и краткую алгебраическую запись для оптимизационного моделирования, устранить барьеры совместимости между оптимизационным моделированием и инструментами прикладного программирования, а также предоставить экспертам по оптимизации такие методы разработки программного обеспечения, как объектно-ориентированная ориентация и поддержка современных IDE.

Модели OptimJ напрямую совместимы с исходным кодом Java, существующими библиотеками Java, такими как доступ к базе данных, подключение к Excel или графические интерфейсы. OptimJ совместим с такими инструментами разработки, как Eclipse, CVS, JUnit или JavaDoc. OptimJ доступен бесплатно со следующими решателями: форматы файлов lp_solve, glpk, LP или MPS, а также поддерживает следующие коммерческие решатели: MOSEK , IBM ILOG CPLEX Optimization Studio.

Языковые понятия

OptimJ объединяет концепции объектно-ориентированных императивных языков с концепциями языков алгебраического моделирования для задач оптимизации. Здесь мы рассмотрим концепции оптимизации, добавленные в Java, начиная с конкретного примера.

Пример раскраски карты

Цель задачи раскраски карты — раскрасить карту так, чтобы регионы, имеющие общую границу, имели разные цвета. В OptimJ это можно выразить следующим образом.

package examples;

// a simple model for the map-coloring problem
public model SimpleColoring solver lpsolve
{
  // maximum number of colors
  int nbColors = 4;

  // decision variables hold the color of each country
  var int belgium in 1 .. nbColors;
  var int denmark in 1 .. nbColors;
  var int germany in 1 .. nbColors;

  // neighbouring countries must have a different color
  constraints {
    belgium != germany;
    germany != denmark;
  }

  // a main entry point to test our model
  public static void main(String[] args)
  {
    // instantiate the model
    SimpleColoring m = new SimpleColoring();

    // solve it
    m.extract();
    m.solve();

    // print solutions
    System.out.println("Belgium: " + m.value(m.belgium));
    System.out.println("Denmark: " + m.value(m.denmark));
    System.out.println("Germany: " + m.value(m.germany));
  }
}

Читатели, знакомые с Java, заметят сильное сходство с этим языком. Действительно, OptimJ является консервативным расширением Java: каждая допустимая программа Java также является допустимой программой OptimJ и имеет такое же поведение.

В этом примере раскраски карты также показаны функции, специфичные для оптимизации, которые не имеют прямого эквивалента в Java, представленные ключевыми словами model, var, constraints.

Концепции, специфичные для OR

Модели

Модель — это расширение класса Java, которое может содержать не только поля и методы, но также ограничения и целевую функцию. Он представлен model ключевое слово и следует тем же правилам, что и объявления классов. Неабстрактная модель должна быть связана с решателем, представленным ключевым словом solver. Возможности решателя будут определять, какие ограничения могут быть выражены в модели, например, линейный решатель, такой как lpsolve, допускает только линейные ограничения.

public model SimpleColoring solver lpsolve

Переменные решения

Императивные языки, такие как Java, предоставляют понятие императивных переменных , которые в основном представляют собой области памяти, в которые можно записывать и читать.

OptimJ также вводит понятие переменной решения, которая по сути представляет собой неизвестную величину, значение которой ищется. Решение задачи оптимизации — это набор значений для всех ее переменных решения, который учитывает ограничения проблемы — без переменных решения было бы невозможно выразить задачи оптимизации. Термин «переменная решения» пришел из сообщества оптимизации, но переменные решения в OptimJ — это та же концепция, что и логические переменные в логических языках, таких как Пролог.

Переменные решения имеют специальные типы, определяемые ключевым словом var. Существует var type для каждого возможного типа Java.

  // a var type for a Java primitive type
  var int x;

  // a var type for a user-defined class
  var MyClass y;

В примере с раскраской карты были введены переменные решения вместе с диапазоном значений, которые они могут принимать.

  var int germany in 1 .. nbColors;

Это всего лишь сокращенный эквивалент ограничения переменной.

Ограничения

Ограничения выражают условия, которые должны соблюдаться при любом решении задачи. Ограничением может быть любое логическое выражение Java, включающее переменные решения.

В примере с раскраской карты этот набор ограничений гласит, что при любом решении задачи раскраски карты цвет Бельгии должен отличаться от цвета Германии, а цвет Германии должен отличаться от цвета Дании.

  constraints {
    belgium != germany;
    germany != denmark;
  }

Оператор != — стандартный оператор Java «не равно».

Ограничения обычно появляются пакетами и могут быть определены количественно с помощью forall оператор. Например, вместо явного перечисления всех стран и их соседей в исходном коде можно использовать массив стран, массив переменных решения, представляющих цвет каждой страны, и массив boolean[][] neighboring или предикат (булева функция) boolean isNeighbor().

constraints {
  forall(Country c1 : countries, Country c2 : countries, :isNeighbor(c1,c2)) {
    color[c1] != color[c2];
  }
}

Country c1 : countries это генератор: он повторяет c1 по всем значениям в коллекции countries.

:isNeighbor(c1,c2) является фильтром: он сохраняет только сгенерированные значения, для которых предикат истинен (символ : можно прочитать как «если»).

Предполагая, что массив countries содержит belgium, germany и denmarkи что предикат isNeighbor возвращает true для пар( Belgium , Germany) и ( Germany, Denmark), то этот код эквивалентен блоку ограничений исходного примера раскраски карты.

Цели

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

Общие концепции

Общие концепции — это концепции программирования, которые не являются специфическими для задач ИЛИ и имеют смысл для разработки приложений любого типа. Общие концепции, добавленные в Java OptimJ, упрощают и делают выражение моделей ИЛИ более кратким. Они часто присутствуют в старых языках моделирования и, таким образом, предоставляют экспертам OR привычный способ выражения своих моделей.

Ассоциативные массивы

В то время как массивы Java могут индексироваться только целыми числами, отсчитываемыми от 0, массивы OptimJ могут индексироваться значениями любого типа. Такие массивы обычно называются ассоциативными массивами или картами. В этом примере массив age содержит возраст лиц, идентифицированный по их имени:

  int[String] age;

Тип int[String] обозначающий массив int индексируется String. Доступ к массивам OptimJ с использованием стандартного синтаксиса Java:

  age["Stephan"] = 37;
  x = age["Lynda"];

Традиционно ассоциативные массивы широко используются при решении задач оптимизации. Ассоциативные массивы OptimJ очень удобны, если они связаны с их конкретным синтаксисом инициализации. Начальные значения могут быть заданы в интенсиональном определении , например:

int[String] age = { 
  "Stephan" -> 37,
  "Lynda"   -> 29 
};

или может быть дано в экстенсиональном определении , например:

  int[String] length[String name : names] = name.length();

Здесь каждая из записей length[i] инициализируется с помощью names[i].length().

Кортежи

Кортежи повсеместно используются в вычислениях, но отсутствуют в большинстве основных языков, включая Java. OptimJ предоставляет понятие кортежа на уровне языка, который может быть очень полезен в качестве индексов в сочетании с ассоциативными массивами.

  (: int, String :) myTuple = new (: 3, "Three" :);
  String s = myTuple#1;

Типы кортежей и значения кортежей записываются между (: и :).

Понимания

Понятия , также называемые агрегатными операциями или сокращениями, представляют собой выражения OptimJ, которые расширяют данную бинарную операцию над набором значений. Типичным примером является сумма:

  // the sum of all integers from 1 to 10
  int k = sum { i | int i in 1 .. 10};

больших сигм, Эта конструкция очень похожа на нотацию суммирования используемую в математике, с синтаксисом, совместимым с языком Java.

Понимания также можно использовать для создания коллекций, таких как списки, наборы, мультимножества или карты:

  // the set of all integers from 1 to 10
  HashSet<Integer> s = `hashSet(){ i | int i in 1 .. 10};

Выражения понимания могут иметь в качестве цели произвольное выражение, например:

  // the sum of all squares of integers from 1 to 10
  int k = sum { i*i | int i in 1 .. 10};

Они также могут иметь произвольное количество генераторов и фильтров:

  // the sum of all f(i,j), for 0<=i<10, 1<=j<=10 and i!=j 
  int k = sum{ f(i,j) | int i : 10, int j : 1 .. 10, :i!=j }

Понимание не обязательно применимо только к числовым значениям. Понимания построения множеств или мультимножеств, особенно в сочетании с кортежами строк, позволяют выражать запросы, очень похожие на запросы к базе данных SQL:

  // select name from persons where age > 18
  `multiSet(){ p.name | Person p : persons, :p.age > 18 }

В контексте моделей оптимизации выражения понимания предоставляют краткий и выразительный способ предварительной обработки и очистки входных данных, а также форматирования выходных данных.

Среда разработки

OptimJ доступен как плагин Eclipse. Компилятор реализует трансляцию из исходного кода из OptimJ в стандартную Java, обеспечивая тем самым немедленную совместимость с большинством инструментов разработки экосистемы Java.

и быстрое

Поскольку компилятор OptimJ знает структуру всех данных, используемых в моделях, он может генерировать структурированное графическое представление этих данных во время компиляции. Это особенно актуально в случае ассоциативных массивов, где компилятор знает коллекции, используемые для индексации различных измерений.

Базовое графическое представление, создаваемое компилятором, напоминает куб OLAP . Затем его можно настроить по-разному: от простой раскраски до предоставления новых виджетов для отображения элементов данных.

Созданный компилятором графический интерфейс OptimJ избавляет эксперта OR от написания всего связующего кода, необходимого для сопоставления графических библиотек с данными. Он позволяет быстро создавать прототипы, предоставляя немедленные визуальные подсказки о структуре данных.

Другая часть графического интерфейса OptimJ сообщает в режиме реального времени статистику производительности решателя. Эту информацию можно использовать для понимания проблем с производительностью и сокращения времени решения. В настоящее время он доступен только для lp_solve.

Поддерживаемые решатели

OptimJ доступен бесплатно со следующими форматами файлов решателей lp_solve, glpk, LP или MPS, а также поддерживает следующие коммерческие решатели: Mosek, IBM ILOG CPLEX Optimization Studio.

Внешние ссылки

• Объектно-ориентированное моделирование с помощью OptimJ
• Руководство по языку OptimJ
• Графический интерфейс OptimJ

Ссылки

• Быстрая разработка приложений с помощью OPTIMJ, отчет об опыте практикующего специалиста. Дэвид Гравот, Патрик Вири. ЕВРО-2010 (Лиссабон)
• OptimJ используется в модели оптимизации сборочных линий смешанной модели, Мюнстерский университет.
• OptimJ используется в методе расчета приближенного идеального равновесия для повторяющихся игр, Университет Лаваля