Hi, Michael,

Thanks for your input.<= br>

Are there some rules about the constraint selection in iterative LP?=

Also, in my LP model, each constraint will introduce a new d=
ecision variable. Thanks for your input.<= br>

Are there some rules about the constraint selection in iterative LP?=

=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 decVarK_j =3D decVarX_i * = constValue_i=C2=A0 - decVarT

then, check the constraint <=
br>

=C2=A0=C2=A0=C2=A0=C2=A0 decVarT + sum of (decVarK_j ) from j=3D1 to= =C2=A0 L=C2=A0 <=3D=C2=A0 [sum of (constantVal= ueP_i=C2=A0 * decVarX_i)=C2=A0 from i=3D1 to=C2=A0 N ] * constantQ

=C2=A0=C2=A0=C2=A0=C2=A0 decVarT + sum of (decVarK_j ) from j=3D1 to= =C2=A0 L=C2=A0 <=3D=C2=A0 [sum of (constantVal= ueP_i=C2=A0 * decVarX_i)=C2=A0 from i=3D1 to=C2=A0 N ] * constantQ

If it satisfies the constraint, it means that the solution optima=
lity still can be kept ?

Any discussion/suggestions woul=
d be welcome.

thanks

On Thu, Sep 1, 2016 at=
2:07 PM, Michael Hennebry <hennebry@web.cs.ndsu.nodak.edu> wrote:

On W= ed, 31 Aug 2016, usa usa wrote:

The problem is that the number of constraints of=C2=A0 =C2=A0decVarK_i for = i=3D1 to L

and L can be very large, e.g. 100,0000.

I think that the given constraints were not what you really intended.

It means that it will have 100,000 constraints in the LP, which I want toavoid.

How to combine them so that I can reduce the size of the LP model meanwhile=

keeping all constraints satisfied ?

In general, you can't.

The usual solution is iterative LP.

Solve the problem with a subset of constraints.

If the solution satisfies all your constaints, you are done.

Otherwise select one or more violated constraints and resolve.

Rinse and repeat until you have a solution or fatigue sets in.

The tricky part is in the constraint selection.

Unless you are doing something silly like working from an explicit list,

it will be problem-specific.=

--

Michael=C2=A0 =C2=A0hennebry@web.cs.ndsu.NoDak.edu

"Sorry but your password must contain an uppercase letter, a number,a haiku, a gang sign, a heiroglyph, and the blood of a virgin."

=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0--=C2= =A0 someeecards

Hi, Michael,

Thanks for =
your answers. On Fri, Sep 2, 2016 at 3:36 PM, Michael=
Hennebry <hennebry@web.cs.ndsu.nodak.edu> wrot=
e:

**=C2=
=A0=C2=A0=C2=A0 A:=C2=A0 It means decVarK_j >=3D=C2=A0 SUM E ( decVarX_i=
* constValue_j_i for i in 1...N) - decVarT=C2=A0 ?**

**=C2=A0 =C2=A0 A:=C2=A0 No, the values of K_j depen=
d on SUM E ( decVarX_i * constValue_j_i for i in 1...N) - decVarT **

= =C2=A0

<=
/div>**=C2=A0=C2=A0 A: I do not quite understand this. For j=3D1 ... =
L, if in one iteration, I chose j =3D1 ... M with M is much smaller than L.=
For example, L =3D 100000, and M =3D 1000. So, in the LP model, I only hav=
e optimal solutions for the constraints of **

=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0=C2=A0 decVarK_j >=3D=C2=A0 SUM E ( decVarX_i * constValue_j_i for= i in 1...N)

**=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0 **

**for j =3D1...M. **

**H=
ow can I use the solutions for j=3D1...M to change each decVarK_j to**

max(0, decVarX_i * constValue_j_i - decVarT)=C2=A0 with j =3D 1... N ?=

**=C2=A0=C2=A0 A: yes**

= =C2=A0

First, I am unclear= as to what the exact model is.

