FICO
FICO Xpress Optimization Examples Repository
FICO Optimization Community FICO Xpress Optimization Home
Back to examples browserPrevious exampleNext example

Project planning with resource constraints

Description
Over the next 6 months we have three projects which can be done. Each of these projects has a profile of manpower requirements over its lifetime, and a benefit which accrues each month when the project has been completed. Our problem is to determine when each project is to start, subject to the constraint that in no month can we try to use more manpower than is available.
  • simple MIP problem
  • alternative formulation using binary variables or SOS-1
  • if-then-else statement
Further explanation of this example: 'Xpress teaching material', Section 2.3 'SOS-1: Manpower planning'; 'Applications of optimization with Xpress-MP', Section 3.4.4 'Special Ordered Sets of type 1'. Similar problem: Section 7.1 'Construction of a stadium'

projplangr.zip[download all files]

Source Files





projplan_graph.mos

(!******************************************************
   Mosel Example Problems
   ======================

   file projplan.mos
   `````````````````
   TYPE:         Planning projects with resource constraints
   DIFFICULTY:   3
   FEATURES:     MIP problem, alternative formulation with SOS-1,
                 tricky formulation of resource use profiles and
                 calculation of benefits, graphical solution representation
   DESCRIPTION:  Over the next 6 months we have three projects which can 
                 be done. Each of these projects has a profile of manpower 
                 requirements over its lifetime, and a benefit which accrues 
                 each month when the project has been completed.
                 Our problem is to determine when each project is to start, 
                 subject to the constraint that in no month can we try to 
                 use more manpower than is available.     
   FURTHER INFO: `Applications of optimization with Xpress-MP teaching 
                 material', Section 2.3 `SOS-1: Manpower planning';
                 `Applications of optimization with Xpress-MP', 
                 Section 3.4.4 `Special Ordered Sets of type 1'.
                 Similar problem:
                 Section 7.1 `Construction of a stadium'

   (c) 2008 Fair Isaac Corporation
       author: S. Heipcke, 2001, rev. Sep. 2017
*******************************************************!)

model "Manpower planning" 
 uses "mmxprs", "mmsvg"

 parameters
  USESOS = false                   ! Set to true to use formulation with SOS
 end-parameters

 declarations
  NP = 3                           ! Number of projects
  PROJ = 1..NP                     ! Projects
  NT = 6                           ! Time horizon
  TIME = 1..NT                     ! Months to plan for
  DUR: array(PROJ) of integer      ! Duration of projects
  RESUSE: array(PROJ,TIME) of integer  ! Resource usage per project
  RESMAX: array(TIME) of integer   ! Resource available per month
  BEN: array(PROJ) of real         ! Benefit per month once project finished

  x: array(PROJ,TIME) of mpvar     ! 1 if project p starts in month t, else 0
  start: array(PROJ) of mpvar      ! Starting time of project t
 end-declarations

 initializations from 'projplan.dat'
  DUR RESMAX BEN RESUSE
 end-initializations
   
! Objective: Maximize Benefit
 MaxBen:= 
  sum(p in PROJ,t in 1..NT-DUR(p)) (BEN(p)*(NT-t-DUR(p)+1)) * x(p,t)

! Resource availability
 forall(t in TIME)
  Capacity(t):= sum(p in PROJ,s in 1..t) RESUSE(p,t-s+1)*x(p,s) <= RESMAX(t)

! Each project starts once and only once
 forall(p in PROJ) OneStart(p):= sum(t in TIME) x(p,t) = 1

! Connect variables x(p,t) and start(p)
 forall(p in PROJ) Link(p):= sum(t in TIME) t*x(p,t) = start(p)

! Finish everything by the end of the planning period
 forall(p in PROJ) start(p) <= NT-DUR(p)+1
 
 if not USESOS then                ! Turn variables x into binaries
  forall(p in PROJ,t in TIME) x(p,t) is_binary
 else                              ! Define SOS-1 sets
  forall(p in PROJ) StartSet(p):= sum(t in TIME) t*x(p,t) is_sos1
 end-if

! Solve the problem
 maximize(MaxBen)

! Solution printing
 writeln("Total benefit: ", getobjval)
 write("   ")
 forall(t in TIME) write(t)
 writeln
 forall(p in PROJ) do
  write(p, ": ")
  forall(t in TIME) 
   write( if(t<getsol(start(p)), " ", if(t<getsol(start(p))+DUR(p), "*", "B")) )
  writeln 
 end-do

! Solution drawing
 declarations
  ProjGraph: array(PROJ) of string
 end-declarations

 svgsetgraphviewbox(0,0,NT,max(t in TIME)RESMAX(t)+1) 
 svgsetgraphscale(10)
 svgsetgraphlabels("Time", "Resource usage")

 forall(p in PROJ) do
  ProjGraph(p):= "P"+p
  svgaddgroup(ProjGraph(p), "Project "+p)
  svgsetstyle(SVG_FILL,SVG_CURRENT)
  svgsetstyle(SVG_STROKEWIDTH,0)
 end-do 
 forall(t in TIME) do
  u:=0.0
  forall(p in PROJ) do
   svgaddrectangle(ProjGraph(p), t-1, u, 
                    1, getsol(sum(s in 1..t) RESUSE(p,t-s+1)*x(p,s)))
   u+=getsol(sum(s in 1..t) RESUSE(p,t-s+1)*x(p,s))
  end-do
 end-do
 
 svgaddgroup("Res", "Available resource", SVG_RED)
 svgaddline(sum(t in 1..NT) [t-1, RESMAX(t), t, RESMAX(t)])

 svgsave("projplan.svg")
 svgrefresh
 svgwaitclose("Close browser window to terminate model execution.", 1)
end-model

Back to examples browserPrevious exampleNext example