OptimJ

OptimJ - это расширение для Java с языковой поддержкой для написания моделей оптимизации и абстракций для массовой обработки данных. Расширения и собственный продукт, реализующий расширения, были разработаны компанией Ateji, которая прекратила свою деятельность в сентябре 2011 года. ^[1] 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 это можно выразить следующим образом.

 примеры пакетов ;// простая модель для задачи раскраски карты public  model  SimpleColoring  solver  lpsolve {  // максимальное количество цветов  int  nbColors  =  4 ; // переменные решения содержат цвет каждой страны  var  int  belgium  в  1  ..  nbColors ;  var  int  denmark  в  1  ..  nbColors ;  var  int  germany  в  1  ..  nbColors ; // соседние страны должны иметь разные цветовые  ограничения  {  belgium  ! =  germany ;  германия  ! =  дания ;  } // основная точка входа для тестирования нашей модели  public  static  void  main ( String []  args )  {  // создание экземпляра модели  SimpleColoring  m  =  new  SimpleColoring (); // решаем  m . extract ();  м . решить (); // решения для печати  System . из . println ( "Бельгия:"  +  m . value ( m . belgium ));  Система . из . println ( "Дания:"  +  m . value ( m . denmark ));  Система . из . println ( "Германия:"  +  m . value ( m . germany ));  } }

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

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

Понятия, связанные с операциями [ править ]

Модели [ править ]

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

публичная  модель  SimpleColoring  solver  lpsolve

Переменные решения [ править ]

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

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

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

 // тип var для примитивного типа Java  var  int  x ; // тип var для пользовательского класса  var  MyClass  y ;

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

 var  int  germany  в  1  ..  nbColors ;

Это просто сокращение, эквивалентное наложению ограничения на переменную.

Ограничения [ править ]

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

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

 ограничения  {  Бельгия  ! =  Германия ;  германия  ! =  дания ;  }

Оператор !=является стандартным оператором неравенства Java.

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

ограничения  {  ForAll ( Страна  c1  :  страны ,  страны  c2  :  страны ,  : isNeighbor ( c1 , c2 ))  {  цвет [ c1 ]  ! =  цвет [ 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:

 возраст [ "Стефан" ]  =  37 ;  x  =  возраст [ "Линда" ] ;

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

int [ String ]  age  =  {  "Стефан"  ->  37 ,  "Линда"  ->  29  };

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

 int [ String ]  length [ String  name  :  names ]  =  имя . длина ();

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

Расширенная инициализация [ править ]

Кортежи [ править ]

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

 (:  int ,  String  :)  myTuple  =  new  (:  3 ,  «Три»  :);  Строка  s  =  myTuple # 1 ;

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

Диапазоны [ править ]

Понимания [ править ]

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

 // сумма всех целых чисел от 1 до 10  int  k  =  sum  {  i  |  int  i  in  1  ..  10 };

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

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

 // набор всех целых чисел от 1 до 10  HashSet < Integer >  s  =  ` hashSet () {  i  |  int  i  in  1  ..  10 };

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

 // сумма всех квадратов целых чисел от 1 до 10  int  k  =  sum  {  i * i  |  int  i  in  1  ..  10 };

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

 // сумма всех f (i, j) для 0 <= i <10, 1 <= j <= 10 и i! = j  int  k  =  sum {  f ( i , j )  |  Int  I  :  10 ,  ИНТ  J  :  1  ..  10 ,  : я ! = J  }

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

 // выбираем имя среди лиц старше 18 лет  ` multiSet () {  стр . имя  |  Человек  р  :  человек ,  : р . возраст  >  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.

Внешние ссылки [ править ]

• Объектно-ориентированное моделирование с OptimJ
• Языковое руководство OptimJ
• OptimJ GUI

Ссылки [ править ]

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