lp_data.h

Go to the documentation of this file.

// Copyright 2010-2018 Google LLC
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
 
//
// Storage classes for Linear Programs.
//
// LinearProgram stores the complete data for a Linear Program:
//   - objective coefficients and offset,
//   - cost coefficients,
//   - coefficient matrix,
//   - bounds for each variable,
//   - bounds for each constraint.
 
#ifndef OR_TOOLS_LP_DATA_LP_DATA_H_
#define OR_TOOLS_LP_DATA_LP_DATA_H_
 
#include <algorithm>  // for max
#include <map>
#include <string>  // for string
#include <vector>  // for vector
 
#include "absl/container/flat_hash_map.h"
#include "absl/container/flat_hash_set.h"
#include "ortools/base/hash.h"
#include "ortools/base/int_type.h"
#include "ortools/base/logging.h"  // for CHECK*
#include "ortools/base/macros.h"   // for DISALLOW_COPY_AND_ASSIGN, NULL
#include "ortools/base/strong_vector.h"
#include "ortools/glop/parameters.pb.h"
#include "ortools/lp_data/lp_types.h"
#include "ortools/lp_data/sparse.h"
#include "ortools/util/fp_utils.h"
 
namespace operations_research {
namespace glop {
 
class SparseMatrixScaler;
 
// The LinearProgram class is used to store a linear problem in a form
// accepted by LPSolver.
//
// In addition to the simple setter functions used to create such problems, the
// class also contains a few more advanced modification functions used primarily
// by preprocessors. A client shouldn't need to use them directly.
class LinearProgram {
 public:
  enum class VariableType {
    // The variable can take any value between and including its lower and upper
    // bound.
    CONTINUOUS,
    // The variable must only take integer values.
    INTEGER,
    // The variable is implied integer variable i.e. it was continuous variable
    // in the LP and was detected to take only integer values.
    IMPLIED_INTEGER
  };
 
  LinearProgram();
 
  // Clears, i.e. reset the object to its initial value.
  void Clear();
 
  // Name setter and getter.
  void SetName(const std::string& name) { name_ = name; }
  const std::string& name() const { return name_; }
 
  // Creates a new variable and returns its index.
  // By default, the column bounds will be [0, infinity).
  ColIndex CreateNewVariable();
 
  // Creates a new slack variable and returns its index. Do not use this method
  // to create non-slack variables.
  ColIndex CreateNewSlackVariable(bool is_integer_slack_variable,
                                  Fractional lower_bound,
                                  Fractional upper_bound,
                                  const std::string& name);
 
  // Creates a new constraint and returns its index.
  // By default, the constraint bounds will be [0, 0].
  RowIndex CreateNewConstraint();
 
  // Same as CreateNewVariable() or CreateNewConstraint() but also assign an
  // immutable id to the variable or constraint so they can be retrieved later.
  // By default, the name is also set to this id, but it can be changed later
  // without changing the id.
  //
  // Note that these ids are NOT copied over by the Populate*() functions.
  //
  // TODO(user): Move these and the two corresponding hash_table into a new
  // LinearProgramBuilder class to simplify the code of some functions like
  // DeleteColumns() here and make the behavior on copy clear? or simply remove
  // them as it is almost as easy to maintain a hash_table on the client side.
  ColIndex FindOrCreateVariable(const std::string& variable_id);
  RowIndex FindOrCreateConstraint(const std::string& constraint_id);
 
  // Functions to set the name of a variable or constraint. Note that you
  // won't be able to find those named variables/constraints with
  // FindOrCreate{Variable|Constraint}().
  // TODO(user): Add PopulateIdsFromNames() so names added via
  // Set{Variable|Constraint}Name() can be found.
  void SetVariableName(ColIndex col, absl::string_view name);
  void SetConstraintName(RowIndex row, absl::string_view name);
 
  // Set the type of the variable.
  void SetVariableType(ColIndex col, VariableType type);
 
  // Returns whether the variable at column col is constrained to be integer.
  bool IsVariableInteger(ColIndex col) const;
 
  // Returns whether the variable at column col must take binary values or not.
  bool IsVariableBinary(ColIndex col) const;
 
