Formulating and fixing a two-stage stochastic server farm drawback
Stochastic programming (SP) is a framework for modeling optimization issues that contain uncertainty [1]. In lots of circumstances, SP fashions take the type of a two-stage drawback. The primary stage includes discovering the optimum deterministic choices. These choices are based mostly on data we all know to make certain (AKA the here-and-now choices). The second stage includes making choices that depend on randomness (additionally referred to as the recourse determination), given our first-stage choices. The optimization drawback goals to reduce the loss (or maximize the revenue) ensuing from the primary stage determination plus the anticipated loss ensuing from the second stage determination. Mathematically, this may be written within the following format:
On this article, I’ll display tips on how to formulate and clear up certainly one of these issues utilizing Gurobi.
Let’s put this framework into perspective with an instance: a server farm drawback. Let’s say we try to design a server farm for our firm, and we have to set up CPU, GPU, and TPU cores to assist deal with the computing assets of our firm given the quantity of house now we have and our upfront price range for getting servers. We now have a common estimation of the next-month demand for every useful resource and the distributions they observe. For the sake of simplicity, we are going to ignore future months after subsequent month (although it’s potential to do a multi-stage stochastic program to deal with this).
Working the servers sooner or later will price a small quantity, but when we don’t meet the demand we must leverage cloud computing assets which can considerably enhance our operational prices.
On this instance, our first-stage determination (the here-and-now determination) is the variety of every useful resource to purchase. The second-stage (recourse) determination is the variety of cloud-compute to purchase. Our purpose is to reduce the operational price of the server farm. This optimization drawback could be written as follows:
The place x represents how a lot of every core we are going to purchase, y represents how a lot cloud compute we are going to leverage, i is our set up prices, B is our set up price range, s is the scale of the cores, S is our obtainable house, c is our cloud computing prices, and d(xi) is our random demand.
To resolve the issue above, we are going to implement a way referred to as pattern common approximation [2]. This methodology includes producing a big quantity (Okay) of potential realizations (situations) of the random variable by Monte Carlo sampling and treating every realization as a person sub-problem [2]. This helps discretize the randomness and due to this fact makes it solvable with out dropping an excessive amount of constancy of data. Which means that as a substitute of simply having 1 set of second-stage variables, we could have Okay variables and the expectation of our second-stage worth is the typical worth of our realizations. With this, our formulation modifications to:
Whereas this formulation can then be applied in quite a lot of programming languages and linear programming solvers (e.x. SCIP, CPLEX, CVXPY), we are going to give attention to fixing this drawback utilizing Gurobi — a commercial-grade, state-of-the-art mathematical programming solver. Gurobi has APIs for languages like Python, MATLAB, R, and Java, however most of its customers choose utilizing the Python API [4], so we are going to use it right here.
First, we are going to import our packages (numpy and gurobipy)in addition to initialize (make up) the info for our drawback.
On this drawback i is the funding price, sis the house every merchandise takes up, Bis our price range, and Sis our most house. One other variable of be aware is the demand in every situation d_xi. We will then use Gurobi to resolve our drawback. First, we are going to outline our mannequin with gp.mannequin(), set the purpose (reduce) in addition to initialize our determination variables.
As you possibly can see within the above examples, each our demand (d_xi) and our second-stage determination variable (y) aren’t single-dimensional vectors, however moderately a matrix since each of those have a situation index in our formulation. After this we will outline our goal operate:
One good factor about Gurobi is that it helps numpy matrix multiplication operations when defining constraints and targets, making it easy to code should you suppose in matrix multiplications (ex. i @ x). Gurobi additionally helps summation operations, making the barrier to entry decrease as effectively. Right here we calculate the primary stage price, then take the typical second stage price.
We will now transfer on to defining our constraints:
The primary line of code ensures that the price of putting in in-house servers doesn’t exceed our price range B. The second line ensures that we solely purchase as many servers as now we have house for. The third line of code ensures the variety of put in servers and quantity of cloud compute assets in situation ok leveraged are sufficient to satisfy the demand in situation ok.
Now that the issue is absolutely outlined, we will merely clear up the issue and get our optimum determination by calling m.optimize():
The optimum variable values are then saved in every variable we outlined and could be accessed through variable_name.x. Whereas we may have gotten the optimum values for each the x and y variables, we solely care in regards to the choices we will make now (x).
This method offers us a high-quality answer, however there are drawbacks.
The primary draw back is that because the variety of situations will increase, the mannequin will get exponentially more durable to resolve. For instance, we solely had 6 true choices we would have liked to make, however utilizing pattern common approximation made our mannequin make 153 choices (3 first-stage, 3 second-stage for 50 situations). Which means that decomposition algorithms (like Benders Decomposition for Linear SPs [3]) typically have to be used to parallelize the computation.
One other consideration is that sadly, Gurobi isn’t free software program. Whereas Gurobi does supply a tutorial license that many college students and researchers leverage, people not affiliated with a college might discover it tough to realize entry to this software program. One open-source different to Gurobi is SCIP [5]. Each share the same modeling language so Gurobi customers can simply adapt to SCIP and vice-versa. I selected to display this idea with Gurobi as a substitute of SCIP attributable to private choice together with Gurobi’s quick solver efficiency. That doesn’t imply that SCIP is inferior. In truth, many optimization researchers who give attention to growing or enhancing optimization algorithms choose SCIP since its open-source nature permits customers to tweak each a part of the solver permitting them to strive new methodologies.
The total code for this drawback could be discovered right here.
Works Cited
[1] A. Philpott, What’s Stochastic Programming. (2022), Stochastic Programming Society.
[2] A. J. Kleywegt, A. Shapiro, T, Homem-de-Mello. The Pattern Common Approximation Methodology for Stochastic Discrete Optimization (2002), SIAM Journal on Optimization.
[3] S. S. Nielsen, S. A. Zenios. Scalable parallel Benders Decomposition for Stochastic linear programming (1997), Parallel Computing Quantity 23, Challenge 8.
[4] Gurobi. Beginning with Gurobi (2022), Gurobi Web site
[5] Bestuzheva et. al. The SCIP Optimization Suite 8.0 (2021), Optimization On-line