This is what I got from yur first post:

The i SUMs run from 1 to N.

The j SUMs run from 1 to L.

Max SUM P_i*X_i

=C2=A0 =C2=A0 =C2=A0i

T + SUM K_j=C2=A0 =C2=A0 =C2=A0 <=3D=C2=A0 =C2=A0SUM Q*P_i*X_i

=C2=A0 =C2=A0 =C2=A0j=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0i

SUM E_i*X_i <=3D D*SUM E_i

=C2=A0i=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 i

K_j >=3D SUM V_j_i*X_i - T=C2=A0 =C2=A0 =C2=A0 =C2=A0j in 1..L

=C2=A0 =C2=A0 =C2=A0 =C2=A0 i

T no explicit bound

0 <=3D X_i <=3D 1=C2=A0 =C2=A0i in 1..N

0 <=3D K_i=C2=A0 =C2=A0 =C2=A0 =C2=A0 i in 1..L

I'm not sure I got it right.

On Thu, 1 Sep 2016, usa usa wrote:

Also, in my LP model, each constraint will introduce a new decision

variable.

That makes it trickier.=C2=A0 Look up column generation.

=C2=A0 =C2=A0 decVarK_j >=3D decVarX_i * constValue_i=C2=A0 - decVarT

Did you mean decVarK_j >=3D decVarX_i * constValue_j_i - decVarT=C2=A0 ?=

If I used the solutions from solving the model with part of the constraints=

and then replace the "decVarX_i" and "decVarT" with the= solution values and

set

=C2=A0 =C2=A0 =C2=A0decVarK_j =3D decVarX_i * constValue_i=C2=A0 - decVarT<= br>

Did you mean decVarK_j =3D SUM decVarX_i * constValue_j_i=C2=A0 - decVarT ?=

=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 i

=C2=A0** =C2=A0 A:=C2=A0 It means decVarK_j =3D SUM =
E( decVarX_i * constValue_j_i=C2=A0 for i in 1...N ) - decVarT ?**

=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 i

=C2=A0

=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 i

=C2=A0

If decVarK_j is in the current LP, use that value.

Traditionally, values of non-explicit variables are often zero,

though other computations are possible.

Will most of the K_j's be zero?

= =C2=A0

If not, m= ost of the j-indexed constraints will be active.

In that case, you would still want an algorithm that

does not do as much work as solving the entire LP at once.

I have an idea, but will not guarantee it will work.

If you use max(0, decVarX_i * constValue_j_i - decVarT) ,

all the nonzero decVarK_j's are likely to change with every iteration.<= br> That said, for every feasible solution, changing each decVarK_j to

max(0, decVarX_i * constValue_j_i - decVarT)

will preserve feasibility and optimality.

=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0=C2=A0 decVarK_j >=3D=C2=A0 SUM E ( decVarX_i * constValue_j_i for= i in 1...N)

max(0, decVarX_i * constValue_j_i - decVarT)=C2=A0 with j =3D 1... N ?

Also note that the set of explicit j indices need not be contiguous.

1..N subsetof explicitIndices subsetof 1..L=C2=A0 is sufficient.

=C2=A0 =C2=A0 decVarT + sum of (decVarK_j ) from j=3D1 to=C2=A0 L=C2=A0 <= ;=3D=C2=A0 [sum of

(constantValueP_i=C2=A0 * decVarX_i)=C2=A0 from i=3D1 to=C2=A0 N ] * consta= ntQ

T + SUM K_j=C2=A0 =C2=A0<=3D=C2=A0 =C2=A0SUM Q*P_i*X_i

=C2=A0 =C2=A0j in 1..L=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0=C2=A0 =C2=A0 i in 1..N

correct?

= =C2=A0

As noted earlier, you are in the realm of column (variable) generation.

There is a feasible solution with all the K_j's fixed at zero.

It might not be optimal.

Pricing the K_j's to determine which should become

nonzero is an important aspect of column generation.

--