  // Defines lower and upper bounds for the variable at col. Note that the
  // bounds may be set to +/- infinity. The variable must have been created
  // before or this will crash in non-debug mode.
  void SetVariableBounds(ColIndex col, Fractional lower_bound,
                         Fractional upper_bound);
 
  // Defines lower and upper bounds for the constraint at row. Note that the
  // bounds may be set to +/- infinity. If the constraint wasn't created before,
  // all the rows from the current GetNumberOfRows() to the given row will be
  // created with a range [0,0].
  void SetConstraintBounds(RowIndex row, Fractional lower_bound,
                           Fractional upper_bound);
 
  // Defines the coefficient for col / row.
  void SetCoefficient(RowIndex row, ColIndex col, Fractional value);
 
  // Defines the objective coefficient of column col.
  // It is set to 0.0 by default.
  void SetObjectiveCoefficient(ColIndex col, Fractional value);
 
  // Define the objective offset (0.0 by default) and scaling factor (positive
  // and equal to 1.0 by default). This is mainly used for displaying purpose
  // and the real objective is factor * (objective + offset).
  void SetObjectiveOffset(Fractional objective_offset);
  void SetObjectiveScalingFactor(Fractional objective_scaling_factor);
 
  // Defines the optimization direction. When maximize is true (resp. false),
  // the objective is maximized (resp. minimized). The default is false.
  void SetMaximizationProblem(bool maximize);
 
  // Calls CleanUp() on each columns.
  // That is, removes duplicates, zeros, and orders the coefficients by row.
  void CleanUp();
 
  // Returns true if all the columns are ordered by rows and contain no
  // duplicates or zero entries (i.e. if IsCleanedUp() is true for all columns).
  bool IsCleanedUp() const;
 
  // Functions that return the name of a variable or constraint. If the name is
  // empty, they return a special name that depends on the index.
  std::string GetVariableName(ColIndex col) const;
  std::string GetConstraintName(RowIndex row) const;
 
  // Returns the type of variable.
  VariableType GetVariableType(ColIndex col) const;
 
  // Returns true (resp. false) when the problem is a maximization
  // (resp. minimization) problem.
  bool IsMaximizationProblem() const { return maximize_; }
 
  // Returns the underlying SparseMatrix or its transpose (which may need to be
  // computed).
  const SparseMatrix& GetSparseMatrix() const { return matrix_; }
  const SparseMatrix& GetTransposeSparseMatrix() const;
 
  // Some transformations are better done on the transpose representation. These
  // two functions are here for that. Note that calling the first function and
  // modifying the matrix does not change the result of any function in this
  // class until UseTransposeMatrixAsReference() is called. This is because the
  // transpose matrix is only used by GetTransposeSparseMatrix() and this
  // function will recompute the whole transpose from the matrix. In particular,
  // do not call GetTransposeSparseMatrix() while you modify the matrix returned
  // by GetMutableTransposeSparseMatrix() otherwise all your changes will be
  // lost.
  //
  // IMPORTANT: The matrix dimension cannot change. Otherwise this will cause
  // problems. This is checked in debug mode when calling
  // UseTransposeMatrixAsReference().
  SparseMatrix* GetMutableTransposeSparseMatrix();
  void UseTransposeMatrixAsReference();
 
  // Release the memory used by the transpose matrix.
  void ClearTransposeMatrix();
 
  // Gets the underlying SparseColumn with the given index.
  // This is the same as GetSparseMatrix().column(col);
  const SparseColumn& GetSparseColumn(ColIndex col) const;
 
  // Gets a pointer to the underlying SparseColumn with the given index.
  SparseColumn* GetMutableSparseColumn(ColIndex col);
 
  // Returns the number of variables.
  ColIndex num_variables() const { return matrix_.num_cols(); }
 
  // Returns the number of constraints.
  RowIndex num_constraints() const { return matrix_.num_rows(); }
 
  // Returns the number of entries in the linear program matrix.
  EntryIndex num_entries() const { return matrix_.num_entries(); }
 
  // Return the lower bounds (resp. upper bounds) of constraints as a column
  // vector. Note that the bound values may be +/- infinity.
  const DenseColumn& constraint_lower_bounds() const {
    return constraint_lower_bounds_;
  }
  const DenseColumn& constraint_upper_bounds() const {
    return constraint_upper_bounds_;
  }
 
