Basic MIP tasks: binary variables; logic constraints


Type:	Knapsack
Rating:	1 (simple)
Description:	We wish to choose among items of different value and weight those that result in the maximum total value for a given weight limit. small MIP problem alternative use of number-valued ranges and sets of strings for indexing variables and data definition of binary variables forall statement formulation of logic constraints using indicators or advmod functionality (burglarl.mos)
File(s):	burglar.mos, burglari.mos, burglarl.mos

burglar.mos

(!*******************************************************
  * Mosel Example Problems                              *
  * ======================                              *
  *                                                     *
  * file burglar.mos                                    *
  * ````````````````                                    *
  * Example for the use of the Mosel language           *
  * (Burglar problem)                                   *
  *                                                     *
  * (c) 2008 Fair Isaac Corporation                     *
  *     author: S. Heipcke, 2001                        *
  *******************************************************!)

model Burglar                       ! Start a new model

uses "mmxprs"                       ! Load the optimizer library

declarations
 Items=1..8                         ! Index range for items

 VALUE: array(Items) of real        ! Value of items
 WEIGHT: array(Items) of real       ! Weight of items
 WTMAX=102                          ! Max weight allowed for haul

 x: array(Items) of mpvar           ! 1 if we take item i; 0 otherwise
end-declarations

!   Item:   1   2   3   4   5   6   7   8
 VALUE :: [15,100, 90, 60, 40, 15, 10,  1]
 WEIGHT:: [ 2, 20, 20, 30, 40, 30, 60, 10]
 
 MaxVal:= sum(i in Items) VALUE(i)*x(i)  ! Objective: maximize total value

                                    ! Weight restriction
 WtMax:= sum(i in Items) WEIGHT(i)*x(i) <= WTMAX 

 forall(i in Items) x(i) is_binary  ! All x are 0/1
  
 maximize(MaxVal)                   ! Solve the MIP-problem

                                    ! Print out the solution
 writeln("Solution:\n Objective: ", getobjval)
 forall(i in Items)  writeln(" x(", i, "): ", x(i).sol)

end-model

burglari.mos

(!*******************************************************
  * Mosel Example Problems                              *
  * ======================                              *
  *                                                     *
  * file burglari.mos                                   *
  * `````````````````                                   *
  * Example for the use of the Mosel language           *
  * (Burglar problem)                                   *
  *                                                     *
  * (c) 2008 Fair Isaac Corporation                     *
  *     author: S. Heipcke, 2001                        *
  *******************************************************!)

model "Burglar (index set)"         ! Start a new model

uses "mmxprs"                       ! Load the optimizer library

declarations
 Items={"camera", "necklace", "vase", "picture", "tv", "video",
        "chest", "brick"}           ! Index set for items

 VALUE: array(Items) of real        ! Value of items
 WEIGHT: array(Items) of real       ! Weight of items
 WTMAX=102                          ! Max weight allowed for haul

 x: array(Items) of mpvar           ! 1 if we take item i; 0 otherwise
end-declarations

 VALUE("camera")  := 15;  WEIGHT("camera")  :=  2
 VALUE("necklace"):=100;  WEIGHT("necklace"):= 20
 VALUE("vase")    := 90;  WEIGHT("vase")    := 20
 VALUE("picture") := 60;  WEIGHT("picture") := 30
 VALUE("tv")      := 40;  WEIGHT("tv")      := 40
 VALUE("video")   := 15;  WEIGHT("video")   := 30
 VALUE("chest")   := 10;  WEIGHT("chest")   := 60
 VALUE("brick")   :=  1;  WEIGHT("brick")   := 10
 
 MaxVal:= sum(i in Items) VALUE(i)*x(i)  ! Objective: maximize total value

                                    ! Weight restriction
 WtMax:= sum(i in Items) WEIGHT(i)*x(i) <= WTMAX 

 forall(i in Items) x(i) is_binary  ! All x are 0/1
  
 maximize(MaxVal)                   ! Solve the MIP-problem

                                    ! Print out the solution
 writeln("Solution:\n Objective: ", getobjval)
 forall(i in Items)  writeln(" x(", i, "): ", x(i).sol)

end-model

burglarl.mos

(!*******************************************************
  * Mosel Example Problems                              *
  * ======================                              *
  *                                                     *
  * file burglarl.mos                                   *
  * `````````````````                                   *
  * Example for the use of the Mosel language           *
  * (Burglar problem)                                   *
  * -- Formulation of logical constraints --            *
  *                                                     *
  * (c) 2009 Fair Isaac Corporation                     *
  *     author: S. Heipcke, June 2009                   *
  *******************************************************!)