Michael=C2=A0 =C2=A0hennebry@web.cs.ndsu.NoDak.edu

"Sorry but your password must contain an uppercase letter, a number,a haiku, a gang sign, a heiroglyph, and the blood of a virgin."

=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0--=C2= =A0 someeecards

Please review my answers below.

thanksOn Tue, Se=
p 6, 2016 at 2:14 PM, Michael Hennebry <hennebry@web.cs.ndsu.=
nodak.edu> wrote:

**=C2=A0 =C2=A0=C2=A0 A:=C2=A0 yes**

=C2=A0

Let us name the constraints.

On Sun, 4 Sep 2016, usa usa wrote:

On Fri, Sep 2, 2016 at 3:36 PM, Michael Hennebry <

hennebr= y@web.cs.ndsu.nodak.edu> wrote:

First, I am unclear as to what the exact model is.

This is what I got from yur first post:

The i SUMs run from 1 to N.

The j SUMs run from 1 to L.

Max SUM P_i*X_i

=C2=A0 =C2=A0 =C2=A0i

Constraint A:

T + SUM K_j=C2=A0 =C2=A0 =C2=A0 <=3D=C2=A0 =C2=A0SUM Q*P_i*X_i

=C2=A0 =C2=A0 =C2=A0j=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0i

Constraint B:

SUM E_i*X_i <=3D D*SUM E_i

=C2=A0i=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 i

Constraints C_1 ... C_L

K_j >=3D SUM V_j_i*X_i - T=C2=A0 =C2=A0 =C2=A0 =C2=A0j in 1..L

=C2=A0 =C2=A0 =C2=A0 =C2=A0 i

T no explicit bound

0 <=3D X_i <=3D 1=C2=A0 =C2=A0i in 1..N

0 <=3D K_i=C2=A0 =C2=A0 =C2=A0 =C2=A0 i in 1..L

On Thu, 1 Sep 2016, usa usa wrote:

Also, in my LP model, each constraint will introduce a new decision

variable.

That makes it trickier.=C2=A0 Look up column generation.

=C2=A0 =C2=A0 decVarK_j >=3D decVarX_i * constValue_i=C2=A0 - decVarT

Did you mean decVarK_j >=3D decVarX_i * constValue_j_i - decVarT=C2=A0 ?=

*=C2=A0 =C2=A0 A:=C2=A0 It means decVarK_j >=3D=C2=A0 SUM E ( decVarX_i = * constValue_j_i for i in

1...N) - decVarT=C2=A0 ?*

Is this supposed to be constraint C_j ?

=C2=A0

Is E suposed to be there?=C2=A0 Should it have an index?

If I used the solutions from solving the model with part of the constraints=1...N ) - decVarT ?*

and then replace the "decVarX_i" and "decVarT" with the= solution values

and

set

=C2=A0 =C2=A0 =C2=A0decVarK_j =3D decVarX_i * constValue_i=C2=A0 - decVarT<= br>

Did you mean decVarK_j =3D SUM decVarX_i * constValue_j_i=C2=A0 - decVarT ?=

=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 i

