org.jorlib.alg.knapsack.separation

Class LiftedCoverInequalitySeparator

java.lang.Object

org.jorlib.alg.knapsack.separation.LiftedCoverInequalitySeparator

public class LiftedCoverInequalitySeparator
extends Object

This class calculates both Lifted and Minimal Cover inequalities for binary knapsack constraints.

The algorithms used to separate violated inequalities are provided in:
Nemhauser, G.L., Wolsey, L.A., Integer and combinatorial optimization. 1999, John Wiley & Sons Given a knapsack constraint: \sum_i a_i x_i <= b where x_i are binary variables, b a positive integer and a_i integer coefficients. Let N be the set of variables in the knapsack constraint. For a given assignment of values to the variables, this class computes two types of violated cover inequalities:

1. Minimal covers: \sum_{j\in C} \leq |C|-1, where C\subseteq N, \sum_{j\in C} a_i >b
2. Lifted covers: \sum_{j\in N\setminus C} \alpha_jx_j + \sum_{j\in C2} \gamma_jx_j + \sum_{j\in C1} x_j \leq |C1|-1+\sum_{j\in C2}\gamma_j, where C1 \cap C2= \emptyset, C1 \cup C2= C, C a minimal cover as defined above.

NOTE: Separating violated Lifted Cover Inequalities is NP-hard. Hence we rely on lifting and a separation heuristic. First we attempt to find a violated Lifted Cover inequality with C2=\emptyset. If we can't find such an inequality, we set C2 to: C2={k}, k=arg max_{j\in C}a_j variableValue[j], and C1=C\setminus C2, and retry.

Note: The precision of the calculations are accurate up to 0.000001.

Since:

April 8, 2015

Author:

Joris Kinable

Field Summary

Fields

Modifier and Type	Field and Description
static double	PRECISION Rounding precision

Constructor Summary

Constructors

Constructor and Description
LiftedCoverInequalitySeparator(KnapsackAlgorithm knapsackAlgorithm) Creates a new separator

Method Summary

Modifier and Type	Method and Description
boolean	coverInequalityExists() Indicates whether a cover inequality exists, i.e returns whether \sum_i a_i > b.
int[]	getLiftedCoverCoefficients() Returns an array of alpha coefficients of the lifted cover inequality
double	getLiftedCoverLHS() Returns evaluation of the LHS of the cover.
int	getLiftedCoverRHS() Returns the RHS of the lifted cover inequality
Set<Integer>	getMinimalCover() Returns C: the variables that are in the minimal cover
double	getMinimalCoverLHS() Returns evaluation of the LHS of the cover.
boolean[]	getMinimalCoverMask() Returns an boolean array indicating which variables belong to the minimal cover inequality C: x_i <= |C|-1}, i.e.
int	getMinimalCoverRHS() returns the RHS of the minimal cover inequality
boolean	isLiftedCoverViolated() Returns true if the lifted cover inequality is violated
boolean	isMinimalCoverViolated() Returns true if the cover inequality x_i <= |C|-1} is violated
void	separateLiftedCover(int nrVars, int[] knapsackCoefficients, int b, double[] variableValues, boolean performDownLifting) Given a knapsack constraint: \sum_{i=0}^n a_ix_i \leq b This method separates Lifted Cover Inequalities, i.e it will search for a valid lifted cover inequality \sum_{j\in N\setminus C} \alpha_jx_j + \sum_{j\in C2} \gamma_jx_j + \sum_{j\in C1} x_j \leq |C1|-1+\sum_{j\in C2}\gamma_j which is violated by the current variable values, where C1 \cap C2= \emptyset, C1 \cup C2= C, C a minimal cover
void	separateMinimalCover(int nrVars, int[] knapsackCoefficients, int b, double[] variableValues) Given a knapsack constraint: \sum_{i=0}^n a_ix_i \leq b This method separates minimal Cover Inequalities, i.e it will search for a valid cover \sum_{i\in C} x_i \leq |C|-1 which is violated by the current variable values

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

PRECISION

public static final double PRECISION

Rounding precision

See Also:

Constant Field Values

Constructor Detail

LiftedCoverInequalitySeparator

