Note¶

Solver APIs¶

This is the most easy part of the work but it is also very important for the user experience. Many solvers have limited API functions or they just do not provide users the flexibility to use their products.

Usually their documentation is not good either, so you need to create simple examples to test each of the functions to confirm your understanding. If there are some examples being included in the help system it would be really helpful to the users.

Numerical Issues¶

One important topic about optimization is numerical issues. You will not notice these problems everyday but definitely you will encounter them occasionally and you will feel the pain.

If you think the numerical issues are only for the solver developers then you are not correct. As a user, it is also very important to have some knowledge in this area. When you create a model, you may add some unnecessary large bounds for some rows and columns. This will not only make the solver unstable but also increase the optimization time and even lead to wrong solutions. Knowledge in this area will also help you do the performance tuning.

Shadow Price¶

The dual of a constraint, in terms of economics, is also called the shadow price. It is the change of the objective value with per unit change of the constraint RHS, i.e., the potential value introduced when the constraint is tightened or relaxed with per unit value. Shadow prices are an important part of the optimization solution. However, we are frequently confused by some special cases.

If the problem has some redundant constraints, the dual solution is not unique; the optimization solver might randomly choose one of the dual solution. Theoretically, all dual solutions are correct while in some cases we understand that there is only one dual solution that is suitable for our problem. The other dual solution is just the artificial one that is generated by our inappropriate problem formulation. If there are redundant constraints, we need to relax one of the constraint or simply remove one to avoid the non-unique dual issue. Note that you might need to relax the bound of one of the variables in the redundant constraint instead.

In some other cases, we might also be confused by the dual solution of MIP problems. When there are some integer variables in the problem, we can no longer explain the dual in the same way as we explain the dual of LP problems. Integer variables have discrete values, so there might be jumps in the change of the dual of some constraints. Under this circumstance, either dual is correct; one is associated with the direction of decreasing the constraint RHS and the other is for the increasing of the RHS.