  // Returns the objective coefficients (or cost) of variables as a row vector.
  const DenseRow& objective_coefficients() const {
    return objective_coefficients_;
  }
 
  // Return the lower bounds (resp. upper bounds) of variables as a row vector.
  // Note that the bound values may be +/- infinity.
  const DenseRow& variable_lower_bounds() const {
    return variable_lower_bounds_;
  }
  const DenseRow& variable_upper_bounds() const {
    return variable_upper_bounds_;
  }
 
  // Returns a row vector of VariableType representing types of variables.
  const StrictITIVector<ColIndex, VariableType> variable_types() const {
    return variable_types_;
  }
 
  // Returns a list (technically a vector) of the ColIndices of the integer
  // variables. This vector is lazily computed.
  const std::vector<ColIndex>& IntegerVariablesList() const;
 
  // Returns a list (technically a vector) of the ColIndices of the binary
  // integer variables. This vector is lazily computed.
  const std::vector<ColIndex>& BinaryVariablesList() const;
 
  // Returns a list (technically a vector) of the ColIndices of the non-binary
  // integer variables. This vector is lazily computed.
  const std::vector<ColIndex>& NonBinaryVariablesList() const;
 
  // Returns the objective coefficient (or cost) of the given variable for the
  // minimization version of the problem. That is, this is the same as
  // GetObjectiveCoefficient() for a minimization problem and the opposite for a
  // maximization problem.
  Fractional GetObjectiveCoefficientForMinimizationVersion(ColIndex col) const;
 
  // Returns the objective offset and scaling factor.
  Fractional objective_offset() const { return objective_offset_; }
  Fractional objective_scaling_factor() const {
    return objective_scaling_factor_;
  }
 
  // Checks if each variable respects its bounds, nothing else.
  bool SolutionIsWithinVariableBounds(const DenseRow& solution,
                                      Fractional absolute_tolerance) const;
 
  // Tests if the solution is LP-feasible within the given tolerance,
  // i.e., satisfies all linear constraints within the absolute tolerance level.
  // The solution does not need to satisfy the integer constraints.
  bool SolutionIsLPFeasible(const DenseRow& solution,
                            Fractional absolute_tolerance) const;
 
  // Tests if the solution is integer within the given tolerance, i.e., all
  // integer variables have integer values within the absolute tolerance level.
  // The solution does not need to satisfy the linear constraints.
  bool SolutionIsInteger(const DenseRow& solution,
                         Fractional absolute_tolerance) const;
 
  // Tests if the solution is both LP-feasible and integer within the tolerance.
  bool SolutionIsMIPFeasible(const DenseRow& solution,
                             Fractional absolute_tolerance) const;
 
  // Fills the value of the slack from the other variable values.
  // This requires that the slack have been added.
  void ComputeSlackVariableValues(DenseRow* solution) const;
 
  // Functions to translate the sum(solution * objective_coefficients()) to
  // the real objective of the problem and back. Note that these can also
  // be used to translate bounds of the objective in the same way.
  Fractional ApplyObjectiveScalingAndOffset(Fractional value) const;
  Fractional RemoveObjectiveScalingAndOffset(Fractional value) const;
 
  // A short string with the problem dimension.
  std::string GetDimensionString() const;
 
  // A short line with some stats on the objective coefficients.
  std::string GetObjectiveStatsString() const;
 
  // Returns a stringified LinearProgram. We use the LP file format used by
  // lp_solve (see http://lpsolve.sourceforge.net/5.1/index.htm).
  std::string Dump() const;
 
  // Returns a string that contains the provided solution of the LP in the
  // format var1 = X, var2 = Y, var3 = Z, ...
  std::string DumpSolution(const DenseRow& variable_values) const;
 
  // Returns a comma-separated string of integers containing (in that order)
  // num_constraints_, num_variables_in_file_, num_entries_,
  // num_objective_non_zeros_, num_rhs_non_zeros_, num_less_than_constraints_,
  // num_greater_than_constraints_, num_equal_constraints_,
  // num_range_constraints_, num_non_negative_variables_, num_boxed_variables_,
  // num_free_variables_, num_fixed_variables_, num_other_variables_
  // Very useful for reporting in the way used in journal articles.
  std::string GetProblemStats() const;
 