public LiftedCoverInequalitySeparator(KnapsackAlgorithm knapsackAlgorithm)

Creates a new separator

Parameters:

knapsackAlgorithm - This separator requires an algorithm to solve knapsack problems

Method Detail

separateMinimalCover

public void separateMinimalCover(int nrVars,
                                 int[] knapsackCoefficients,
                                 int b,
                                 double[] variableValues)

Given a knapsack constraint: \sum_{i=0}^n a_ix_i \leq b This method separates minimal Cover Inequalities, i.e it will search for a valid cover \sum_{i\in C} x_i \leq |C|-1 which is violated by the current variable values

Parameters:

nrVars - number of variables in the knapsack constraint

knapsackCoefficients - a_i

b - right hand side of the knapsack constraint

variableValues - values of the x_i variables

separateLiftedCover

public void separateLiftedCover(int nrVars,
                                int[] knapsackCoefficients,
                                int b,
                                double[] variableValues,
                                boolean performDownLifting)

Given a knapsack constraint: \sum_{i=0}^n a_ix_i \leq b This method separates Lifted Cover Inequalities, i.e it will search for a valid lifted cover inequality \sum_{j\in N\setminus C} \alpha_jx_j + \sum_{j\in C2} \gamma_jx_j + \sum_{j\in C1} x_j \leq |C1|-1+\sum_{j\in C2}\gamma_j which is violated by the current variable values, where C1 \cap C2= \emptyset, C1 \cup C2= C, C a minimal cover

Parameters:

nrVars - number of variables in the knapsack constraint

knapsackCoefficients - a_i

b - right hand side of the knapsack constraint

variableValues - values of the x_i variables

performDownLifting - When set to true, additional effort is performed to find a violated Lifted Cover AbstractInequality. When this value is false, C2 will be an empty set.

coverInequalityExists

public boolean coverInequalityExists()

Indicates whether a cover inequality exists, i.e returns whether \sum_i a_i > b. You should NOT ask for a minimal or lifted cover if this function returns false!

Returns:

Indicates whether a cover inequality exists, i.e returns whether \sum_i a_i > b. You should NOT ask for a minimal or lifted cover if this function returns false!

getMinimalCover

public Set<Integer> getMinimalCover()

Returns C: the variables that are in the minimal cover

Returns:

Returns C: the variables that are in the minimal cover

getMinimalCoverMask

public boolean[] getMinimalCoverMask()

Returns an boolean array indicating which variables belong to the minimal cover inequality C: x_i <= |C|-1}, i.e. minimalCover[i] is true if variable i is in the cover.

Returns:

an boolean array indicating which variables belong to the minimal cover inequality C: x_i <= |C|-1}, i.e. minimalCover[i] is true if variable i is in the cover.

isMinimalCoverViolated

public boolean isMinimalCoverViolated()

Returns true if the cover inequality x_i <= |C|-1} is violated

Returns:

Returns true if the cover inequality x_i <= |C|-1} is violated

getMinimalCoverLHS

public double getMinimalCoverLHS()

Returns evaluation of the LHS of the cover. If the cover is violated, than LHS>RHS

Returns:

evaluation of the LHS of the cover. If the cover is violated, than LHS>RHS

getMinimalCoverRHS

public int getMinimalCoverRHS()

returns the RHS of the minimal cover inequality

Returns:

returns the RHS of the minimal cover inequality

getLiftedCoverCoefficients

public int[] getLiftedCoverCoefficients()

Returns an array of alpha coefficients of the lifted cover inequality

Returns:

an array of alpha coefficients of the lifted cover inequality

getLiftedCoverLHS

public double getLiftedCoverLHS()

Returns evaluation of the LHS of the cover. If the cover is violated, than LHS>RHS

Returns:

evaluation of the LHS of the cover. If the cover is violated, than LHS>RHS

getLiftedCoverRHS

public int getLiftedCoverRHS()

Returns the RHS of the lifted cover inequality

Returns:

the RHS of the lifted cover inequality

isLiftedCoverViolated

public boolean isLiftedCoverViolated()

Returns true if the lifted cover inequality is violated

Returns:

true if the lifted cover inequality is violated