Introductory Example

This is a very simple optimization problem originally described here:

300 kids need to travel to the London zoo. The school may rent 40 seats and 30 seats buses for 500£ and 400£. How many buses of each type should they rent to minimize the total cost?

The class ProblemZoo shows how to define and solve this problem with Java Solver:

This class is inherited from JavaSolver. The method “define()” uses embedded object csp that represents an instance of a constraint satisfaction problem (CSP) specified by the JSR-331 standard “Constraint Programming API”. First, it creates 2 integer constraint variables numberOf30Buses and numberOf40Buses defined from 0 to 30 (because we don’t need more than 30 buses of any type to sit 300 kids).  Here we used the csp’s method variable(name,min,max) that creates one constrained integer variable of the type Var.

The array seats contains numbers of seats in each bus type. Then we placed both variables in the array vars. It allowed us to specify another variable totalNumberOfSeats of the type Var as a scalar product of the arrays seats and vars. Then we stated that the total number of seats in all buses should be at least 300 by posting this constraint:, ” >=“,  300)

The array costs contains costs for each bus type. Next 2 lines specify the optimization objective totalCost that is a scalar product of the arrays costs and vars.

That’s it – our optimization problem is defined. The method main creates an instance of the class ProblemZoo and calls its define() and minimize() methods. The latest method will minimize the specified optimization objective totalCost. Here are the execution results:

As you can see, by default Java Solver used an open source constraint solver “Constrainer”. We can switch to a linear solver, e.g. to another open source solver “SCIP”. To do that we just need to change the selected SOLVER in the batch file “runZoo.bat”:

As you can see, we commented out CONSTRAINER, and set SOLVER=SCIP. Here are the new execution results:

There are many other CP and LP solvers (open source and commercial) which can be utilized by Java Solver.  Constraint solvers can represent almost any problem while linear solvers are limited to linear constraints. Linear solvers usually can find optimal solutions for problems of very large size when constraint solvers stop short. So, sometimes you can split your problem in several sub-problems and solve them using different solvers.