1/* $Id: CoinPresolveDupcol.hpp 1372 2011-01-03 23:31:00Z lou $ */
2// Copyright (C) 2002, International Business Machines
3// Corporation and others. All Rights Reserved.
4// This code is licensed under the terms of the Eclipse Public License (EPL).
5
6#ifndef CoinPresolveDupcol_H
7#define CoinPresolveDupcol_H
8
9#include "CoinPresolveMatrix.hpp"
10
11/*!
12 \file
13*/
14
15#define DUPCOL 10
16
17/*! \class dupcol_action
18 \brief Detect and remove duplicate columns
19
20 The general technique is to sum the coefficients a_(*,j) of each column.
21 Columns with identical sums are duplicates. The obvious problem is that,
22 <i>e.g.</i>, [1 0 1 0] and [0 1 0 1] both add to 2. To minimize the
23 chances of false positives, the coefficients of each row are multipled by
24 a random number r_i, so that we sum r_i*a_ij.
25
26 Candidate columns are checked to confirm they are identical. Where the
27 columns have the same objective coefficient, the two are combined. If the
28 columns have different objective coefficients, complications ensue. In order
29 to remove the duplicate, it must be possible to fix the variable at a bound.
30*/
31
32class dupcol_action : public CoinPresolveAction {
33 dupcol_action();
34 dupcol_action(const dupcol_action& rhs);
35 dupcol_action& operator=(const dupcol_action& rhs);
36
37 struct action {
38 double thislo;
39 double thisup;
40 double lastlo;
41 double lastup;
42 int ithis;
43 int ilast;
44
45 double *colels;
46 int nincol;
47 };
48
49 const int nactions_;
50 // actions_ is owned by the class and must be deleted at destruction
51 const action *const actions_;
52
53 dupcol_action(int nactions, const action *actions,
54 const CoinPresolveAction *next) :
55 CoinPresolveAction(next),
56 nactions_(nactions),
57 actions_(actions) {}
58
59 public:
60 const char *name() const override;
61
62 static const CoinPresolveAction *presolve(CoinPresolveMatrix *prob,
63 const CoinPresolveAction *next);
64
65 void postsolve(CoinPostsolveMatrix *prob) const override;
66
67 ~dupcol_action();
68
69};
70
71
72/*! \class duprow_action
73 \brief Detect and remove duplicate rows
74
75 The algorithm to detect duplicate rows is as outlined for dupcol_action.
76
77 If the feasible interval for one constraint is strictly contained in the
78 other, the tighter (contained) constraint is kept. If the feasible
79 intervals are disjoint, the problem is infeasible. If the feasible
80 intervals overlap, both constraints are kept.
81
82 duprow_action is definitely a work in progress; #postsolve is
83 unimplemented.
84 This doesn't matter as it uses useless_constraint.
85*/
86
87class duprow_action : public CoinPresolveAction {
88 struct action {
89 int row;
90 double lbound;
91 double ubound;
92 };
93
94 const int nactions_;
95 const action *const actions_;
96
97 duprow_action():CoinPresolveAction(nullptr),nactions_(0),actions_(nullptr) {}
98 duprow_action(int nactions,
99 const action *actions,
100 const CoinPresolveAction *next) :
101 CoinPresolveAction(next),
102 nactions_(nactions), actions_(actions) {}
103
104 public:
105 const char *name() const override;
106
107 static const CoinPresolveAction *presolve(CoinPresolveMatrix *prob,
108 const CoinPresolveAction *next);
109
110 void postsolve(CoinPostsolveMatrix *prob) const override;
111
112 //~duprow_action() { delete[]actions_; }
113};
114
115/*! \class gubrow_action
116 \brief Detect and remove entries whose sum is known
117
118 If we have an equality row where all entries same then
119 For other rows where all entries for that equality row are same
120 then we can delete entries and modify rhs
121 gubrow_action is definitely a work in progress; #postsolve is
122 unimplemented.
123*/
124
125class gubrow_action : public CoinPresolveAction {
126 struct action {
127 int row;
128 double lbound;
129 double ubound;
130 };
131
132 const int nactions_;
133 const action *const actions_;
134
135 gubrow_action():CoinPresolveAction(nullptr),nactions_(0),actions_(nullptr) {}
136 gubrow_action(int nactions,
137 const action *actions,
138 const CoinPresolveAction *next) :
139 CoinPresolveAction(next),
140 nactions_(nactions), actions_(actions) {}
141
142 public:
143 const char *name() const override;
144
145 static const CoinPresolveAction *presolve(CoinPresolveMatrix *prob,
146 const CoinPresolveAction *next);
147
148 void postsolve(CoinPostsolveMatrix *prob) const override;
149
150 //~gubrow_action() { delete[]actions_; }
151};
152
153#endif
154