=C2=A0*=C2=A0 =C2=A0A:=C2=A0 It means decVarK_j =3D SUM E( decVarX_i * cons= tValue_j_i=C2=A0 for i in

=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0i

If decVarK_j is in the current LP, use that value.

Traditionally, values of non-explicit variables are often zero,

though other computations are possible.

Will most of the K_j's be zero?

*=C2=A0 =C2=A0 A:=C2=A0 No, the values of K_j depend on SUM E ( decVarX_i *= constValue_j_i

for i in 1...N) - decVarT *

If not, most of the j-indexed constraints will be active.

In that case, you would still want an algorithm that

does not do as much work as solving the entire LP at once.

I have an idea, but will not guarantee it will work.

If you use max(0, decVarX_i * constValue_j_i - decVarT) ,

Should have been max(0, SUM decVarX_i*constValue_j_i - decVarT)

=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0i

Doesn't help.

all the nonzero decVarK_j's are likely to change with every iteration.<= br> That said, for every feasible solution, changing each decVarK_j to

max(0, decVarX_i * constValue_j_i - decVarT)

will preserve feasibility and optimality.

*=C2=A0 =C2=A0A: I do not quite understand this. For j=3D1 ... L, if in one= iteration,

I chose j =3D1 ... M with M is much smaller than L. For example, L =3D 1000= 00,

and M =3D 1000. So, in the LP model, I only have optimal solutions for the<= br> constraints of=C2=A0 =C2=A0 =C2=A0 =C2=A0 decVarK_j >=3D=C2=A0 SUM E ( d= ecVarX_i * constValue_j_i for

i in 1...N)*

*for j =3D1...M. *

*How can I use the solutions for j=3D1...M to change each decVarK_j to max(= 0,

decVarX_i * constValue_j_i - decVarT)=C2=A0 with j =3D 1... N ? *

I do not know that you can.

That was more or less the point.

When one does column generation,

one usually arranges for the unmentioned variables to be zero.

To do column generation, you will need to reformulate without the K_j's= .

Replace them with something that you expect to be mostly zero.

You will almost certainly need to represent nonzero variables.

I suspect that with a bit of algrebra one

could get rid of the K_j's and T altogether.

That would leave the X_i's as the remaining variables.

The price would be an exponential number of constraints.

=

I'd expect the task of finding the most

violated constraint to not be very difficult.

--

Michael=C2=A0 =C2=A0hennebry@web.cs.ndsu.NoDak.edu

"Sorry but your password must contain an uppercase letter, a number,a haiku, a gang sign, a heiroglyph, and the blood of a virgin."

=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0--=C2= =A0 someeecards

--089e012290ee156c48053bdb143b-- From MAILER-DAEMON Tue Sep 06 20:35:28 2016 Received: from list by lists.gnu.org with archive (Exim 4.71) id 1bhQps-0001Af-Ki for mharc-help-glpk@gnu.org; Tue, 06 Sep 2016 20:35:28 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:52763) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from

I am working on a bit integer program and my data has=
45000 variables (see below). I am basically=C2=A0 just looking for a feasi=
ble solution, my objective is constant.

My question: it took =
10 minutes to run using the glpk solver. I converted to a CBC form and it s=
olved it in 1 minute, and using Gurobi it took about 1 second (but it used =
all 8 threads).=C2=A0 Am I doing something wrong with glpk for bit integer =
programs?=C2=A0 Is there an option that is more efficient?Mode= l has been successfully generated

GLPK Integer Optimizer, v4.60

68514= rows, 45040 columns, 372605 non-zeros

45040 integer variables, all of w= hich are binary

Preprocessing...

9020 hidden covering inequaliti(es) = were detected

1397 constraint coefficient(s) were reduced

15253 rows,= 29410 columns, 161743 non-zeros

29410 integer variables, all of which a= re binary

Scaling...

=C2=A0A: min|aij| =3D=C2=A0 1.000e+00=C2=A0 max|= aij| =3D=C2=A0 1.000e+01=C2=A0 ratio =3D=C2=A0 1.000e+01

Problem data se= em to be well scaled

Constructing initial basis...

Size of triangular= part is 15253

Solving LP relaxation...

GLPK Simplex Optimizer, v4.60=

15253 rows, 29410 columns, 161743 non-zeros

=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0 0: obj =3D=C2=A0=C2=A0 0.000000000e+00 inf =3D=C2=A0=C2=A0 6.040e+02= (247)

=C2=A0=C2=A0=C2=A0 500: obj =3D=C2=A0=C2=A0 0.000000000e+00 inf = =3D=C2=A0=C2=A0 3.980e+02 (115) 1

=C2=A0=C2=A0=C2=A0 837: obj =3D=C2=A0= =C2=A0 0.000000000e+00 inf =3D=C2=A0=C2=A0 0.000e+00 (0) 1

