scalation
API
Generated with
scalation/scalation/scalation.optimization/scalation.optimization.linear_opt

scalation.optimization.linear_opt

package scalation.optimization.linear_opt

Members list

Type members

Classlikes

class CheckLP(a: MatrixD, b: VectorD, c: VectorD)

The CheckLP class checks the solution to Linear Programming (LP) problems. Given a constraint matrix 'a', limit/RHS vector 'b' and cost vector 'c', determine if the values for the solution/decision vector 'x' minimizes the objective function 'f(x)', while satisfying all of the constraints, i.e.,

The CheckLP class checks the solution to Linear Programming (LP) problems. Given a constraint matrix 'a', limit/RHS vector 'b' and cost vector 'c', determine if the values for the solution/decision vector 'x' minimizes the objective function 'f(x)', while satisfying all of the constraints, i.e.,

minimize f(x) = c x subject to a x <= b, x >= 0

Check the feasibility and optimality of the solution.

Value parameters

a

the M-by-N constraint matrix

b

the M-length limit/RHS vector (make b_i negative for ">=" constraint => surplus)

c

the N-length cost vector

Attributes

Supertypes
class Object
trait Matchable
class Any
class IntegerLP(a: MatrixD, b: VectorD, c: VectorD, excl: Set[Int])

The IntegerLP class solves Integer Linear Programming (ILP) and Mixed Integer Linear Programming (MILP) problems recursively using the Simplex algorithm. First, an LP problem is solved. If the optimal solution vector x is entirely integer valued, the ILP is solved. If not, pick the first x_j that is not integer valued. Define two new LP problems which bound x_j to the integer below and above, respectively. Branch by solving each of these LP problems in turn. Prune by not exploring branches less optimal than the currently best integer solution. This technique is referred to as Branch and Bound. An exclusion set may be optionally provided for MILP problems. FIX: Use the Dual Simplex Algorithm for better performance.

The IntegerLP class solves Integer Linear Programming (ILP) and Mixed Integer Linear Programming (MILP) problems recursively using the Simplex algorithm. First, an LP problem is solved. If the optimal solution vector x is entirely integer valued, the ILP is solved. If not, pick the first x_j that is not integer valued. Define two new LP problems which bound x_j to the integer below and above, respectively. Branch by solving each of these LP problems in turn. Prune by not exploring branches less optimal than the currently best integer solution. This technique is referred to as Branch and Bound. An exclusion set may be optionally provided for MILP problems. FIX: Use the Dual Simplex Algorithm for better performance.

Given a constraint matrix a, limit/RHS vector b and cost vector c, find values for the solution/decision vector x that minimize the objective function f(x), while satisfying all of the constraints, i.e.,

minimize f(x) = c x subject to a x <= b, x >= 0, some x_i must be integer valued

Make b_i negative to indicate a >= constraint.

Value parameters

a

the M-by-N constraint matrix

b

the M-length limit/RHS vector

c

the N-length cost vector

excl

the set of variables to be excluded from the integer requirement

Attributes

Supertypes
class Object
trait Matchable
class Any
trait MinimizerLP

The MinimizerLP trait sets the pattern for optimization algorithms for solving Linear Programming (LP) problems of the form:

The MinimizerLP trait sets the pattern for optimization algorithms for solving Linear Programming (LP) problems of the form:

minimize c x subject to a x <= b, x >= 0

where a is the constraint matrix b is the limit/RHS vector c is the cost vector

Classes mixing in this trait must implement an objective function objF an iterative method (solve) that searches for improved solutions x-vectors with lower objective function values.

Attributes

Supertypes
class Object
trait Matchable
class Any
Known subtypes
class Simplex2P
class Simplex2P(a: MatrixD, b: VectorD, c: VectorD) extends MinimizerLP

The Simplex2P class solves Linear Programming (LP) problems using a tableau based Simplex Algorithm. Given a constraint matrix a, limit/RHS vector b and cost vector c, find values for the solution/decision vector x that minimize the objective function f(x), while satisfying all of the constraints, i.e.,

The Simplex2P class solves Linear Programming (LP) problems using a tableau based Simplex Algorithm. Given a constraint matrix a, limit/RHS vector b and cost vector c, find values for the solution/decision vector x that minimize the objective function f(x), while satisfying all of the constraints, i.e.,

minimize f(x) = c x subject to a x <= b, x >= 0

In case of a_i x >= b_i, use -b_i as an indicator of a ">=" constraint. The program will flip such negative b_i back to positive as well as use a surplus and artificial variable instead of the usual slack variable, i.e., a_i x <= b_i => a_i x + s_i = b_i // use slack variable s_i with coefficient 1 a_i x >= b_i => a_i x + s_i = b_i // use surplus variable s_i with coefficient -1 For each '>=' constraint, an artificial variable is introduced and put into the initial basis. These artificial variables must be removed from the basis during Phase I of the Two-Phase Simplex Algorithm. After this, or if there are no artificial variables, Phase II is used to find an optimal value for x and the optimum value for f.

Creates an MM-by-nn simplex tableau with -- [0..M-1, 0..N-1] = a (constraint matrix) -- [0..M-1, N..M+N-1] = s (slack/surplus variable matrix) -- [0..M-1, M+N..nn-2] = r (artificial variable matrix) -- [0..M-1, nn-1] = b (limit/RHS vector) -- [M, 0..nn-2] = c (cost vector)

Value parameters

a

the M-by-N constraint matrix

b

the M-length limit/RHS vector (input b_i negative for surplus)

c

the N-length cost vector

Attributes

Supertypes
trait MinimizerLP
class Object
trait Matchable
class Any
final class integerLPTest

Attributes

Supertypes
class Object
trait Matchable
class Any
final class simplex2PTest

Attributes

Supertypes
class Object
trait Matchable
class Any

Value members

Concrete methods

def integerLPTest(): Unit

The IntegerLPTest main function is used to test the IntegerLP class. real solution x = (.8, 1.6), f = 8.8 integer solution x = (2, 1), f = 10

The IntegerLPTest main function is used to test the IntegerLP class. real solution x = (.8, 1.6), f = 8.8 integer solution x = (2, 1), f = 10

Attributes

See also

Linear Programming and Network Flows, Example 6.14

runMain scalation.optimization.linear_opt.integerLPTest

def simplex2PTest(): Unit

The simplex2PTest main function is used to test the Simplex2P class.

The simplex2PTest main function is used to test the Simplex2P class.

runMain scalation.optimization.linear_opt.simplex2PTest

Attributes

Generated with