model "Burglar (logic constraints)"

uses "advmod"                       ! Use logic constraints package

declarations
 Items={"camera", "necklace", "vase", "picture", "tv", "video",
        "chest", "brick"}           ! Index set for items

 VALUE: array(Items) of real        ! Value of items
 WEIGHT: array(Items) of real       ! Weight of items
 WTMAX=102                          ! Max weight allowed for haul

 x: array(Items) of mpvar           ! 1 if we take item i; 0 otherwise
end-declarations

 VALUE("camera")  := 15;  WEIGHT("camera")  :=  2
 VALUE("necklace"):=100;  WEIGHT("necklace"):= 20
 VALUE("vase")    := 90;  WEIGHT("vase")    := 20
 VALUE("picture") := 60;  WEIGHT("picture") := 30
 VALUE("tv")      := 40;  WEIGHT("tv")      := 40
 VALUE("video")   := 15;  WEIGHT("video")   := 30
 VALUE("chest")   := 10;  WEIGHT("chest")   := 60
 VALUE("brick")   :=  1;  WEIGHT("brick")   := 10
 
 MaxVal:= sum(i in Items) VALUE(i)*x(i)  ! Objective: maximize total value

                                    ! Weight restriction
 WtMax:= sum(i in Items) WEIGHT(i)*x(i) <= WTMAX 

 forall(i in Items) x(i) is_binary  ! All x are 0/1


! *** Logic constraint:
! *** Either take "vase" and "picture" or "tv" and "video" (but not both pairs).

! * Values within each pair are the same
 Log1:= x("vase") = x("picture")
 Log2:= x("tv") = x("video")

! * Choose exactly one pair (uncomment one of the 3 formulations A, B, or C)

! (A) MIP formulation  
!  Log3:= x("tv") = 1 - x("vase")

! (B) Logic constraint
  Log3:= xor(x("vase")+x("picture")>=2, x("tv")+x("video")>=2) 

! (C) Alternative logic formulation (does not create additional binaries)
(!
  Log3a:= indicator(1, x("vase"), x("tv")+x("video") <= 0)
                                    ! x("vase")=1 -> x("tv")+x("video")=0
  Log3b:= indicator(-1, x("vase"), x("tv")+x("video") >= 2)
                                    ! x("vase")=0 -> x("tv")+x("video")=2
!)

  
 maximize(MaxVal)                   ! Solve the MIP-problem

                                    ! Print out the solution
 writeln("Solution:\n Objective: ", getobjval)
 forall(i in Items)  writeln(" x(", i, "): ", x(i).sol)

end-model

© 2001-2019 Fair Isaac Corporation. All rights reserved. This documentation is the property of Fair Isaac Corporation (“FICO”). Receipt or possession of this documentation does not convey rights to disclose, reproduce, make derivative works, use, or allow others to use it except solely for internal evaluation purposes to determine whether to purchase a license to the software described in this documentation, or as otherwise set forth in a written software license agreement between you and FICO (or a FICO affiliate). Use of this documentation and the software described in it must conform strictly to the foregoing permitted uses, and no other use is permitted.

Contents

Index

Glossary

Search Results

Basic MIP tasks: binary variables; logic constraints