OPTIMAL LP SO= LUTION FOUND

Integer optimization begins...

+=C2=A0=C2=A0 837: mip = =3D=C2=A0=C2=A0=C2=A0=C2=A0 not found yet >=3D=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 -inf=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0 (1; 0)

+=C2=A0 1389: mip =3D=C2=A0=C2=A0=C2= =A0=C2=A0 not found yet >=3D=C2=A0=C2=A0 0.000000000e+00=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0 (30; 0)

+=C2=A0 2309: mip =3D=C2=A0=C2=A0=C2= =A0=C2=A0 not found yet >=3D=C2=A0=C2=A0 0.000000000e+00=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0 (50; 7)

+=C2=A0 2835: mip =3D=C2=A0=C2=A0=C2= =A0=C2=A0 not found yet >=3D=C2=A0=C2=A0 0.000000000e+00=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0 (77; 14)

+=C2=A0 3106: mip =3D=C2=A0=C2=A0= =C2=A0=C2=A0 not found yet >=3D=C2=A0=C2=A0 0.000000000e+00=C2=A0=C2=A0= =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 (113; 14)

On Thu, Sep 8, 2016 at 1:23 AM, Michael Hennebry <=
hennebr=
y@web.cs.ndsu.nodak.edu> wrote:

On Tue, 6 Sep 2016, Michael = Hennebry wrote:

Let us name the constraints.

First, I am unclear as to what the exact model is.

This is what I got from yur first post:

The i SUMs run from 1 to N.

The j SUMs run from 1 to L.

Max SUM P_i*X_i

=C2=A0 =C2=A0 =C2=A0i

Constraint A:

T + SUM K_j=C2=A0 =C2=A0 =C2=A0 <=3D=C2=A0 =C2=A0SUM Q*P_i*X_i

=C2=A0 =C2=A0 =C2=A0j=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0i

Constraint B:

SUM E_i*X_i <=3D D*SUM E_i

=C2=A0i=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 i

Constraints C_1 ... C_L

K_j >=3D SUM V_j_i*X_i - T=C2=A0 =C2=A0 =C2=A0 =C2=A0j in 1..L

=C2=A0 =C2=A0 =C2=A0 =C2=A0 i

T no explicit bound

0 <=3D X_i <=3D 1=C2=A0 =C2=A0i in 1..N

0 <=3D K_i=C2=A0 =C2=A0 =C2=A0 =C2=A0 i in 1..L

I suspect that with a bit of algrebra one

could get rid of the K_j's and T altogether.

That would leave the X_i's as the remaining variables.

The price would be an exponential number of constraints.

I'd expect the task of finding the most

violated constraint to not be very difficult.

No need to get rid of T.

Getting rid of the K_j's is easy:

Replace Constraint A and constraints C with

D:

T +=C2=A0 SUM=C2=A0 =C2=A0(SUM V_j_i*X_i - T)=C2=A0 <=3D SUM Q*P_i*X_i= =C2=A0 =C2=A0for all S subsetof 1..L

=C2=A0 =C2=A0 j in S=C2=A0 i in 1..N

This is 2**L constraints.

For given values of X and T,

a most violated is D_S with S =3D { j in 1..L: SUM V_j_i*X_i - T > 0 }

=C2=A0=C2=A0 A: replacing K_j in Constraint A can r=
educe the number of constraints in the beginning, but how to reduce the siz=
e of D_S at each iteration so that the algorithm can be convergent. =

Otherwise, the number of violated "K_j >=3D SUM V_j_i*X_i - T=C2=A0 =C2=A0 =C2=A0 =C2=A0j in 1..L=
" constraints cannot be reduced efficiently at each iteration. The mod=
el size is still large.

<= blockquote style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,= 204,204);padding-left:1ex" class=3D"gmail_quote">=C2=A0

--

Michael=C2=A0 =C2=A0hennebry@web.cs.ndsu.NoDak.edu

"Sorry but your password must contain an uppercase letter, a number,**
a haiku, a gang sign, a heiroglyph, and the blood of a virgin."**