  // Returns a string containing the same information as with GetProblemStats(),
  // but in a much more human-readable form, for example:
  //      Number of rows                               : 27
  //      Number of variables in file                  : 32
  //      Number of entries (non-zeros)                : 83
  //      Number of entries in the objective           : 5
  //      Number of entries in the right-hand side     : 7
  //      Number of <= constraints                     : 19
  //      Number of >= constraints                     : 0
  //      Number of = constraints                      : 8
  //      Number of range constraints                  : 0
  //      Number of non-negative variables             : 32
  //      Number of boxed variables                    : 0
  //      Number of free variables                     : 0
  //      Number of fixed variables                    : 0
  //      Number of other variables                    : 0
  std::string GetPrettyProblemStats() const;
 
  // Returns a comma-separated string of numbers containing (in that order)
  // fill rate, max number of entries (length) in a row, average row length,
  // standard deviation of row length, max column length, average column length,
  // standard deviation of column length
  // Useful for profiling algorithms.
  //
  // TODO(user): Theses are statistics about the underlying matrix and should be
  // moved to SparseMatrix.
  std::string GetNonZeroStats() const;
 
  // Returns a string containing the same information as with GetNonZeroStats(),
  // but in a much more human-readable form, for example:
  //      Fill rate                                    : 9.61%
  //      Entries in row (Max / average / std, dev.)   : 9 / 3.07 / 1.94
  //      Entries in column (Max / average / std, dev.): 4 / 2.59 / 0.96
  std::string GetPrettyNonZeroStats() const;
 
  // Adds slack variables to the problem for all rows which don't have slack
  // variables. The new slack variables have bounds set to opposite of the
  // bounds of the corresponding constraint, and changes all constraints to
  // equality constraints with both bounds set to 0.0. If a constraint uses only
  // integer variables and all their coefficients are integer, it will mark the
  // slack variable as integer too.
  //
  // It is an error to call CreateNewVariable() or CreateNewConstraint() on a
  // linear program on which this method was called.
  //
  // Note that many of the slack variables may not be useful at all, but in
  // order not to recompute the matrix from one Solve() to the next, we always
  // include all of them for a given lp matrix.
  //
  // TODO(user): investigate the impact on the running time. It seems low
  // because we almost never iterate on fixed variables.
  void AddSlackVariablesWhereNecessary(bool detect_integer_constraints);
 
  // Returns the index of the first slack variable in the linear program.
  // Returns kInvalidCol if slack variables were not injected into the problem
  // yet.
  ColIndex GetFirstSlackVariable() const;
 
  // Returns the index of the slack variable corresponding to the given
  // constraint. Returns kInvalidCol if slack variables were not injected into
  // the problem yet.
  ColIndex GetSlackVariable(RowIndex row) const;
 
  // Populates the calling object with the dual of the LinearProgram passed as
  // parameter.
  // For the general form that we solve,
  // min c.x
  // s.t.  A_1 x = b_1
  //       A_2 x <= b_2
  //       A_3 x >= b_3
  //       l <= x <= u
  // With x: n-column of unknowns
  // l,u: n-columns of bound coefficients
  // c: n-row of cost coefficients
  // A_i: m_i×n-matrix of coefficients
  // b_i: m_i-column of right-hand side coefficients
  //
  // The dual is
  //
  // max b_1.y_1 + b_2.y_2 + b_3.y_3 + l.v + u.w
  // s.t. y_1 A_1 + y_2 A_2 + y_3 A_3 + v + w = c
  //       y_1 free, y_2 <= 0, y_3 >= 0, v >= 0, w <= 0
  // With:
  // y_i: m_i-row of unknowns
  // v,w: n-rows of unknowns
  //
  // If range constraints are present, each of the corresponding row is
  // duplicated (with one becoming lower bounded and the other upper bounded).
  // For such ranged row in the primal, duplicated_rows[row] is set to the
  // column index in the dual of the corresponding column duplicate. For
  // non-ranged row, duplicated_rows[row] is set to kInvalidCol.
  //
  // IMPORTANT: The linear_program argument must not have any free constraints.
  //
  // IMPORTANT: This function always interprets the argument in its minimization
  // form. So the dual solution of the dual needs to be negated if we want to
  // compute the solution of a maximization problem given as an argument.
  //
  // TODO(user): Do not interpret as a minimization problem?
  void PopulateFromDual(const LinearProgram& dual,
                        RowToColMapping* duplicated_rows);
 
