OptimJ - OptimJ

OptimJ
Парадигма объектно-ориентированный
Разработано Ateji
Впервые появился 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 форматы файлов, а также поддерживает следующие коммерческие решатели: Gurobi , 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 . Возможности решателя будут определять, какие ограничения могут быть выражены в модели, например, линейный решатель, такой как lp resolve , допускает только линейные ограничения. 

public model SimpleColoring solver lpsolve

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

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

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

Переменные решения имеют специальные типы, введенные ключевым словом var . Для var каждого возможного типа 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, упрощают или упрощают выражение моделей ИЛИ. Они часто присутствуют в более старых языках моделирования и, таким образом, предоставляют специалистам по операционной системе знакомый способ выражения своих моделей.

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

В то время как массивы 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 GUI и быстрое прототипирование

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

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

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

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

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

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

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

использованная литература