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

Maximise discount at a bookstore

Description
A bookstore has the following discount policy: For each $1 you spend you get 0.1% discount on your next purchase.

Example: If you have to buy three books that cost $10, $20 and $30, you could buy the $30 book today, the $10 book tomorrow (on which you'll get a 3% discount), and the $20 book the following day (on which you'll get a 1% discount). Or you could buy the $30 book and the $20 book today, and the $10 book tomorrow (with a 5% discount).

What is the cheapest way to buy N books (for given prices) ?


Source Files





bookdisc.mos

(!*********************************************************************
   Mosel NL examples
   =================
   file bookdisc.mos
   `````````````````
   A bookstore has the following discount policy: 
   For each $1 you spend you get 0.1% discount on your next purchase.
   Example: 
   If you have to buy three books that cost $10, $20 and $30, you could 
   buy the $30 book today, the $10 book tomorrow (on which you'll get  
   a 3% discount), and the $20 book the following day (on which you'll get 
   a 1% discount). Or you could buy the $30 book and the $20 book today, 
   and the $10 book tomorrow (with a 5% discount).
   What is the cheapest way to buy N books (for given prices) ?

   Based on AMPL model bookdisc.mos by M.J.Chlond
   Reference: J. & L. Poniachik, Hard-to-Solve Brainteasers (p16), Sterling

   (c) 2008 Fair Issac Corporation
       author: S. Heipcke, Jul. 2003, rev. Mar 2013
*********************************************************************!)

model "bookdisc"
 uses "mmxnlp"

 parameters
   N = 8                        ! Number of books
   D = 4                        ! Number of days
   DISC = 0.001                 ! Discount factor
 end-parameters

 declarations
  BOOKS = 1..N                  ! Set of books
  DAYS = 1..D                   ! Set of days
  COST: array(BOOKS) of real	! Cost of books
  ifbuy: array(BOOKS,DAYS) of mpvar  ! ifbuy[i,j]=1 if book i bought on day j, 0 otherwise
  total: array(DAYS) of mpvar	! Total cost of books on day j
  totcost: mpvar                ! Total cost of all books
 end-declarations

 forall(i in BOOKS,j in DAYS) ifbuy(i,j) is_binary
! forall(j in DAYS) total(j) is_integer

! Generate random book prices
 setrandseed(3)
 forall(i in BOOKS) COST(i):= 10+round(50*random)     

! Objective: total cost
 totcost = sum(i in BOOKS) COST(i) -
           sum(k in DAYS | k>1) DISC*total(k-1)*total(k)
 
! Total cost per day
 forall(j in DAYS) total(j) = sum(i in BOOKS) COST(i)*ifbuy(i,j)
! Every book is bought on one day
 forall(i in BOOKS) sum(j in DAYS) ifbuy(i,j) = 1

! Solve the problem
 setparam("xnlp_verbose",true)
 setparam("xnlp_solver",0)

 minimize(totcost)

! Solution printing
 TOTCOST:= sum(i in BOOKS) COST(i)
 writeln("Total cost: ", strfmt(getsol(totcost),5,2), " (orig: ", TOTCOST, ") discount:",
         strfmt((TOTCOST-totcost.sol)/TOTCOST * 100,5,2), "%" )
 forall(i in BOOKS) BDay(i):=round(getsol(sum(j in DAYS) j*ifbuy(i,j)))
 forall(i in BOOKS)
   writeln("Book ", i, " bought on day ", BDay(i), " at ",
           strfmt(COST(i)*(1-if(BDay(i)>1, DISC*total(BDay(i)-1).sol,0)),5,2),
           " (orig: ", strfmt(COST(i),5,2), ")" )
 
end-model

Back to examples browserPrevious exampleNext example