  // Populates the calling object with the given LinearProgram.
  void PopulateFromLinearProgram(const LinearProgram& linear_program);
 
  // Populates the calling object with the given LinearProgram while permuting
  // variables and constraints. This is useful mainly for testing to generate
  // a model with the same optimal objective value.
  void PopulateFromPermutedLinearProgram(
      const LinearProgram& lp, const RowPermutation& row_permutation,
      const ColumnPermutation& col_permutation);
 
  // Populates the calling object with the variables of the given LinearProgram.
  // The function preserves the bounds, the integrality, the names of the
  // variables and their objective coefficients. No constraints are copied (the
  // matrix in the destination has 0 rows).
  void PopulateFromLinearProgramVariables(const LinearProgram& linear_program);
 
  // Adds constraints to the linear program. The constraints are specified using
  // a sparse matrix of the coefficients, and vectors that represent the
  // left-hand side and the right-hand side of the constraints, i.e.
  // left_hand_sides <= coefficients * variables <= right_hand_sides.
  // The sizes of the columns and the names must be the same as the number of
  // rows of the sparse matrix; the number of columns of the matrix must be
  // equal to the number of variables of the linear program.
  void AddConstraints(const SparseMatrix& coefficients,
                      const DenseColumn& left_hand_sides,
                      const DenseColumn& right_hand_sides,
                      const StrictITIVector<RowIndex, std::string>& names);
 
  // Calls the AddConstraints method. After adding the constraints it adds slack
  // variables to the constraints.
  void AddConstraintsWithSlackVariables(
      const SparseMatrix& coefficients, const DenseColumn& left_hand_sides,
      const DenseColumn& right_hand_sides,
      const StrictITIVector<RowIndex, std::string>& names,
      bool detect_integer_constraints_for_slack);
 
  // Swaps the content of this LinearProgram with the one passed as argument.
  // Works in O(1).
  void Swap(LinearProgram* linear_program);
 
  // Removes the given column indices from the LinearProgram.
  // This needs to allocate O(num_variables) memory to update variable_table_.
  void DeleteColumns(const DenseBooleanRow& columns_to_delete);
 
  // Removes slack variables from the linear program. The method restores the
  // bounds on constraints from the bounds of the slack variables, resets the
  // index of the first slack variable, and removes the relevant columns from
  // the matrix.
  void DeleteSlackVariables();
 
  // Scales the problem using the given scaler.
  void Scale(SparseMatrixScaler* scaler);
 
  // While Scale() makes sure the coefficients inside the linear program matrix
  // are in [-1, 1], the objective coefficients, variable bounds and constraint
  // bounds can still take large values (originally or due to the matrix
  // scaling).
  //
  // It makes a lot of sense to also scale them given that internally we use
  // absolute tolerances, and that it is nice to have the same behavior if users
  // scale their problems. For instance one could change the unit of ALL the
  // variables from Bytes to MBytes if they denote memory quantities. Or express
  // a cost in dollars instead of thousands of dollars.
  //
  // Here, we are quite prudent and just make sure that the range of the
  // non-zeros magnitudes contains one. So for instance if all non-zeros costs
  // are in [1e4, 1e6], we will divide them by 1e4 so that the new range is
  // [1, 1e2].
  //
  // TODO(user): Another more aggressive idea is to set the median/mean/geomean
  // of the magnitudes to one. Investigate if this leads to better results. It
  // does look more robust.
  //
  // Both functions update objective_scaling_factor()/objective_offset() and
  // return the scaling coefficient so that:
  // - For ScaleObjective(), the old coefficients can be retrieved by
  //   multiplying the new ones by the returned factor.
  // - For ScaleBounds(), the old variable and constraint bounds can be
  //   retrieved by multiplying the new ones by the returned factor.
  Fractional ScaleObjective(GlopParameters::CostScalingAlgorithm method);
  Fractional ScaleBounds();
 
