BigObject MixedIntegerLinearProgram<Scalar>

from application polytope

A mixed integer linear program specified by a linear or abstract objective function

Type Parameters:

Scalar: numeric type of variables and objective function

INTEGER_VARIABLES

Set of integers that indicate which entries of the solution should be integral. If no value is specified, all entries are required to be integral. If all entries should be rational, please use an LinearProgram instead.

Type:

Set<Int>

Example:

The following defines a MixedIntegerLinearProgram together with a linear objective on a rational line segment embedded in two-dimensional space.

 > $l = new Polytope(INEQUALITIES=>[[0,1,0],[3/2,-1,0],[1,0,0]],EQUATIONS=>[[0,0,1]]);
 > $obj = new Vector([0,1,0]);
 > $intvar = new Set<Int>([0,1,2]);
 > $milp = $l->MILP(LINEAR_OBJECTIVE=>$obj, INTEGER_VARIABLES=>$intvar);
 > print $milp->INTEGER_VARIABLES;
 {0 1 2}

Example:

Same as the previous example, but we do not require the first coordinate to be integral anymore.

 > $l = new Polytope(INEQUALITIES=>[[0,1,0],[3/2,-1,0],[1,0,0]],EQUATIONS=>[[0,0,1]]);
 > $obj = new Vector([0,1,0]);
 > $intvar = new Set<Int>([0,2]);
 > $milp = $l->MILP(LINEAR_OBJECTIVE=>$obj, INTEGER_VARIABLES=>$intvar);
 > print $milp->INTEGER_VARIABLES;
 {0 2}

LINEAR_OBJECTIVE

Linear objective funtion. In d-space a linear objective function is given by a (d+1)-vector. The first coordinate specifies a constant that is added to the resulting value.

Type:

Vector<Scalar>

Example:

The following defines a MixedIntegerLinearProgram together with a linear objective on a rational line segment embedded in two-dimensional space.

 > $l = new Polytope(INEQUALITIES=>[[0,1,0],[3/2,-1,0],[1,0,0]],EQUATIONS=>[[0,0,1]]);
 > $obj = new Vector([0,-1,0]);
 > $intvar = new Set<Int>([0,1,2]);
 > $milp = $l->MILP(LINEAR_OBJECTIVE=>$obj, INTEGER_VARIABLES=>$intvar);
 > print $milp->LINEAR_OBJECTIVE;
 0 -1 0

MAXIMAL_SOLUTION

Coordinates of a (possibly not unique) affine vertex at which the maximum of the objective function is attained.

Type:

Vector<Scalar>

Example:

The following defines a MixedIntegerLinearProgram together with a linear objective for the centered square with side length 2 and asks for a maximal solution:

 > $c = new Vector([0, 1, -1/2]);
 > $p = cube(2);
 > $p->MILP(LINEAR_OBJECTIVE=>$c);
 > print $p->MILP->MAXIMAL_SOLUTION;
 1 1 -1

Example:

The following defines a MixedIntegerLinearProgram together with a linear objective on a rational line segment embedded in two-dimensional space. Note that the maximal solution is not a vertex/endpoint of the line segment.

 > $l = new Polytope(INEQUALITIES=>[[0,1,0],[3/2,-1,0],[1,0,0]],EQUATIONS=>[[0,0,1]]);
 > $obj = new Vector([0,1,0]);
 > $intvar = new Set<Int>([0,1,2]);
 > $milp = $l->MILP(LINEAR_OBJECTIVE=>$obj, INTEGER_VARIABLES=>$intvar);
 > print $milp->MAXIMAL_SOLUTION;
 1 1 0

Example:

Same as the previous example, but we do not require the first coordinate to be integral anymore. Now the maximal solution is an endpoint of the line segment.

 > $l = new Polytope(INEQUALITIES=>[[0,1,0],[3/2,-1,0],[1,0,0]],EQUATIONS=>[[0,0,1]]);
 > $obj = new Vector([0,1,0]);
 > $intvar = new Set<Int>([0,2]);
 > $milp = $l->MILP(LINEAR_OBJECTIVE=>$obj, INTEGER_VARIABLES=>$intvar);
 > print $milp->MAXIMAL_SOLUTION;
 1 3/2 0

MAXIMAL_VALUE

Maximum value the objective funtion takes under the restriction given by INTEGER_VARIABLES.

Type:

Scalar

Example:

The following defines a MixedIntegerLinearProgram together with a linear objective on a rational line segment embedded in two-dimensional space. Note that the maximal value is integral and not the same as the value of the objective function on any of the vertices.

 > $l = new Polytope(INEQUALITIES=>[[0,1,0],[3/2,-1,0],[1,0,0]],EQUATIONS=>[[0,0,1]]);
 > $obj = new Vector([0,1,0]);
 > $intvar = new Set<Int>([0,1,2]);
 > $milp = $l->MILP(LINEAR_OBJECTIVE=>$obj, INTEGER_VARIABLES=>$intvar);
 > print $milp->MAXIMAL_VALUE;
 1

Example:

Same as the previous example, but we do not require the first coordinate to be integral anymore.

 > $l = new Polytope(INEQUALITIES=>[[0,1,0],[3/2,-1,0],[1,0,0]],EQUATIONS=>[[0,0,1]]);
 > $obj = new Vector([0,1,0]);
 > $intvar = new Set<Int>([0,2]);
 > $milp = $l->MILP(LINEAR_OBJECTIVE=>$obj, INTEGER_VARIABLES=>$intvar);
 > print $milp->MAXIMAL_VALUE;
 3/2

MINIMAL_SOLUTION

Similar to MAXIMAL_SOLUTION

Type:

Vector<Scalar>

Example:

The following defines a MixedIntegerLinearProgram together with a linear objective for the centered square with side length 2 and asks for a maximal solution:

 > $c = new Vector([0, 1, -1/2]);
 > $p = cube(2);
 > $p->MILP(LINEAR_OBJECTIVE=>$c);
 > print $p->MILP->MINIMAL_SOLUTION;
 1 -1 1

MINIMAL_VALUE

Similar to MAXIMAL_VALUE.

Type:

Scalar

Example:

The following defines a MixedIntegerLinearProgram together with a linear objective on a rational line segment embedded in two-dimensional space. Note that the maximal value is integral and not the same as the value of the objective function on any of the vertices.

 > $l = new Polytope(INEQUALITIES=>[[0,1,0],[3/2,-1,0],[1,0,0]],EQUATIONS=>[[0,0,1]]);
 > $obj = new Vector([0,-1,0]);
 > $intvar = new Set<Int>([0,1,2]);
 > $milp = $l->MILP(LINEAR_OBJECTIVE=>$obj, INTEGER_VARIABLES=>$intvar);
 > print $milp->MINIMAL_VALUE;
 -1

Example:

Same as the previous example, but we do not require the first coordinate to be integral anymore.

 > $l = new Polytope(INEQUALITIES=>[[0,1,0],[3/2,-1,0],[1,0,0]],EQUATIONS=>[[0,0,1]]);
 > $obj = new Vector([0,-1,0]);
 > $intvar = new Set<Int>([0,2]);
 > $milp = $l->MILP(LINEAR_OBJECTIVE=>$obj, INTEGER_VARIABLES=>$intvar);
 > print $milp->MINIMAL_VALUE;
 -3/2