Определение затрат / переменных, приводящих к неограниченной задаче оптимизации в ojAlgo - PullRequest
Новая
       11

Определение затрат / переменных, приводящих к неограниченной задаче оптимизации в ojAlgo

0 голосов
/ 17 апреля 2020

Я использую решатель ojAl go linear / quadrati c через ExpressionsBasedModel , чтобы решить расположение графических элементов в библиотеке графиков, чтобы они аккуратно вписывались в границы экрана. В частности, я хочу решить для масштаба и перевода так, чтобы координаты точечной диаграммы заполняли пространство экрана. Я делаю это, объявляя переменные масштаба и трансляции ExpressionsBasedModel и преобразуя координаты диаграммы рассеяния на экран, используя эти переменные, а затем создаю линейные ограничения, которые преобразованные координаты должны проецировать внутри экрана. Я также добавляю отрицательные затраты к переменным масштаба, чтобы они были максимальными, и график рассеяния покрывал как можно больше экранного пространства. Моя проблема заключается в том, что в некоторых особых случаях, например, если у меня есть только одна точка для построения графика, это приводит к неограниченной проблеме, когда масштаб движется к бесконечности без каких-либо активных ограничений. Как я могу определить переменные масштаба, для которых это произойдет, и зафиксировать их в некоторых значениях по умолчанию?

Чтобы проиллюстрировать вышеуказанную проблему, я создал игрушечную библиотеку для построения графиков (полную библиотеку, которую я Я работаю над слишком большой, чтобы вписаться в этот вопрос). Чтобы помочь расположить графические элементы, у меня есть класс задачи: 

class Problem {
    private ArrayList<Variable> _scale_variables = new ArrayList<Variable>();
    private ExpressionsBasedModel _model = new ExpressionsBasedModel();

    Variable freeVariable() {
        return _model.addVariable();
    }

    Variable scaleVariable() {
        Variable x = _model.addVariable();
        x.lower(0.0); // Negative scale not allowed
        _scale_variables.add(x);
        return x;
    }

    Expression expr() {
        return _model.addExpression();
    }

    Result solve() {
        for (Variable scale_var: _scale_variables) {

            // This is may result in unbounded solution for degenerate cases.
            Expression expr = _model.addExpression("Encourage-larger-scale");
            expr.set(scale_var, -1.0);
            expr.weight(1.0);
        }
        return _model.minimise();
    }
}

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

class Transform2d {
    Variable x_scale;
    Variable y_scale;
    Variable x_translation;
    Variable y_translation;

    Transform2d(Problem problem) {
        x_scale = problem.scaleVariable();
        y_scale = problem.scaleVariable();
        x_translation = problem.freeVariable();
        y_translation = problem.freeVariable();
    }

    void respectBounds(double x, double y, double marker_size,
        double width, double height,
        Problem problem) {
        // Respect left and right screen bounds
        {
            Expression expr = problem.expr();
            expr.set(x_scale, x);
            expr.set(x_translation, 1.0);
            expr.lower(marker_size);
            expr.upper(width - marker_size);
        }

        // Respect top and bottom screen bounds
        {
            Expression expr = problem.expr();
            expr.set(y_scale, y);
            expr.set(y_translation, 1.0);
            expr.lower(marker_size);
            expr.upper(height - marker_size);
        }            
    }
}

Метод respectBounds используется для добавления ограничений одной точки на диаграмме рассеяния класс Problem, упомянутый ранее. Чтобы добавить все точки графика рассеяния, у меня есть эта функция: 

void addScatterPoints(
    double[] xy_pairs,

    // How much space every marker occupies
    double marker_size,

    Transform2d transform_to_screen,

    // Screen size
    double width, double height,

    Problem problem) {

    int data_count = xy_pairs.length/2;
    for (int i = 0; i < data_count; i++) {
        int offset = 2*i;
        double x = xy_pairs[offset + 0];
        double y = xy_pairs[offset + 1];
        transform_to_screen.respectBounds(x, y, marker_size, width, height, problem);
    }
}

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

    Problem problem = new Problem();
    double marker_size = 4;
    double width = 800;
    double height = 600;

    double[] data_to_plot = new double[] {
        1.0, 2.0,
        4.0, 9.3,
        7.0, 4.5};

    Transform2d transform = new Transform2d(problem);
    addScatterPoints(data_to_plot, marker_size, transform, width, height, problem);

    Result result = problem.solve();
    System.out.println("Solution: " + result);

, который печатает Solution: OPTIMAL -81.0958904109589 @ { 0, 81.0958904109589, 795.99999999999966, -158.19178082191794 }.

Так выглядит вырожденный случай, изображая две точки с одинаковой координатой y : 

    Problem problem = new Problem();

    double marker_size = 4;
    double width = 800;
    double height = 600;

    double[] data_to_plot = new double[] {
        1, 1,
        9, 1
    };

    Transform2d transform = new Transform2d(problem);
    addScatterPoints(data_to_plot, marker_size, transform, width, height, problem);

    Result result = problem.solve();
    System.out.println("Solution: " + result);

Отображает Solution: UNBOUNDED -596.0 @ { 88.44444444444444, 596, 0, 0 }. Как упоминалось ранее, , мой вопрос : Как я могу обнаружить переменные масштаба, отрицательные затраты которых приведут к неограниченному решению, и ограничить их некоторым значением по умолчанию, чтобы мое решение не было неограниченным?

...