  // Removes the given row indices from the LinearProgram.
  // This needs to allocate O(num_variables) memory.
  void DeleteRows(const DenseBooleanColumn& rows_to_delete);
 
  // Does basic checking on the linear program:
  // - returns false if some coefficient are NaNs.
  // - returns false if some coefficient other than the bounds are +/- infinity.
  // Note that these conditions are also guarded by DCHECK on each of the
  // SetXXX() function above.
  bool IsValid() const;
 
  // Updates the bounds of the variables to the intersection of their original
  // bounds and the bounds specified by variable_lower_bounds and
  // variable_upper_bounds. If the new bounds of all variables are non-empty,
  // returns true; otherwise, returns false.
  bool UpdateVariableBoundsToIntersection(
      const DenseRow& variable_lower_bounds,
      const DenseRow& variable_upper_bounds);
 
  // Returns true if the linear program is in equation form Ax = 0 and all slack
  // variables have been added. This is also called "computational form" in some
  // of the literature.
  bool IsInEquationForm() const;
 
  // Returns true if all integer variables in the linear program have strictly
  // integer bounds.
  bool BoundsOfIntegerVariablesAreInteger(Fractional tolerance) const;
 
  // Returns true if all integer constraints in the linear program have strictly
  // integer bounds.
  bool BoundsOfIntegerConstraintsAreInteger(Fractional tolerance) const;
 
  // Advanced usage. Bypass the costly call to CleanUp() when we known that the
  // change we made kept the matrix columns "clean" (see the comment of
  // CleanUp()). This is unsafe but can save a big chunk of the running time
  // when one does a small amount of incremental changes to the problem (like
  // adding a new row with no duplicates or zero entries).
  void NotifyThatColumnsAreClean() {
    DCHECK(matrix_.IsCleanedUp());
    columns_are_known_to_be_clean_ = true;
  }
 
  // If true, checks bound validity in debug mode.
  void SetDcheckBounds(bool dcheck_bounds) { dcheck_bounds_ = dcheck_bounds; }
 
 private:
  // A helper function that updates the vectors integer_variables_list_,
  // binary_variables_list_, and non_binary_variables_list_.
  void UpdateAllIntegerVariableLists() const;
 
  // A helper function to format problem statistics. Used by GetProblemStats()
  // and GetPrettyProblemStats().
  std::string ProblemStatFormatter(const absl::string_view format) const;
 
  // A helper function to format non-zero statistics. Used by GetNonZeroStats()
  // and GetPrettyNonZeroStats().
  std::string NonZeroStatFormatter(const absl::string_view format) const;
 
  // Resizes all row vectors to include index 'row'.
  void ResizeRowsIfNeeded(RowIndex row);
 
  // Populates the definitions of variables, name and objective in the calling
  // linear program with the data from the given linear program. The method does
  // not touch the data structures for storing constraints.
  void PopulateNameObjectiveAndVariablesFromLinearProgram(
      const LinearProgram& linear_program);
 
  // Stores the linear program coefficients.
  SparseMatrix matrix_;
 
  // The transpose of matrix_. This will be lazily recomputed by
  // GetTransposeSparseMatrix() if transpose_matrix_is_consistent_ is false.
  mutable SparseMatrix transpose_matrix_;
 
  // Constraint related quantities.
  DenseColumn constraint_lower_bounds_;
  DenseColumn constraint_upper_bounds_;
  StrictITIVector<RowIndex, std::string> constraint_names_;
 
  // Variable related quantities.
  DenseRow objective_coefficients_;
  DenseRow variable_lower_bounds_;
  DenseRow variable_upper_bounds_;
  StrictITIVector<ColIndex, std::string> variable_names_;
  StrictITIVector<ColIndex, VariableType> variable_types_;
 
  // The vector of the indices of variables constrained to be integer.
  // Note(user): the set of indices in integer_variables_list_ is the union
  // of the set of indices in binary_variables_list_ and of the set of indices
  // in non_binary_variables_list_ below.
  mutable std::vector<ColIndex> integer_variables_list_;
 
