Obtaining a good suboptimal solution from ojalgo for a linear optimisation

Question

Introduction

I'm trying to use the ojalgo library to produce a solution to controlling thrusters placed in arbitrary places to generate an overall requested rotation and translation. Sometimes the requested rotation and translation will not be possible but I'd like it to have a go in those situations.

Issue

I've created this minimal example of the ExpressionsBasedModel I've set up.

If I request a set of conditions that are possible I get a good result:

    Variable thruster1 = new Variable("t1").lower(0).upper(1).weight(0.1);
    Variable thruster2 = new Variable("t2").lower(0).upper(1).weight(0.1);

    ExpressionsBasedModel model = new ExpressionsBasedModel();
    model.addVariable(thruster1);
    model.addVariable(thruster2);

    double targetXThrust = 2;
    
    model.addExpression("XMotion")
            .weight(1)
            .set(thruster1, 1)
            .set(thruster2, 1).lower(targetXThrust).upper(targetXThrust);

    Optimisation.Result minimised = model.minimise();
    System.out.println(minimised); //outputs 1,1

But if I request something that isn't quite possible

    double targetXThrust = 2.1;
    
    model.addExpression("XMotion")
            .weight(1)
            .set(thruster1, 1)
            .set(thruster2, 1).lower(targetXThrust).upper(targetXThrust);
    System.out.println(minimised); //outputs 0.5,0.5

I would ideally like a good suboptimal solution (1,1) but instead it seems to give up and returns 0.5,0.5 instead

Question

Is it possible to get a good suboptimal solution for an impossible to fully fulfil problem?

Possible the problem is that I want to minimise the error on the expressions, but I think its actually minimising the values (while trying to meet the constraints)

I do have a hacky solution, introducing an extra variables; badness which is allowed any positive value (and contributes to XMotion) and has a very high weight. This leads to the model only using it if it really really has to, but ensures a solution is always possible (from the solvers perspective). If I don't get an answer I'll post that, but it doesn't feel right — Richard Tingle, Aug 28 '21 at 12:36

score 1 · Answer 1 · answered Aug 28 '21 at 12:58

Actually, I've come around to what I previously was calling hacky, as it recasts it as an actual optimisation problem, so I'm posting it as a solution (still open to better answers though)

Solution

Introduce positiveError and negativeError variables for each equation to ensure that the problem has a solution, but give them large weights so the solver avoids using them

Example

//thrusters at powers between 0 and 1 (hard limits)
Variable thruster1 = new Variable("t1").lower(0).upper(1).weight(0.1); //we'd rather an engine was off if possible so give it a small weight
Variable thruster2 = new Variable("t2").lower(0).upper(1).weight(0.1);
Variable positiveError = new Variable("positiveError").lower(0).weight(10000); //we'd rather a solution was found if at all possible
Variable negativeError = new Variable("negativeError").lower(0).weight(10000);

ExpressionsBasedModel model = new ExpressionsBasedModel();
model.addVariable(thruster1);
model.addVariable(thruster2);
model.addVariable(positiveError);
model.addVariable(negativeError);

double targetXThrust = 2.1;

model.addExpression("XMotion")
        .set(thruster1, 1)
        .set(positiveError, 1)
        .set(negativeError, -1)
        .set(thruster2, 1)
        .lower(targetXThrust)
        .upper(targetXThrust);

Optimisation.Result minimised = model.minimise();
System.out.println(minimised); //prints 1, 1, 0.1, 0

This approach also allows me to define which error I care more about, as I can give different error variables different weights

A variation to perhaps try is to do it in two steps. First try to minimise the error. If it's possible to bring that to 0.0 then optimise the other stuff. Should be possible to modify the ExpressionsBasedModel instance you have. — apete, Aug 28 '21 at 13:26