Linear and Integer Programming
A linear program is constituted of a linear objective function that models a profit to maximize or a cost to minimize, and a set of linear constraints that restrict decision variables. It has been the subject of very extensive research, and was given a major boost by Dantzig’s development of the Simplex method.
Mathematically, a linear program is formulated as:
$$Min_x \space c x $$
$$s.t. \space Ax \geq b, \space x \geq 0$$
Some problems may require the use of all or some integer variables. These types of problems are difficult to solve optimally in a reasonable amount of time. Solving integer programs requires combining the simplex method and a branch and bound technique, often supplemented by domain reduction techniques (constraint programming), column generation or generation of cutting planes.
Today, powerful commercial and non-commercial solvers capable of solving problems with up to millions of variables and thousands of constraints are available, there are a variety of relative performance profiles available, such as CPLEX , Gurobi and GLPK.
A dynamic programming model is described by a process of states with set of decisions, transitions and a return. The process starts at an initial state and evolves until it reaches a final state. The problem consists in finding the sequence that maximizes the total return.
In dynamic programming, the optimal solution is obtained by combining optimal solutions of sub-problems.
Dynamic Programming has applications in numerous fields, such as economics and finance.
In a stochastic process, the attributes of the system randomly change over time. For example, the number of costumers in a checkout line or the number of cars arriving at a highway toll station. A model is constructed by enumerating the states in which the system can be found at a point of time into a linear measure through which the system moves.
For instance, stochastic processes can be used to study the resources of an insurance company, such as the resources of the insurance company at time t are defined by a random variable that increases at a randomly fluctuating but fairly steady rate as premiums come in, but is subject to sudden falls as claims are met.
Simulation allows a decision maker to run “what ifs” scenarios on an entire process. It is widely used to analyze stochastic processes by repeatedly imitating the evolution of the process or system. It randomly generates the various events that may occur in the system to obtain statistical observation of its performances.
A simulation model requires to define the possible states, identify the possible events, randomly generate the events and identify state transitions over time.
Matthias Miltenberger, Introduction to the SCIP Optimization Suite (2015),Zuse Institute Berlin, http://co-at-work.zib.de/berlin2015/files/introduction_to_SCIP_Opt_Suite.pdf
Koch T., Martin A., Pfetsch M.E. (2013) Progress in Academic Computational Integer Programming. In: Jünger M., Reinelt G. (eds) Facets of Combinatorial Optimization. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38189-8_19