Problem Types - Overview

In an optimization problem, the types of mathematical relationships between the objective and constraints and the decision variables determine how hard it is to solve, the solution methods or algorithms that can be used for optimization, and the confidence you can have that the solution is truly optimal.

A key issue is whether the problem functions are convex or non-convex:  Click Convex Optimization Problems to learn more.  If the objective and all constraints are convex, you can be confident of determining whether there is a feasible solution, finding the globally optimal solution, and solving the problem up to very large size.  If any functions are non-convex, the problem is much harder and you cannot be certain of any of these things.

Below is a list of optimization problem types, arranged in order of increasing difficulty for the solution methods.  To learn more about each type of problem, please click the topics below.

All linear functions and some quadratic functions are convex, and the cone constraints in conic optimization problems are also convex functions.  Some but not all smooth nonlinear functions are convex.  Integer and constraint programming problems are inherently non-convex.  Global optimization methods are designed to solve non-convex problems.

When evaluating your objective and constraint formulas, bear in mind that only the parts of formulas that are dependent on the decision variables count.  An Excel formula such as =IF(C1>10,D1,2*D1) is nonsmooth if C1 depends on the decision variables.  But if C1 doesn't depend on the variables, then only D1 or 2*D1 -- not both -- can be selected during the optimization. So if D1 is a linear function of the variables, then the IF expression is also a linear function of the variables.

To learn more about Frontline Systems' technology and products for each of these problem types, please click on  Solver Technology. 

To choose the method most appropriate for your problem, Select the Best Product for Your Needs.

(Note: Links with # are intentionally not active yet.)