#include <entering_variable.h>

Public Member Functions
	EnteringVariable (const VariablesInfo &variables_info, absl::BitGenRef random, ReducedCosts *reduced_costs)
	Takes references to the linear program data we need.

	EnteringVariable (const EnteringVariable &)=delete
	This type is neither copyable nor movable.

EnteringVariable &	operator= (const EnteringVariable &)=delete

ABSL_MUST_USE_RESULT Status	DualChooseEnteringColumn (bool nothing_to_recompute, const UpdateRow &update_row, Fractional cost_variation, std::vector< ColIndex > bound_flip_candidates, ColIndex entering_col)

ABSL_MUST_USE_RESULT Status	DualPhaseIChooseEnteringColumn (bool nothing_to_recompute, const UpdateRow &update_row, Fractional cost_variation, ColIndex *entering_col)

void	SetParameters (const GlopParameters &parameters)
	Sets the parameters.

std::string	StatString () const
	Stats related functions.

double	DeterministicTime () const

Detailed Description

This class contains the dual algorithms that choose the entering column (i.e. variable) during a dual simplex iteration. That is the dual ratio test.

Terminology:

The entering edge is the edge we are following during a simplex step, and we call "direction" the reverse of this edge restricted to the basic variables, i.e. the right inverse of the entering column.

Definition at line 46 of file entering_variable.h.

Constructor & Destructor Documentation

◆ EnteringVariable() [1/2]

operations_research::glop::EnteringVariable::EnteringVariable	(	const VariablesInfo &	variables_info,
		absl::BitGenRef	random,
		ReducedCosts *	reduced_costs )

Takes references to the linear program data we need.

Definition at line 30 of file entering_variable.cc.

◆ EnteringVariable() [2/2]

operations_research::glop::EnteringVariable::EnteringVariable ( const EnteringVariable & )

delete

This type is neither copyable nor movable.

Member Function Documentation

◆ DeterministicTime()

double operations_research::glop::EnteringVariable::DeterministicTime ( ) const

inline

Deterministic time used by some of the functions of this class.

Todo: (user): Be exhausitive and more precise.

Definition at line 83 of file entering_variable.h.

◆ DualChooseEnteringColumn()

Status operations_research::glop::EnteringVariable::DualChooseEnteringColumn	(	bool	nothing_to_recompute,
		const UpdateRow &	update_row,
		Fractional	cost_variation,
		std::vector< ColIndex > *	bound_flip_candidates,
		ColIndex *	entering_col )

Dual optimization phase (i.e. phase II) ratio test. Returns the index of the entering column given that we want to move along the "update" row vector in the direction given by the sign of cost_variation. Computes the smallest step that keeps the dual feasibility for all the columns.

If everything has the best possible precision currently, we ignore low coefficients. This make sure we will never choose a pivot too small. It however can degrade the dual feasibility of the solution, but we can always fix that later.

Todo: (user): It is unclear if this is a good idea, but the primal simplex have pretty good/stable behavior with a similar logic. Experiment seems to show that this works well with the dual too.

Harris ratio test. See below for more explanation. Here this is used to prune the first pass by not enqueueing ColWithRatio for columns that have a ratio greater than the current harris_ratio.

Like for the primal, we always allow a positive ministep, even if a variable is already infeasible by more than the tolerance.

We will add ratio * coeff to this column with a ratio positive or zero. cost_variation makes sure the leaving variable will be dual-feasible (its update coeff is sign(cost_variation) * 1.0).

In this case, at some point the reduced cost will be positive if not already, and the column will be dual-infeasible.

In this case, at some point the reduced cost will be negative if not already, and the column will be dual-infeasible.

Process the breakpoints in priority order as suggested by Maros in I. Maros, "A generalized dual phase-2 simplex algorithm", European Journal of Operational Research, 149(1):1-16, 2003. We use directly make_heap() to avoid a copy of breakpoints, benchmark shows that it is slightly faster.

Harris ratio test. Since we process the breakpoints by increasing ratio, we do not need a two-pass algorithm as described in the literature. Each time we process a new breakpoint, we update the harris_ratio of all the processed breakpoints. For the first new breakpoint with a ratio greater than the current harris_ratio we know that:

