How can you tell if a problem requires linear or nonlinear programming?

In real cases most of the problem are mixed integer LP. For example production planning will have production decisions in given interval for a product as binary decision variables while the time interval length is a continuous variable optimiser needs to find out. And yes most popular solvers use branch and bound to solve these problems.

If the objective function or one of the constraints or both in a problem are non-linear, then non-linear programming is required. Other than that, linear programming can be used.

Many more basic continuous simple min/max linear programming problems can be solved by graphing out the constraints and calculating the values at the "corner" or valid points were constraints intersect and finding the maximum or minimum value of these as desired in the problem

Branch-and-bound is used to solve mixed-integer-linear-programs (MILP). When using branch-and-bound, the simplex method can be used to solve LP relaxations.

A concave function such as a discounting problem that is based on declining marginal utility is non-linear but can be solved using linear programming using piece wise linear functions. Over the given interval function becomes linear. Also, the maximization problem for a concave function is easier to solve compared to the minimization problem.

The use of Non linear programming first and foremost arises when a problem is best framed by either non linear objective function or constraints. The decision variables can be integer, binary or continuous but how they are solved depends on some structures that can be exploited (convexity) if they exist.

My personal experience in real life situations is that there is no straight fit solution to bring on board an OR algorithm directly. While these algorithms do provide the basics, one has to dwell deeper into the boundary conditions of the situation under study and try to figure out a nomenclature solution

When we say non linear programming it becomes a very broad topic. Most of the cases in mixed integer NLP requires you to linearize the non linear constraint and that in itself will require good aptitude and experience in operations research problem solving. There are other cases which do require other methods to find optimal point. Like newton or gradient methods.

If the relationship (either in objective function or constraint) can be thought as straight line equations, it’s LP, haha. Note: sometimes even for non-linear problem, we linearize it so that LP/MIP solvers can be used (because dealing with non-linear optimization can be tricky, even for small-scale problems).

Estoy de acuerdo en que para saber con certeza si debemos usar Programación Lineal o Programación no Lineal debemos conocer la naturaleza de todas las funciones del modelo. Sin embargo, considero útil que al inicio del proyecto se consulten trabajos previos que nos darán una idea de lo que podríamos tener más adelante!

\- Discrete products or Lumpiness: individual, countable items are produced, or when products come in certain discrete sizes, such as pallets, containers, etc. Or when the decision variable is binary. (integer programming). \- Economies of scale: cost per product decreases for higher volumes. In this case (nonlinear programming). \- Nonlinear costs: costs, such as holding costs for inventories, are exponential or otherwise nonlinear.(nonlinear programming). \- Interdependence between the decision variables: This is when two or more decision variables depend on each other, such as when they are multiplied or divided. In this case, I would use a nonlinear model to account for the interaction effects. (nonlinear programming).

To decide whether a problem needs linear or nonlinear programming, consider these factors: 1. Objective Function & Constraints: - Linear Programming (LP) for linear objective functions and constraints. - Nonlinear Programming (NLP) for nonlinear mathematical relationships. 2. Decision Variable Bounds: - LP often uses linear bounds (x >= 0), while NLP may involve nonlinear bounds. 3. Problem Complexity: - LP suits simpler problems; NLP is for more complex situations with nonlinear dependencies. 4. Real-World Context: - Assess the real-world context to gauge the need for linearity or nonlinearity. Analyze the math, problem complexity, and context to make the right choice.

In operations research, recognizing linear vs. nonlinear problems is key. Linear problems have a straight-line relationship between variables; their objective function and constraints are linear equations. Look for constant coefficients and absence of variable multiplication, divisions, or exponents. Nonlinear problems involve curved relationships, where variables interact in a non-linear way like multiplication, division, or raised to powers. Identifying the nature of relationships in the objective function and constraints is crucial. Nonlinearities often signal complex, real-world scenarios requiring advanced solving techniques.

One of the tricks I always use to linearize a nonlinear problem is to reformulate the function and add a few continuous/binary variables. For example, a function that has absolute value: a <= |x1| This inequality constraint is clearly nonlinear. To linearize it, I introduce a new variable called y. The constraint above can be thus reformulated by a set of sub-constraints: y >= x1 y >= -x1 y >= 0 a <= y

