1. Pierre Schaus
  2. OscaR

Wiki

Clone wiki

OscaR / LP

Linear Programming (need to be updated)

  • Find all the linear programming examples here.
  • OscaR does not implement its own LP solver but a high level scala modeling layer. Your model can be solved with high quality commercial or open source solvers namely gurobi, glpk, lp_solve (the solver is just one parameter of OscaR model).
  • We refer to the install section to set-up Eclipse and OscaR to use external linear solvers.

Hands-On

Whatever you'll do, you just need to import three packages :

import oscar.linprog.modeling._
import oscar.linprog._
import oscar.algebra._

object Diet {
   def main(args: Array[String]) {
   }
}

You can now create a solver and create some variables in this solver:

import oscar.linprog.modeling._
import oscar.linprog._
import oscar.algebra._

object MyLPProblem {
   def main(args: Array[String]) {
      val lp = LPSolver() 
      val x0 = LPVar(lp,"x0",0,40) // can take value in continuous interval [0,40]
      val x1 = LPVar(lp,"x1",0, 1000) 
      val x2 = LPVar(lp,"x2",0 ,17) 
      val x3 = LPVar(lp,"x3",2,3)	 
	   
      lp.maximize(x0+2*x1+3*x2+x3) subjectTo {
	  lp.add(-1*x0 + x1 + x2 + 10*x3 <= 20)
 	  lp.add(x0 - 3.0*x1 + x2 <= 30)
 	  lp.add(x1 - 3.5*x3 == 0 )
      }
      println("objective"+lp.getObjectiveValue()) 
      println(x1.getValue())
   }
}

Alternatively, you can mix continuous variables with integer variables using a MIP solver (rather than an LP solver).

import oscar.linprog.modeling._
import oscar.linprog._
import oscar.algebra._

object MyMIPProblem {
   def main(args: Array[String]) {
      val mip = MIPSolver()
      val x0 = MIPVar(mip,"x0",0,40)
      val x1 = MIPVar(mip,"x1",0 to 1000) // can take integer value in range[0 .. 1000]
      val x2 = MIPVar(mip,"x2",0 until 18)// can take integer value in range[0 .. 17] 
      val x3 = MIPVar(mip,"x3",2,3)	 
	   
	   
      mip.maximize(x0+2*x1+3*x2+x3) subjectTo {
 	  mip.add(-1*x0 + x1 + x2 + 10*x3 <= 20)
 	  mip.add(x0 - 3.0*x1 + x2 <= 30)
 	  mip.add(x1 - 3.5*x3 == 0 )
      }
      println("objective"+mip.getObjectiveValue()) 
      println(x1.getValue())
   }
}

Even if all the constraints are added, it is important to use the subjectTo{} function that executes the block of constraints.

Writing large linear expressions and linear constraints

OscaR has some facilities for writing large linear expressions. Here is an example of making a summation over an array of variables:

val x = Array.fill(10)(MIPVarInt(mip,0 to 100)
cp.add(sum(x) == 5)
cp.add(sum(0 to x.size)(i => x(i)) == 5)

This function also works for a larger number of dimensions:

val x = Array.fill(10,10)(MIPVarInt(mip,0 to 100)
cp.add(sum(0 to 9, 0 to 9)((i,j) => x(i)(j) == 5)

Note that the summation indexes can be any Iterable object. Have a look at the doc/api here to find all the different ways to create linear expressions with sum.

Integer vs Continuous Variables

OscaR recognizes that a MIPVar must be continuous or integer automatically.

  • Continuous Variable: If you specify the two bounds with lb,ub then the allowed values are in the continuous interval [lb,ub]. For instance MIPVar(mip,"x0",0,40).
  • Integer Variable: If you give it a Scala range (using to or until) you create an integer variable that can take values in that range. For instance MIPVar(mip,"x2",0 until 18).

Retrieve the solution and get status of the solver

To retrieve the values of the variables:

x.getValue() // gives you Double
x.value // gives you an Option[Double]

To retrieve the value of the objective you can do

mip.getObjectiveValue() // gives you a Double
mip.objectiveValue() // gives you an Option[Double]

Alternatively you can store the objective as a symbolic linear expression type (LinearExpression) and get its value later:

val objective = x0+2*x1+3*x2+x3
mip.maximize(objective) subjectTo {
 // ... some constraints ...
}
objective.value // gives you Some[Double]

Get the outcome of the Solver

A MIP/LP solver can finish well or not so well. You can check its status with

mip.status

It gives you a value from this enumeration (names are quite explicit):

#scala
object LPStatus extends Enumeration {
    val NOT_SOLVED = Value("not solved yet")
    val OPTIMAL = Value("optimal")
    val SUBOPTIMAL = Value("suboptimal")
    val UNBOUNDED = Value("unbounded")
    val INFEASIBLE = Value("infeasible")
}

Change the Solver

OscaR supports lp_solve, glpk, and gurobi (the latter two are only available on dev branch and you must add the jar files yourself since we cannot distribute them with OscaR).

You can specify which solver you want to use in the constructor of the solver. For instance:

val mip = MIPSolver(LPSolverLib.lp_solve) // default
val mip = MIPSolver(LPSolverLib.glpk)
val mip = MIPSolver(LPSolverLib.gurobi)

The default solver is lp_solve for MIP and LP.

Releasing the memory of the Solver

Because OscaR relies on C/C++ libraries for the linear programming solving the memory cannot be released automatically. So it is always wise to release the memory of the internal MIP/LP solver when you don't need it anymore:

mip.release()

Updated