3
$\begingroup$

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.

Thanks in advance to whoever will answer.

$\endgroup$
5
$\begingroup$

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).

| improve this answer | |
$\endgroup$

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.