All the unprocessed breakpoints will have a ratio greater too, so they will not contribute to the minimum Harris ratio.
We thus have the actual harris_ratio.
We have processed all breakpoints with a ratio smaller than it.

If the column is boxed, we can just switch its bounds and ignore the breakpoint! But we need to see if the entering row still improve the objective. This is called the bound flipping ratio test in the literature. See for instance: http://www.mpi-inf.mpg.de/conferences/adfocs-03/Slides/Bixby_2.pdf

For each bound flip, cost_variation decreases by |upper_bound - lower_bound| times coeff.

Note: the actual flipping will be done afterwards by MakeBoxedVariableDualFeasible() in revised_simplex.cc.

Todo: (user): We want to maximize both the ratio (objective improvement) and the coeff_magnitude (stable pivot), so we have to make some trade-offs. Investigate alternative strategies.

Update harris_ratio. Note that because we process ratio in order, the harris ratio can only get smaller if the coeff_magnitude is bigger than the one of the best coefficient.

If the dual infeasibility is too high, the harris_ratio can be negative. To avoid this we always allow for a minimum step even if we push some already infeasible variable further away. This is quite important because its helps in the choice of a stable pivot.

Note: the step is not directly used, so it is okay to leave it negative.

Remove the top breakpoint and maintain the heap structure. This is the same as doing a pop() on a priority_queue.

Break the ties randomly.

If best_coeff is small and they are potential bound flips, we can take a smaller step but use a good pivot.

Note: it is okay to leave more candidate than necessary in the returned bound_flip_candidates vector.

Definition at line 38 of file entering_variable.cc.

◆ DualPhaseIChooseEnteringColumn()

Status operations_research::glop::EnteringVariable::DualPhaseIChooseEnteringColumn	(	bool	nothing_to_recompute,
		const UpdateRow &	update_row,
		Fractional	cost_variation,
		ColIndex *	entering_col )

Dual feasibility phase (i.e. phase I) ratio test. Similar to the optimization phase test, but allows a step that increases the infeasibility of an already infeasible column. The step magnitude is the one that minimize the sum of infeasibilities when applied.

List of breakpoints where a variable change from feasibility to infeasibility or the opposite.

Boxed variables shouldn't be in the update position list because they will be dealt with afterwards by MakeBoxedVariableDualFeasible().

Fixed variable shouldn't be in the update position list.

Skip if the coeff is too small to be a numerically stable pivot.

We will add ratio * coeff to this column. cost_variation makes sure the leaving variable will be dual-feasible (its update coeff is sign(cost_variation) * 1.0).

Todo: (user): This is the same in DualChooseEnteringColumn(), remove duplication?

Only proceed if there is a transition, note that if reduced_costs[col] is close to zero, then the variable is counted as dual-feasible.

Continue if the variation goes in the dual-feasible direction.

For an already dual-infeasible variable, we allow to push it until the harris_tolerance. But if it is past that or close to it, we also always enforce a minimum push.

If the two are of the same sign, there is no transition, skip.

We are sure there is a transition, add it to the set of breakpoints.

Process the breakpoints in priority order.

Because of our priority queue, it is easy to choose a sub-optimal step to have a stable pivot. The pivot with the highest magnitude and that reduces the infeasibility the most is chosen.

Select the last breakpoint that still improves the infeasibility and has a numerically stable pivot.

We keep the greatest coeff_magnitude for the same ratio.

If the variable is free, then not only do we loose the infeasibility improvment, we also render it worse if we keep going in the same direction.

Definition at line 245 of file entering_variable.cc.

◆ operator=()

EnteringVariable & operations_research::glop::EnteringVariable::operator= ( const EnteringVariable & )

delete

◆ SetParameters()

void operations_research::glop::EnteringVariable::SetParameters ( const GlopParameters & parameters )

Sets the parameters.

Definition at line 363 of file entering_variable.cc.

◆ StatString()

std::string operations_research::glop::EnteringVariable::StatString ( ) const