Some non linear functions like conditional constraints can be linearize by writing multiple constraints in linear form. For example if x(t)=1 and x(t-1)=1 then s(t)=1 else s(t)=0 x(t)+x(t-1)-s(t)<=1

Here are some nonlinear functions that can be converted and handled with linear programming (LP): -max -min -if -absolute value

There are a few techniques by which a non-linear programming can be converted into linear programming which includes using binary variables(MILP) with certain required tweaking in logic (without conflicting with the objectives & constraints), Big M method. This is not limited only to these techniques, as a mere understanding about the problem can always help one to create a linear mathematical logic to satisfy the non-linear behaviour of the model. Also, I would say a big NO if the question is 'can all the nonlinear programming can be converted into linear one?'.

Here's another Linearization Examples: 1- Taylor Series Expansion Example: If you have a complex nonlinear function like sin(x), you can approximate it as a linear function for small x using a Taylor series expansion: sin(x) ≈ x. This is a useful linear approximation for small angles. 2- Linear Approximations Example: For a logarithmic function like z = log(x), you can approximate it as a linear function using the first-order Taylor series expansion: z ≈ log(a) + 1/a(x-a), where a is a chosen reference point. These examples demonstrate various ways to simplify or approximate nonlinear problems using linear techniques or transformations. The specific method you choose depends on the nature of the problem you're dealing with.

Don't make the same mistake that I made in grad school. I had to use subtour elimination constraints to solve a traveling salesperson (TSP). I accidentally used a "global optimization" solver instead of a MIP solver like Gurobi or CPLEX. Solvers that are marketed as "global optimization" usually can handle a variety of problems, including nonlinear problems, but may not actually find the global optimal solution. If your problem is linear, then make sure that you are using an LP/MIP solver. By using a solver that can handle nonlinear problems for your linear problem, you may not actually find the global optimal solution.

The choice between linear and nonlinear optimization methods depends on the problem's mathematical characteristics, size, available tools, and the specific goals of your optimization problem. You may need to analyze the problem carefully and potentially consult with experts to make an informed decision. Some factors to consider, involve: problem type, OF and constrains mathematical form, availability of optimization libraries, sensitivity analysis, problem complexity, problem domain, robustness and tolerance, and last but not least trial and error.

Problem: Linear models work well for linear functions and constraints, but nonlinear models can handle more realistic functions and constraints. Data: Linear models are robust and easy to fit with sparse or incomplete data, but nonlinear models can capture more details with rich and smooth data. Resources: Linear models are simple and efficient to solve with methods like simplex, but nonlinear models are complex and challenging to solve with methods like gradient descent or genetic algorithms. The choice is a trade-off between simplicity and accuracy, and it depends on the purpose and objective of the problem. As Box said, "All models are wrong, but some are useful". The best model is the one that is useful and valid for the situation.

In operations research, selecting the best method hinges on understanding problem characteristics and constraints. For linear problems with clear, straightforward relationships, linear programming is efficient. If the problem involves integer variables, like scheduling or routing, integer programming is suitable. For problems with uncertainty or varying parameters over time, stochastic or dynamic programming might be the best approach. Nonlinear problems with complex relationships require nonlinear programming methods. Always consider the problem's scale, complexity, and specific requirements like time or resource constraints to determine the most effective and efficient method.

For learning purposes, you will probably want to use Python instead of MATLAB because Python is free and MATLAB isn't. If you are a student, you may be able to get MATLAB for free through your university though.

Once you are familiar with formulations it is always a good practice to solve those using commercial solvers such as Gurobi/Cplex and use python on IDE such as Jupyter notebook. If you are a student you can get an academic license from Gurobi that is free of cost. Also, pyomo helps to formulate easily.

An interesting type of programming problem is called a minimax problem. Say you want to distribute a set of EMS first responders such that you are maximizing the minimum number of responders in the region with the global minimum number while making sure all requirements are met for other regions which may demand a greater value than the global minimum