There are generally two steps in solving an optimization problem: model development and optimization

Optimisation is using a set of mathematical techniques to find the best possible solution to a business problem, generally minimising costs, maximising yields, specific resource assignments and exploring best possible time of activities.

Here are some examples of optimisation in achieving business goals (individual or in combination):

• Business optimisation – to improve the business processes
• Rule optimisation – optimise the way the rules are written and making fewer rules
• Hard disk optimisation – compact the hard disk
• DB (query) optimisation – 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 optimisation model (objective function, decision variables, constraints), data (to create the instance of the model) and an optimisation engine/solver (algorithms to solve the model instantly).

In mathematical term, the purpose of optimisation is to find the values for the decision variables to satisfy all constraints and optimise the objective function.

Optimisation Engine / Solver

An optimisation engine or solver is a set of algorithms.

Different algorithms solving different types of optimisation 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

Optimisation Model

The typical optimisation 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 optimisation. 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 “maximise” or “minimise” of the outputs, for example, minimising costs, idle or time, also, maximising 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
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 10000 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 prioritised for fulfilment and shipment
• transition time of Product A from Machine A to Machine B is nonstandard

Optimization Techniques

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

Mathematical (MP)

• Branch: Applied Mathematics
• Root: analytical geometry
• Uses: matrix algebra equations, continuous mathematics and numerical methods form the core
• Assisted: a large number of algorithms and heuristics (rules of thumb)
• Excels at: finding the optimal plan or schedule
• Optimality: applying equations to a large search space of potential solutions
• Application: linear programming (LP), integer programming (IP), Quadratic programming (QP), mixed-integer programming (MIP), MIQP, etc

Constraint (CP)

• Branch: Computer Science (ie Logic Programming)
• Root: symbolic logic and Artificial Intelligence (AI)
• Uses: Logic Programming & Object Oriented Software engineering
• Assisted: appropriate for detailed scheduling problems and certain combinatorial optimisation 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 feasible solutions to large scheduling problems with thousands of individual constraints
• Optimality: 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: 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.

When problems are particularly hard, some hybrid approaches are known to bring "the best of both worlds" - typically a MP + CP approach. This is how batching + detailed scheduling is done in many optimisation tools for manufacturing.

We can help you identify the best technology to solve your problem, create suitable models and benchmark them, using all of the best engines (CPLEX/CPO, Gurobi, LocalSolver and FICO Xpress).