Carl Love

Carl Love

26386 Reputation

25 Badges

11 years, 140 days
Himself
Wayland, Massachusetts, United States
My name was formerly Carl Devore.

MaplePrimes Activity


These are replies submitted by Carl Love

It goes without saying that it's impossible to Answer your Question if you don't post the code. As a worksheet showing a timed example would likely be best.

@mmcdara Here's an example to show the multi-argument capability of ~, which would be quite awkward  to duplicate with map:

f~([a,b], X*Y, [c,d], [1,2]);
               [f(a, X Y, c, 1), f(b, X Y, d, 2)]

Here is, I believe, the only situation where ~ and map are equivalent: Let be an object of one of the four basic container types that I mentioned in my last Reply. Let a1, a2, ..., ak be a sequence (possibly empty) of additional arguments, none of which are of any of those container types. Then map(f, La1a2, ..., ak= f~(L, a1, a2, ..., ak). (Both map and ~ can be overloaded by object methods, which can alter those rules somewhat.)

Regarding map(f, Lversus map(x-> f(x), L): They produce the same result, but the former is more efficient, and can be much more efficient some cases, such as when f is a builtin command. In most cases (whether or not map is involved), (x-> f(x)) can be replaced by simply f, and it's more efficient to do so.

@nm Are you saying that in some earlier version of Maple, solve needed the parametric option to solve that pair of linear equations? I find that hard to believe. Indeed, one can get the solutions symbolically for uninstantiated initial conditions:

sol:= <c1,c2>^+.(<3,-1> +~ exp(4*t))/4/exp(t):
ICsol:= solve(eval([y(t) = sol, D(y)(t) = diff(sol,t)], t= t0), [c1,c2]);
simplify(eval(ICsol, [t0, y(t0), D(y)(t0)]=~ [4, -3, -17]));

The elementwise operator ~ affects only arguments that are specific types of containers: lists, sets, rtables, and tables. For other types of arguments, such as your `*`, it's simply ignored. So, your issue is only with simplify; the simplify~ is correctly passing it's argument to simplify. Note that ~ is not simply an abbreviation for map; it simultaneously applies to all arguments of those container types (tables are handled a bit differently).

I am by no means denying that your point about simplify itself is interesting.

@RukevweOyinloye For the follwing discussion, let

  • = number of profiles,
  • = number of groups,
  • = number of websites.

So for the toy problem, [P,G,W] [4,2,3], and for the larger problem [256, 16, 103].

Let's consider the size of the coefficient matrix needed to apply the simplex algorithm to the continuous LP (Linear Program) subproblem of the larger ILP (Integer LP). There are P*W binary decision variables. The number of inequality constraints is P, so there are slack variables, and we add 1 artificial variable, z, so the total number of variables is 1 + P + P*W. There's 1 column for the constants, so the matrix has 2 + P + P*W columns. The number of equality constraints is G*W. There's 1 objective row. So the number of rows is 1 + P + G*W. The number of matrix entries is thus (1 + P + G*W)*(2 + P + P*W) = 50722530 ~ 51 million.

That's a lot of entries; however, the problem is quite sparse. Let's count the nonzero entries in the initial matrix. (A variable's value being zero is irrelevant to this; we're only interested in the variables' coefficients and the constant terms.) Each equality constraint has P/G + 1 terms. Each inequality constraint has W + 2 terms. The objective row has 2 terms. So the total nonzero terms is (P/G + 1)*G*W + (W + 2)*P + 2 =  54898. So the proportion of nonzero entries is 54998/50722630 ~ 0.001, which is very sparse. But special syntax is needed to get the solver to make efficient  use of that sparsity..

@C_R I don't undestand your suggestion from your 3rd paragraph. Why would it be any easier to obtain an older version?

@RukevweOyinloye You mentioned wanting to extend this to 256 profiles in 16 groups. How many websites would there be?

Just a curiosity at this point: That mysterious r shows up in the result of an example on help page ?linalg,eigenvectors with no explanation in the help page text. I guess it's an escaped local of a procedure called by linalg[eigenvectors]. Anyway, there's likely little point in investigating it further as that code has been obsolete for more than 20 years.

This isn't related to your crashed kernel, but I thought that you'd like to know how to do the type of polynomial factoring that you were attempting in the first section of your worksheet:

evala(AFactor(x^2+2));

@RukevweOyinloye I think that all of the errors are due to the first error, the absence of ListTools:-Slice in your version of Maple. Here's a replacement:

A combinatorial minimax-optimal matching problem formulated and solved as an Integer Linear Program

Author: Carl Love <carl.j.love@gmail.com> 2023-Dec-19

 

restart
:

#Utility procedure to replace ListTools:-Slice:
Slice:= proc(L::list, d::posint)
local r, q:= iquo(nops(L), d, r), k;
    seq(L[(k-1)*(q+1)+1..k*(q+1)], k= 1..r),
    seq(L[r*(q+1)+(k-1)*q+1..r*(q+1)+k*q], k= 1..d-r)
end proc
:

# Given data:
num_websites:= 3:  num_profiles:= 4:  num_groups:= 2:

# Partition profiles into groups:
groups:= (g-> g[1]..g[-1])~([Slice]([$1..num_profiles], num_groups));

# Decision variables:
#x[i,j] will be 1 if profile i is optimally assigned to website j, 0 otherwise.
X:= Array((1..num_profiles, 1..num_websites), (i,j)-> x[i,j]):

# Objective:
#The objective (as I understand it) is to minimize the maximum
#correspondence between a profile and a website. Translated to
#abstract math, that means minimizing the maximum row sum of X.
objs:= seq(add(X[i]), i= 1..num_profiles):  #row sums
'objs' = <objs>;  #just for neat display

# Constraints:
constraints:=
    #exactly 1 member of each group per website:
    #column sums of rows partitioned by group:
    seq(seq(add(X[g,j]) =~ 1, j= 1..num_websites), g= groups),

    #z is an added "artificial" variable to facilitate linearizing
    #the minimax objective:
    z >=~ objs  #i.e., z >= max(objs)
:
'constraints' = <constraints>;  #just for neat display

# Solve:
sol:= Optimization:-Minimize(
    z, {constraints}, integervariables= {z}, binaryvariables= {seq}(X)
);

# Display results:
optimal_assignment:= eval(X, sol[2]);
for g in groups do
    printf("Group %d..%d:\n", op(g));
    for ij in op(3, optimal_assignment[g]) do
        printf("Profile %d assigned to Website %d.\n", lhs(ij))
    od;
    printf("\n")  #blank line to separate groups
od;
printf("Objective Value (Minimized Maximum Website Overlap): %d\n", sol[1]);

groups := [1 .. 2, 3 .. 4]

objs = (Vector(4, {(1) = x[1, 1]+x[1, 2]+x[1, 3], (2) = x[2, 1]+x[2, 2]+x[2, 3], (3) = x[3, 1]+x[3, 2]+x[3, 3], (4) = x[4, 1]+x[4, 2]+x[4, 3]}))

constraints = (Vector(10, {(1) = x[1, 1]+x[2, 1] = 1, (2) = x[1, 2]+x[2, 2] = 1, (3) = x[1, 3]+x[2, 3] = 1, (4) = x[3, 1]+x[4, 1] = 1, (5) = x[3, 2]+x[4, 2] = 1, (6) = x[3, 3]+x[4, 3] = 1, (7) = x[1, 1]+x[1, 2]+x[1, 3] <= z, (8) = x[2, 1]+x[2, 2]+x[2, 3] <= z, (9) = x[3, 1]+x[3, 2]+x[3, 3] <= z, (10) = x[4, 1]+x[4, 2]+x[4, 3] <= z}))

sol := [2, [z = 2, x[1, 1] = 0, x[1, 2] = 0, x[1, 3] = 1, x[2, 1] = 1, x[2, 2] = 1, x[2, 3] = 0, x[3, 1] = 0, x[3, 2] = 0, x[3, 3] = 1, x[4, 1] = 1, x[4, 2] = 1, x[4, 3] = 0]]

Array(%id = 36893489983424648364)

Group 1..2:
Profile 1 assigned to Website 3.
Profile 2 assigned to Website 1.
Profile 2 assigned to Website 2.

Group 3..4:
Profile 3 assigned to Website 3.
Profile 4 assigned to Website 1.
Profile 4 assigned to Website 2.

Objective Value (Minimized Maximum Website Overlap): 2

 

NULL

Download MinimaxILP.mw

@RukevweOyinloye Here is the fixed program. I changed from a Matrix back to an Array because an extracted subMatrix (such as the rows belonging to a particular group of profiles) has its rows and columns re-indexed starting at 1. Re-indexing doesn't happen for Arrays. That was the "matrix-indexing idiosyncracy" that I mentioned yesterday.

A combinatorial minimax-optimal matching problem formulated and solved as an Integer Linear Program

Author: Carl Love <carl.j.love@gmail.com> 2023-Dec-19

 

restart
:

# Given data:
num_websites:= 3:  num_profiles:= 4:  num_groups:= 2:

# Partition profiles into groups:
groups:= (g-> g[1]..g[-1])~([ListTools:-Slice]([$1..num_profiles], num_groups));

# Decision variables:
#x[i,j] will be 1 if profile i is optimally assigned to website j, 0 otherwise.
X:= Array((1..num_profiles, 1..num_websites), (i,j)-> x[i,j]):

# Objective:
#The objective (as I understand it) is to minimize the maximum
#correspondence between a profile and a website. Translated to
#abstract math, that means minimizing the maximum row sum of X.
objs:= seq(add(X[i]), i= 1..num_profiles):  #
'objs' = <objs>; #just for neat display

# Constraints:
constraints:=
    #exactly 1 member of each group per website:
    #column sums of rows partitioned by group:
    seq(seq(add(X[g,j]) =~ 1, j= 1..num_websites), g= groups),

    #z is an added "artificial" variable to facilitate linearizing
    #the minimax objective:
    z >=~ objs  #i.e., z >= max(objs)
:
'constraints' = <constraints>;  #just for neat display

# Solve:
sol:= Optimization:-Minimize(
    z, {constraints}, integervariables= {z}, binaryvariables= {seq}(X)
);

# Display results:
optimal_assignment:= eval(X, sol[2]);
for g in groups do
    printf("Group %a:\n", g);
    for ij in op(3, optimal_assignment[g]) do
        printf("Profile %d assigned to Website %d.\n", lhs(ij))
    od;
    printf("\n")  #blank line to separate groups
od;
printf("Objective Value (Minimized Maximum Website Overlap): %d.\n", sol[1]);

groups := [1 .. 2, 3 .. 4]

objs = (Vector(4, {(1) = x[1, 1]+x[1, 2]+x[1, 3], (2) = x[2, 1]+x[2, 2]+x[2, 3], (3) = x[3, 1]+x[3, 2]+x[3, 3], (4) = x[4, 1]+x[4, 2]+x[4, 3]}))

constraints = (Vector(10, {(1) = x[1, 1]+x[2, 1] = 1, (2) = x[1, 2]+x[2, 2] = 1, (3) = x[1, 3]+x[2, 3] = 1, (4) = x[3, 1]+x[4, 1] = 1, (5) = x[3, 2]+x[4, 2] = 1, (6) = x[3, 3]+x[4, 3] = 1, (7) = x[1, 1]+x[1, 2]+x[1, 3] <= z, (8) = x[2, 1]+x[2, 2]+x[2, 3] <= z, (9) = x[3, 1]+x[3, 2]+x[3, 3] <= z, (10) = x[4, 1]+x[4, 2]+x[4, 3] <= z}))

sol := [2, [z = 2, x[1, 1] = 0, x[1, 2] = 0, x[1, 3] = 1, x[2, 1] = 1, x[2, 2] = 1, x[2, 3] = 0, x[3, 1] = 0, x[3, 2] = 0, x[3, 3] = 1, x[4, 1] = 1, x[4, 2] = 1, x[4, 3] = 0]]

Array(%id = 36893490328587871284)

Group 1 .. 2:
Profile 1 assigned to Website 3.
Profile 2 assigned to Website 1.
Profile 2 assigned to Website 2.

Group 3 .. 4:
Profile 3 assigned to Website 3.
Profile 4 assigned to Website 1.
Profile 4 assigned to Website 2.

Objective Value (Minimized Maximum Website Overlap): 2.

 

Download MinimaxILP.mw

@RukevweOyinloye Sorry, there is a bug in my code. Please don't try to assess the code until I fix it. The bug is due to an idiosyncracy of Maple matrix indexing. It has nothing to do with the mathematical formulation of the problem. 

@sand15 This is the evidence for what I said, to wit, that the OP has conceptualized as the symbolic decision variables of the problem.

  1. The OP's code contains the line
    sol:= Optimization[Minimize](obj, constraints, assume= binary)
    So, the OP is trying to solve an Integer Program with all binary variables.
  2. The OP assigns no values whatsoever, neither numeric nor symbolic, to any entry of X.
  3. The only things that look remotely like decision variables are the X[i,j]s used in the lines defining obj and constraints.
  4. obj and constraints are in algebraic form (rather than procedural), so we're required to have symbolic decision variables.
     

@RukevweOyinloye Okay, this version automatically partitions the profiles into num_groups groups. It's not necessary that num_groups evenly divides num_profiles. If it doesn't, the groups will be sized as evenly as possible, with a maximum size difference of 1.

A combinatorial minimax-optimal matching problem formulated and solved as an integer linear program

Author: Carl Love <carl.j.love@gmail.com> 2023-Dec-19

 

restart
:

# Given data:
num_websites:= 3:  num_profiles:= 4:  num_groups:= 2:

# Partition profiles into groups:
groups:= (g-> g[1]..g[-1])~([ListTools:-Slice]([$1..num_profiles], num_groups));

# Decision variables:
#x[i,j] will be 1 if profile i is optimally assigned to website j, 0 otherwise.
X:= Matrix((num_profiles, num_websites), symbol= x):

# Objective:
#The objective (as I understand it) is to minimize the maximum
#correspondence between a profile and a website. Translated to
#abstract math, that means minimizing the maximum row sum of X.
objs:= seq(ArrayTools:-AddAlongDimension(X,2)):  #row sums
'objs' = <objs>:  #just for neat display

# Constraints:
constraints:=
    #exactly 1 member of each group per website:
    #column sums of rows partitioned by group:
    seq(seq(ArrayTools:-AddAlongDimension(X[g],1)) =~ 1, g= groups),

    #z is an added (artificial) variable to facilitate linearizing
    #the minimax objective:
    z >=~ objs  #i.e., z >= max(objs)
:
'constraints' = <constraints>:  #just for neat display

# Solve:
sol:= Optimization:-Minimize(
    z, {constraints}, integervariables= {z}, binaryvariables= {seq}(X)
);

# Display results:
optimal_assignment:= eval(X, sol[2]);
for g in groups do
    printf("Group %a:\n", g);
    for ij in op(2, optimal_assignment[g]) do
        printf("Profile %d assigned to Website %d.\n", lhs(ij))
    od;
    printf("\n")  #blank line to separate groups
od;
printf("Objective Value (Minimized Maximum Website Overlap): %d.\n", sol[1]);

groups := [1 .. 2, 3 .. 4]

sol := [2, [z = 2, x[1, 1] = 0, x[1, 2] = 0, x[1, 3] = 1, x[2, 1] = 1, x[2, 2] = 1, x[2, 3] = 0, x[3, 1] = 0, x[3, 2] = 0, x[3, 3] = 1, x[4, 1] = 1, x[4, 2] = 1, x[4, 3] = 0]]

Matrix(%id = 36893490259323885556)

Group 1 .. 2:
Profile 1 assigned to Website 3.
Profile 2 assigned to Website 1.
Profile 2 assigned to Website 2.

Group 3 .. 4:
Profile 1 assigned to Website 3.
Profile 2 assigned to Website 1.
Profile 2 assigned to Website 2.

Objective Value (Minimized Maximum Website Overlap): 2.

 

NULL

Download MinimaxILP.mw

@acer Thanks. Your reasoning seems quite plausible to me, and I'm satisfied with your explanation.

Now, if we had formally declared bound variables, they could be easily filtered out.

4 5 6 7 8 9 10 Last Page 6 of 687