  // The vector of the indices of variables constrained to be binary.
  mutable std::vector<ColIndex> binary_variables_list_;
 
  // The vector of the indices of variables constrained to be integer, but not
  // binary.
  mutable std::vector<ColIndex> non_binary_variables_list_;
 
  // Map used to find the index of a variable based on its id.
  absl::flat_hash_map<std::string, ColIndex> variable_table_;
 
  // Map used to find the index of a constraint based on its id.
  absl::flat_hash_map<std::string, RowIndex> constraint_table_;
 
  // Offset of the objective, i.e. value of the objective when all variables
  // are set to zero.
  Fractional objective_offset_;
  Fractional objective_scaling_factor_;
 
  // Boolean true (resp. false) when the problem is a maximization
  // (resp. minimization) problem.
  bool maximize_;
 
  // Boolean to speed-up multiple calls to IsCleanedUp() or
  // CleanUp(). Mutable so IsCleanedUp() can be const.
  mutable bool columns_are_known_to_be_clean_;
 
  // Whether transpose_matrix_ is guaranteed to be the transpose of matrix_.
  mutable bool transpose_matrix_is_consistent_;
 
  // Whether integer_variables_list_ is consistent with the current
  // LinearProgram.
  mutable bool integer_variables_list_is_consistent_;
 
  // The name of the LinearProgram.
  std::string name_;
 
  // The index of the first slack variable added to the linear program by
  // LinearProgram::AddSlackVariablesForAllRows().
  ColIndex first_slack_variable_;
 
  // If true, checks bounds in debug mode.
  bool dcheck_bounds_ = true;
 
  friend void Scale(LinearProgram* lp, SparseMatrixScaler* scaler,
                    GlopParameters::ScalingAlgorithm scaling_method);
 
  DISALLOW_COPY_AND_ASSIGN(LinearProgram);
};
 
// --------------------------------------------------------
// ProblemSolution
// --------------------------------------------------------
// Contains the solution of a LinearProgram as returned by a preprocessor.
struct ProblemSolution {
  ProblemSolution(RowIndex num_rows, ColIndex num_cols)
      : status(ProblemStatus::OPTIMAL),
        primal_values(num_cols, 0.0),
        dual_values(num_rows, 0.0),
        variable_statuses(num_cols, VariableStatus::FREE),
        constraint_statuses(num_rows, ConstraintStatus::FREE) {}
  // The solution status.
  ProblemStatus status;
 
  // The actual primal/dual solution values. This is what most clients will
  // need, and this is enough for LPSolver to easily check the optimality.
  DenseRow primal_values;
  DenseColumn dual_values;
 
  // The status of the variables and constraints which is difficult to
  // reconstruct from the solution values alone. Some remarks:
  //  - From this information alone, by factorizing the basis, it is easy to
  //    reconstruct the primal and dual values.
  //  - The main difficulty to construct this from the solution values is to
  //    reconstruct the optimal basis if some basic variables are exactly at
  //    one of their bounds (and their reduced costs are close to zero).
  //  - The non-basic information (VariableStatus::FIXED_VALUE,
  //    VariableStatus::AT_LOWER_BOUND, VariableStatus::AT_UPPER_BOUND,
  //    VariableStatus::FREE) is easy to construct for variables (because
  //    they are at their exact bounds). They can be guessed for constraints
  //    (here a small precision error is unavoidable). However, it is useful to
  //    carry this exact information during post-solve.
  VariableStatusRow variable_statuses;
  ConstraintStatusColumn constraint_statuses;
 
  std::string DebugString() const;
};
 
// Helper function to check the bounds of the SetVariableBounds() and
// SetConstraintBounds() functions.
inline bool AreBoundsValid(Fractional lower_bound, Fractional upper_bound) {
  if (std::isnan(lower_bound)) return false;
  if (std::isnan(upper_bound)) return false;
  if (lower_bound == kInfinity && upper_bound == kInfinity) return false;
  if (lower_bound == -kInfinity && upper_bound == -kInfinity) return false;
  if (lower_bound > upper_bound) return false;
  return true;
}
 
}  // namespace glop
}  // namespace operations_research
 
#endif  // OR_TOOLS_LP_DATA_LP_DATA_H_