TransWikia.com

Find a particular optimal solution

Operations Research Asked by LJG on August 19, 2021

After writing an integer linear program in AMPL, I solved it using CPLEX. Now, I have some variables that must necessarily be 1, others that must necessarily be 0 and finally it is possible that some variables are free and therefore the number of optimal solutions can be greater than one.

My question is: is there a way in AMPL to force all free variables to 0?

I need this to find the solution that makes the most sense from a practical point of view.

One Answer

I don't think there is anything special in AMPL for doing this, but it can be done.

Option 1 is to add a term to the objective that penalizes the sum of all variables. (I'm assuming that all variables are nonnegative.) This will encourage the solver to force your "free" variables to zero. The catch is that you have to multiply this term by a coefficient that is small enough to prevent the secondary goal of getting the free variables to be zero from leading the solver to a suboptimal solution with regard to the original objective, while at the same time is not so small that the solver basically considers that term to be rounding error and ignores it.

Option 2 is to solve the model twice. First solve the initial model. Next, add a constraint that says the objective value has to be at least as good as the optimal value (with perhaps a small adjustment away from optimality to account for rounding error), change the objective to minimize the sum of the variables, and solve again.

Neither of these is foolproof, by the way. Assume there are three "free" variables. It is possible that the solver will have a choice between a solution with two small free variables and one zero versus a solution with one large free variable and two zeros, in which case the first solution might win in terms of the "sum of variables" criterion. Unfortunately, maximizing the actual number of zeros might involve adding binary variables (unless the "free" variables are all binary in the first place).

Correct answer by prubin on August 19, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP