Optimization Model Development with IBM ILOG CPLEX

Optimization Model Development and Mathematical Techniques for Optimized Solution

In Blog by kaiph1 Comment

Optimization is using a set of mathematical techniques to find the best possible solution to a business problem, generally minimizing costs, maximizing yields, specific resource assignments and exploring best possible time of activities. Here are some examples of optimization in achieving business goals (individual or in combination).

  • Business optimization – to improve the business processes
  • Rule optimization – optimize the way the rules are written and making fewer rules
  • Hard disk optimization – compact the hard disk
  • DB (query) optimization – use best practices to get the best performance of the DB access.
  • Manpower planning – reduce the # people to reduce cost
  • Process/project scheduling – keep all the due dates + increase throughput
  • Container positioning – put more containers at the same place / move containers with as few movements as possible
  • Component placement – putting electronic components on boards (eg. Phone/computer cards) – make as few movements of the soldering head as possible to reduce energy / increase throughput

The process involves an optimization model (objective function, decision variables, constraints), data (to create the instance of the model) and an optimization engine/solver (algorithms to solve the model instantly). In mathematical term, the purpose of optimization is to find the values for the decision variables to satisfy all constraints and optimize the objective function.

Optimization Engine / Solver

An optimization engine or solver is a set of algorithms. Different algorithms solving different types of optimization problems. The algorithm is a search mechanism to find better and better solutions efficiently (fast enough) among the different possible alternatives based on the model (type).

Algorithms have been measured how fast they can solve a problem in function of the size (worst-case / average …)

Read: Optimization Engines Make The Industry Efficient

Optimization Model

Optimization Model Development

The typical optimization model development cycle is

  1. Define the scope
  2. Identify objectives, variables and constraints
  3. Gather data (populate the model), create and test a prototype
  4. Edit the model based on test results
  5. Create and test a complete instance of the model and evaluate the performance
  6. Adjust the model

Objective Function

We need to first identify the objective in performing optimization. As well as the metric(s) or Key Performance Indicators (KPIs) we would use, to compare and determine the best solution among the solutions.

Objective function is a mathematical representation of the business objectives or goals to be achieved. It always starts with “maximize” or “minimize” of the outputs, for example, minimizing costs, idle or time, also, maximizing revenue, throughput, profitability, customer satisfaction or employee preferences.

It can be a simple expression involving a single objective or a more complex expression combining several objectives. Each alternative (solution) is measured by a goal (function = cost, time, #people), that is, alternative 1 is better than alternative 2 if the measurement on alternative 1 is better than the (same) measurement on alternative 2. It is said that a solution is optimal if it is the best alternative among all the possible solutions, measured by a goal.

Decision variables

Each model has several variables. Each variable has several possible values. Decision variables are the values or decisions that can be changed to arrive at the best solution possible for the objective function. They are determined during the solution process (solver engine) or possible initial guess.

The inputs can be the demand to be met, resources available, costs, yields & recipes, operational constraints & customer preferences and business goals. They have a domain (a set of possible variables), bounds (upper and lower limit of the domain) and a type (: integer, boolean…). It is important to choose the decision variables well, in which will impact the formulation of the constraints.

  • Resource available: trucks, containers, airplanes, rail cars, people of various skills or seniority, machines, assembly or packaging lines, hospital beds, inventories (raw materials, work in process, finished goods), just-in-time (JIT) deliveries, consumers who could buy a product…
  • Demand to be filled or services to be performed: products to be built, customer orders to be filled, patients to be cared for, marketing offers to make, classes to be scheduled, …sometimes this requires forecasting best case, worst case and most likely over one or multiple time periods.
  • Operating and capital costs: hourly labor rates, overtime premiums, mileage costs, depreciation expense, supply costs, switchover costs, inventory carrying costs, shrinkage costs, marginal costs, cost of capital for new equipment purchases….
  • Yield / throughput assumptions: average driving speed between warehouse A and customer B, minutes to dock and load a truck, cars painted per hour, regular patients served safely by a nurse, percent of customers who will agree to accept a marketing offer in exchange for a discount, revenue per customer at different times of the day…
  • Frequency: Long term planning (annual, quarterly, occasional), Short term planning (Monthly, weekly) and Detailed scheduling (weekly, daily, hourly)

Constraints

Constraints define the relationship between different decision variables. They represent the limits within which the solution should exist. There are 2 types of constraints. (1) Hard constraints should not be violated under any circumstances and (2) soft constraints can be violated under certain circumstances.

  • Global operating constraints: rail yard A is 500 miles from rail yard B, a worker can work no more than 20 hours of overtime in a week, a worker must have a one-hour break no more than four hours from the beginning or end of a shift, the Intensive Care Unit must have at least two nurses with X certification, 50 percent of the nurses on a shift must be fully credentialed, no more than 5 percent of homeowner policies in X state should be from Y county, fund position weights may not be more than then 0.5 percent from index weighs, the production of Product A requires five activities in sequence (each with resource consumption, cost and time properties), truck drivers must end their routes in the same town they started from, the call centre can only call 10,000 people for this marketing campaign, employees can be rotated from day shift to evening shift and evening to night, but not day to night, ….
  • Individual operating constraints and preferences: customer A will not take deliveries between 11.30am and 1pm. Nurse B wants a two-and-a-half-week vacation from X date to Y date, Doctor C requires Nurse D and Nurse E to be assigned to his Operating Room team, orders for top accounts are always prioritized for fulfillment and shipment, transition time of Product A from Machine A to Machine B is nonstandard, ….

Optimization Techniques

There are two main optimization techniques, which are Mathematical Programming (MP) and Constraint Programming (CP).

Technique Mathematical (MP) Constraint (CP)
Branch Applied Mathematics Computer Science (ie Logic Programming)
Root analytical geometry symbolic logic and Artificial Intelligence (AI)
Uses matrix algebra equations, continuous mathematics and numerical methods form the core Logic Programming & Object Oriented Software engineering
Assisted a large number of algorithms and heuristics (rules of thumb) appropriate for detailed scheduling problems and certain combinatorial optimization problems when there are too many possible combinations or too many individual constraints regarding sequence and timing for MP to find a solution in an acceptable timeframe.
Excels at finding the optimal plan or schedule finding feasible solutions to large scheduling problems with thousands of individual constraints
Optimality applying equations to a large search space of potential solutions finding feasibility first, rapidly eliminating possibilities, zeroing in on feasible combinations of resource assignments and activities, based on the systematic comparison of new solutions to a base feasible solution.
Application linear programming (LP), integer programming (IP), Quadratic programming (QP), mixed-integer programming (MIP), MIQP, etc Gantt chart. A time-honoured way to visualise a complete picture of all of the available resources and all of the necessary activities done using the available resources over a period of time.

Comments

  1. Pingback: IBM Decision Optimization for Application Development and Deployment

Leave a Comment