3
$\begingroup$

In an MILP problem, I wonder if it is better to use an objective function that involves as many of the variables of the problem as possible as opposed to an objective function with only a few variables.

I would expect that the "variable rich" objective is the better choice because it carries more information.

I could always put variables in the objective function even if they do not belong there by penalizing them to an extend that they do not do harm.

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ You might be confusing data with information (relevancy). Would you add the amount of eggs uncle Jack's chickens laid yesterday to the objective function, only to multiply that added number by zero? $\endgroup$ – Maarten Mar 31 '20 at 20:37
  • $\begingroup$ Well, if the amount of eggs uncle Jack's chickens laid yesterday are part of my optimization model, yes I would put them in the objective function but not with a penalty of zero. In fact, I am dealing with a scheduling problem where I want to maximize profit. Maximize profit is maximize "amount produced x price". Now if I add to the objective the term - 0,1 production time, I get the solution to the problem much faster. I do not believe that happens by chance. $\endgroup$ – Clement Mar 31 '20 at 20:44
  • 1
    $\begingroup$ After adding those 0, 1 production times, are you getting exactly same solution (probably with a different objective function)? Have you tried a few instances (ideally with different characteristics) to see if its true for all those instances? $\endgroup$ – Mostafa Apr 1 '20 at 3:56
  • $\begingroup$ Yes, it works for different instances. The effect the addition has, I believe, is to avoid some combinations that lead to the same objective. $\endgroup$ – Clement Apr 1 '20 at 6:50
  • $\begingroup$ Could you clarify your thought process by adding the problem formulation? As far as I see it, you've triggered a faster search procedure by chance. Same values are necessary, not sufficient. If the optimal solution is somehow always invariant under adding certain parameters, they hold no added information with regards to the optimum per definition. $\endgroup$ – Maarten Apr 1 '20 at 9:00
5
$\begingroup$

If a problem has multiple optima, adding small penalties or rewards to variables that do not directly contribute to the true objective can help by breaking ties that the solver would otherwise encounter. Note that I said "can" help, not "will" help. The solver would work through those ties on its own, so the added terms only help if you get lucky in the choice of variables and coefficients. As far as I know, you can also make the solution time greater by an unlucky choice of spurious terms.

I think you may also benefit in some cases by avoid degeneracy in the dual of the LP relaxation. Again, I believe this adheres to the old adage about bear hunting: some days you get the bear, and some days the bear gets you.

One thing, however, is certain: if you make the coefficients of the additional terms too large, you can end up with a solution that is optimal in the modified problem but suboptimal in the original problem.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I totally agree with you. I only hoped that this approach has been explored by the theoreticians and that they came up with some helping idea. $\endgroup$ – Clement Apr 2 '20 at 11:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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