Lower Objective leads to better solution MILP

Question

In this optimization problem, I am trying to maximize the output value representing the "income" of a city based on some arbitrary formula. The formula relies on discrete values, so-called improvements, most of which are variables that the solver is free to play with.

My question relates to the fact that if I specifically divide the objective function so that their magnitude is smaller, it yields better results. I can confirm that because if I then take the values for the improvements (vars) and run them through the formula, I get a better result.

For the code, most of it is jargon and I think is not relevant? I will try to be succinct.

m = gekko.GEKKO(remote=False, name="Optimal Build")
m.options.SOLVER = 1
m.solver_options = ['minlp_gap_tol 1.0e-10',
                    'minlp_integer_tol 1.0e-10']

f = FormulasSolver(m)  # Formulas, external
imps = f.improvements  # Values for each improvement, ie pollution, 
# base cost, prd rate, max number of improvements per imp type...


x = 27 * [0]  # Array of imps

for i in imps.non_constant():
    x[imps.index(i)] = m.Var(value=0, name=i.name, lb=0, ub=i.building_limit, integer=True)

for i in imps.constant():
    x[imps.index(i)] = m.Const(value=constant_buildings[imps.index(i) - 23], name=i.name)


m.Equation("" Sum of all imps, max number of imps is 50 "" <= 50)
m.Equation("" Sum of commerce affecting imps, max commerce is 100% "") <= 100)

commerce = m.Intermediate("" Sum of improvements that affect commerce "")  # Commerce
pollution_index = m.Intermediate("" Sum of improvements that affect pollution "")  # Pollution Index

m.Maximize((
    f.fixed_city_income(2500, 2500, commerce, pollution_index, 365, x[15], x[16])  # Fixed Income
    - sum("" Base cost for every imp "")  # Fixed Cost
    + sum("" Every producing imp "")  # Variable Income
    - sum("" Every manufacturing imp has an associated v cost "")  # Variable Cost
) / 1) <-- Relevant part

m.solve(disp=True)

Iter:     1 I:  0 Tm:      0.00 NLPi:    4 Dpth:    0 Lvs:    3 Obj: -1.05E+06 Gap:       NaN
--Integer Solution:  -1.04E+06 Lowest Leaf:  -1.05E+06 Gap:   9.67E-03
Iter:     2 I:  0 Tm:      0.00 NLPi:    2 Dpth:    1 Lvs:    2 Obj: -1.04E+06 Gap:  9.67E-03
Iter:     3 I:  0 Tm:      0.00 NLPi:    4 Dpth:    1 Lvs:    4 Obj: -1.06E+06 Gap:  9.67E-03
--Integer Solution:  -1.05E+06 Lowest Leaf:  -1.06E+06 Gap:   4.78E-03
Iter:     4 I:  0 Tm:      0.00 NLPi:    2 Dpth:    2 Lvs:    3 Obj: -1.05E+06 Gap:  4.78E-03
.
.
.
Objective      :  -1050396.901745295

Running the imps values given back into the formula will confirm that the imps given by this optimization indeed lead to an "income" of 1,050,396.90

Now changing the objective formula:

m.Maximize((
    f.fixed_city_income(2500, 2500, commerce, pollution_index, 365, x[15], x[16])  # Fixed Income
    - sum("" Base cost for every imp "")  # Fixed Cost
    + sum("" Every producing imp "")  # Variable Income
    - sum("" Every manufacturing imp has an associated v cost "")  # Variable Cost
) / 100) <-- Relevant part

Iter:     1 I:  0 Tm:      0.00 NLPi:   12 Dpth:    0 Lvs:    3 Obj: -1.06E+04 Gap:       NaN
--Integer Solution:  -1.06E+04 Lowest Leaf:  -1.06E+04 Gap:   1.25E-03
Iter:     2 I:  0 Tm:      0.00 NLPi:    2 Dpth:    1 Lvs:    2 Obj: -1.06E+04 Gap:  1.25E-03
Iter:     3 I:  0 Tm:     -0.00 NLPi:    1 Dpth:    1 Lvs:    4 Obj: -1.06E+04 Gap:  1.25E-03
Iter:     4 I:  0 Tm:      0.00 NLPi:    1 Dpth:    1 Lvs:    5 Obj: -1.06E+04 Gap:  1.25E-03
.
.
.
Objective      :  -10613.94773200687

New values through formula -> 1,061,394.77 Thus better solution

If your ```<-- relevant part``` text is included in your tested code, have you tried running it with this commented out: ```# <-- relevant part```? — foam78, Aug 31 '21 at 09:32
It would lead to a syntax error, I just put it there to signal what part of the code is actually different. Some of the stuff in the code like "" Every producing imp "" is psedo code to make it simpler — Mathias Sven, Aug 31 '21 at 10:20

score 1 · Accepted Answer · answered Aug 31 '21 at 15:57

Optimization algorithms can perform better when functions and variables are scaled (see section 2.4 of Chapter 2 of the Design Optimization book). This generally explains why the solver can find a solution faster but does not change the solution for convex optimization problems (one local minimum).

If there are multiple local minima (non-convex problem) then scaling or variable initialization can influence the solution. One observation is that a lower objective is found on the first MINLP iteration (NLP solution that doesn't use integer variables). There is either another objective in the problem that isn't scaled or else the problem is non-convex.

Unscaled

Iter: 1 I:  0 Tm: 0.00 NLPi:    4 Dpth:    0 Lvs:    3 Obj: -1.05E+06

Scaled

Iter: 1 I:  0 Tm: 0.00 NLPi:   12 Dpth:    0 Lvs:    3 Obj: -1.06E+04

If the problem is non-convex then try different initial conditions. Parallelization can help: How to do parallel Python Gekko? but please use GEKKO(remote=False) to solve locally and avoid overloading the public servers.

Lower Objective leads to better solution MILP

1 Answers1