=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0--=C2= =A0 someeecards

Michael=C2=A0 =C2=A0hennebry@web.cs.ndsu.NoDak.

"Sorry but your password must contain an uppercase letter, a number,

=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0--=C2= =A0 someeecards

--001a114e2e3ab51a80053c00d9c7-- From MAILER-DAEMON Thu Sep 08 12:02:43 2016 Received: from list by lists.gnu.org with archive (Exim 4.71) id 1bi1ml-0000AI-J7 for mharc-help-glpk@gnu.org; Thu, 08 Sep 2016 12:02:43 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:55957) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from

On Thu, Sep 8, 2016 at 1:23 AM, Michael Hennebry <=
hennebr=
y@web.cs.ndsu.nodak.edu> wrote:

On Tue, 6 Sep 2016, Michael = Hennebry wrote:

Let us name the constraints.

First, I am unclear as to what the exact model is.

This is what I got from yur first post:

The i SUMs run from 1 to N.

The j SUMs run from 1 to L.

Max SUM P_i*X_i

=C2=A0 =C2=A0 =C2=A0i

Constraint A:

T + SUM K_j=C2=A0 =C2=A0 =C2=A0 <=3D=C2=A0 =C2=A0SUM Q*P_i*X_i

=C2=A0 =C2=A0 =C2=A0j=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0i

Constraint B:

SUM E_i*X_i <=3D D*SUM E_i

=C2=A0i=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 i

Constraints C_1 ... C_L

K_j >=3D SUM V_j_i*X_i - T=C2=A0 =C2=A0 =C2=A0 =C2=A0j in 1..L

=C2=A0 =C2=A0 =C2=A0 =C2=A0 i

T no explicit bound

0 <=3D X_i <=3D 1=C2=A0 =C2=A0i in 1..N

0 <=3D K_i=C2=A0 =C2=A0 =C2=A0 =C2=A0 i in 1..L

I suspect that with a bit of algrebra one

could get rid of the K_j's and T altogether.

That would leave the X_i's as the remaining variables.

The price would be an exponential number of constraints.

I'd expect the task of finding the most

violated constraint to not be very difficult.

No need to get rid of T.

Getting rid of the K_j's is easy:

Replace Constraint A and constraints C with

D:

T +=C2=A0 SUM=C2=A0 =C2=A0(SUM V_j_i*X_i - T)=C2=A0 <=3D SUM Q*P_i*X_i= =C2=A0 =C2=A0for all S subsetof 1..L

=C2=A0 =C2=A0 j in S=C2=A0 i in 1..N

This is 2**L constraints.

For given values of X and T,

a most violated is D_S with S =3D { j in 1..L: SUM V_j_i*X_i - T > 0 }

=C2=A0 A: Another thought, suppose that L=3D 1000, =
in the first iteration, we find that 500 K_j violat=
ed, we choose 100 most violated constraints of them as=C2=A0 new constraint=
s :

=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 K_j >=3D SUM V_j_i*X_i - T= =C2=A0 =C2=A0 =C2=A0 =C2=A0j in 1..100 (assume that j=3D1..100 are most vio= lated and j =3D1...500 are all the violated constraints)

=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 K_j >=3D SUM V_j_i*X_i - T= =C2=A0 =C2=A0 =C2=A0 =C2=A0j in 1..100 (assume that j=3D1..100 are most vio= lated and j =3D1...500 are all the violated constraints)

=C2=A0After solving the new LP model with new=
added constraints, we may find that some of the original K_j for j =3D501 =
to 1000 may become violated. So, how to assure that the number of violated =
constraints reducing efficiently is a bottle neck problem.

Any help would be appreciated.

=

Any help would be appreciated.

=

--

Michael=C2=A0 =C2=A0hennebry@web.cs.ndsu.NoDak.edu

"Sorry but your password must contain an uppercase letter, a number,

=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0--=C2= =A0 someeecards