1

I am currently setting up an optimization problem that has as objective to define some parameters minimizing the distance from some target parameters, given some fixed constraints

Hi already set up the problem in Excel Solver and works fine, but when I am translating in LinearOptimization services i get infeasible as result of the optimization.

Unfortunately I am not being able to understand if I set up the math for the absolute difference minimization or I simply did some mistakes in translating the model in Google Linear Optimization Services language. I am not being able to explore the details of the model I set up.

Here is the problem statement

i= 1, 2, 3

Variables
Xi
Di

Parameters
target_i
coeff_i
targetvalue

I want to define Xi such that

minimize sum(abs(Di))
Di = target_i-Xi

with the following contraints

Xi is between 0 and 1
sum(Xi)=1
Sum(Xi*coeff_i)=targetvalue

to decline it in Linear Optimization Service i used the equivalent problem:

minimize sum(Di)

with the following contraints
Di >= target_i-Xi
Di <= -(target_i-Xi)
Xi is between 0 and 1
sum(Xi)=1
Sum(Xi*coeff_i)=targetvalue

Here is the the script I wrote to implement it

// test data  
  var TargetFrequency=2
  var ActualVolumesByBand=[50,100,1200]
  var AvgDropByBand=[5,15,25]
  var TargetDistribution=[0.25,0.5,0.25]
  var Weight=[2,1,2]
  var NumberOfPeriods=52

  var tolerance=0.0001
  var nBands=ActualVolumesByBand.length
  var engine = LinearOptimizationService.createEngine();

// adds a variable for each distribution band

 for (var i=0; i<nBands; i++)

  {
   engine.addVariable('distance'+i, 0, 10000)
   engine.addVariable('FinalDistribution'+i, 0, 1)
  }

 // set objective coefficients using weight and distance 

   for (var i=0; i<nBands; i++)  
  {
   engine.setObjectiveCoefficient('distance'+i, Weight[i])
  }

// set problem
  engine.setMinimization()



////Start Setting COntraints


  // define support arrays
  var LowerBound0=new Array
  for (var i=0;i<nBands;i++ )
  {
    LowerBound0[i]=0
  }
  Logger.log(LowerBound0)
  var UpperBound1000=new Array
  for (var i=0;i<nBands;i++ )
  {
    UpperBound1000[i]=10000
  }
  Logger.log(UpperBound1000)


  var C12VariblesArray= []
  for (var i=0;i<nBands;i++ )
  {
    C12VariblesArray[i]=['distance'+i, 'FinalDistribution'+i]
  }

  Logger.log(C12VariblesArray)


  var C1Coefficients=[]
  for (var i=0;i<nBands;i++ )
  {
    C1Coefficients[i]=[1, 1]
  }
  Logger.log(C1Coefficients)



/// Adding fist constraint for absolute value minimization

engine.addConstraints(TargetDistribution, UpperBound1000 ,C12VariblesArray ,C1Coefficients )
//

    var C2Coefficients=[]
  for (var i=0;i<nBands;i++ )
  {
    C2Coefficients[i]=[-1,1]
  }
  Logger.log(C2Coefficients)

// Adding second constraint for absolute value minimization


engine.addConstraints(TargetDistribution, UpperBound1000,C12VariblesArray ,C2Coefficients )


// adding constraint for integrity of distribution 


  var C34VariblesArray= []
  for (var i=0;i<nBands;i++ )
  {
    C34VariblesArray[i]='FinalDistribution'+i
  }

  Logger.log(C34VariblesArray)


  var C3Coefficients = []
  for (var i=0;i<nBands;i++ )
  {
    c=1
  }

  Logger.log(C3Coefficients)                

  var c3=engine.addConstraint(1, 1)

  for (var i=0;i<nBands;i++ ){
    c3.setCoefficient('FinalDistribution'+i,1 )
  }


// adding constraint for target frequency 

// calculate total volume

var TotalVolume=0

  for (var i=0;i<nBands;i++ )
{
    TotalVolume=TotalVolume+ActualVolumesByBand[i]
}


    var C4Coefficients = []
  for (var i=0;i<nBands;i++ )
  {
    C4Coefficients[i]=TotalVolume/NumberOfPeriods/AvgDropByBand[i]
  }

  Logger.log(C4Coefficients)                  

  var c4=engine.addConstraint(TargetFrequency,TargetFrequency)
  for (var i=0;i<nBands;i++ ){
    c4.setCoefficient('FinalDistribution'+i,C4Coefficients[i] )
  }

  ////Finish setting COntraints


// start solving

var solution = engine.solve();
if (!solution.isValid()) {
  Logger.log('No solution ' + solution.getStatus());
} else {
   for (var i=0;i<nBands;i++ )
  {
    Logger.log('Value of band '+i+': ' + solution.getVariableValue('FinalDistribution'+i));
  }
}

Could you help me understand where is the mistake?

4
  • I have executed your code without any modification and worked just fine. Could you try again? Or maybe you are feeding another data that the one provided that cannot meet the conditions?
    – Raserhin
    Commented Jan 17, 2020 at 16:52
  • Thank you for running it. It runs without problem, but the outcome is not the expected one. If you look at the logger, the final outcome is that the problem is INFEASIBLE, but I know from excel solver that the solution exists. What I cannot understand is if I have mistaken the math problem or to set it up in goggle language since I wasn’t able to find a way to explore the object. Commented Jan 17, 2020 at 18:15
  • It's hard to read your code. It would be helpful for other readers, if you comment your code with your explanation: like //Weight is Xi// distribution is Di and what each loop does. As it is, your explanation and code seem widely different from each other. Reconciling both will take time, which most users wouldn't be willing to spend. Also, if you need Latex type math expressions, it's better to present a screenshot. See How to Ask and minimal reproducible example(Step1 is rewriting your code from scratch)
    – TheMaster
    Commented Jan 17, 2020 at 21:13
  • Step1: Create a new program, adding in only what is needed to see the problem. Use simple, descriptive names for functions and variables – don’t copy the names you’re using in your existing code. Longer the code, lesser the chances of getting a answer.
    – TheMaster
    Commented Jan 17, 2020 at 21:16

1 Answer 1

2

I did not look at the source code, but I saw a problem in your description. You write:

minimize sum(Di)
with the following contraints
Di >= target_i-Xi
Di <= -(target_i-Xi)

This looks incorrect. The math is usually derived as:

min sum(i, |target(i)-X(i)|)

<=>

min sum(i, d(i))
-d(i) <= target(i)-X(i) <= d(i)

<=>

min sum(i, d(i))
d(i) >= target(i)-X(i)
d(i) >= -(target(i)-X(i))    
1
  • Thank you Erwin.It is just the kind of feedback I was looking for! I corrected the math problem according to your indication. Now it works perfectly! Commented Jan 22, 2020 at 14:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.