Advanced Search

Carl Love

Carl Love

28045 Reputation

25 Badges

12 years, 333 days
Himself
Wayland, Massachusetts, United States
Contact Carl Love
My name was formerly Carl Devore.

MaplePrimes Activity


These are replies submitted by Carl Love

Replacement for ListTools:-Slice...

Carl Love 28045
December 21 2023
0 0

@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

Here is the fixed program...

Carl Love 28045
December 20 2023
0 0

@RukevweOyinloye Here is the fixed program. I changed X 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

Bug in my code...

Carl Love 28045
December 19 2023
0 0

@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. 

My crystal ball...

Carl Love 28045
December 19 2023
0 0

@sand15 This is the evidence for what I said, to wit, that the OP has conceptualized X 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.
     

With automatic partitioning...

Carl Love 28045
December 19 2023
0 0

@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

Quite plausible...

Carl Love 28045
December 19 2023
0 0

@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.

With the groups...

Carl Love 28045
December 19 2023
0 0

@RukevweOyinloye Okay, I think I have it. Please let me know if this worksheet does what you want. Please read the comments carefully. I implemented this so that the groups can be any partition of the profiles. They need not be contiguous or equally sized. The groups are now relevant, although the number of them is not. 

If the below is correct, then your error in the constraints was simply what I suggested before: You just needed to move the "= 1" to the inner add.

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:
#a partition of {1..numprofiles} into groups,
#each with a trivial name:
groups:= table(["A"=(1,2), "B"=(3,4)]):
#In general, it'd be good to verify that it's a partition,
#but I skip that for now.

# Decision variables:
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= entries(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,g in eval(groups) do
    printf("Group %s:\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]);

Matrix(4, 3, {(1, 1) = x[1, 1], (1, 2) = x[1, 2], (1, 3) = x[1, 3], (2, 1) = x[2, 1], (2, 2) = x[2, 2], (2, 3) = x[2, 3], (3, 1) = x[3, 1], (3, 2) = x[3, 2], (3, 3) = x[3, 3], (4, 1) = x[4, 1], (4, 2) = x[4, 2], (4, 3) = x[4, 3]})

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[3, 1]+x[4, 1] = 1, (2) = x[3, 2]+x[4, 2] = 1, (3) = x[3, 3]+x[4, 3] = 1, (4) = x[1, 1]+x[2, 1] = 1, (5) = x[1, 2]+x[2, 2] = 1, (6) = x[1, 3]+x[2, 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]]

Matrix(%id = 36893490538316452556)

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

Group A:
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 MiinimaxILP.mw

I see no rand...

Carl Love 28045
December 19 2023
0 0

@mmcdara The OP's code---posted in the Question---has no occurence of rand. The code is

X:= Array(1..num_profiles, 1..num_websites, datatype= integer[0..1]);

It's obvious (to me at least) that this is intended to be an array of the (necessarily symbolic) decision variables. The OP's conceptual error is trying to impose a numeric datatype on symbolic variables. The syntactic error is that although integer[0..1] is indeed a valid type, datatype treats integer as a special keyword value, and it expects a number of bytes in the square brackets. It's totally understandable that a newbie would make either of these errors.

I made it a matrix just for convenience, and the x could be any unassigned symbol.

Definitely a bug...

Carl Love 28045
December 19 2023
0 0

@Thomas Dean I found definitive proof that the way that until handles FAIL is a bug. The help page ?do has this paragraph:

  • The expr in the until clause is a Boolean expression, which must evaluate to true, false, or FAIL;  otherwise, an error occurs. The repetition statement is terminated when the result is true.

Can you formulate it algebraically?...

Carl Love 28045
December 19 2023
0 0

@RukevweOyinloye Yes, that's what I thought: that something was missing. Yet I'm certain that my code has the same mathematical information as your code (same objective and constraints); I just made it linear. But I realize that neither of these codes captures the essence of your verbal description of the problem. Can you formulate algebraically some constraints to capture the role of groups? Perhaps you meant for the "... = 1" on the constraints to be attached to the inner add, thus making 6 constraints in this case rather than 3?

Please also see the similar Reply that I posted in the subthread under the main Question a few minutes ago.

Please further explain the "groups"...

Carl Love 28045
December 19 2023
0 0

I notice from both your code and text that the "profiles" are partitioned into "groups", and also that the number of groups is irrelevant to this code because each constraint is simply the sum of a complete column of the decision-variable matrix X equated to 1. So, do you think that you need more constraints tthat use the groups?

Is there any real-world reason why the groups would be the same size? It would very easy to recode this so that the groups could be an arbitrary partition of the profiles rather than a partition into equal size blocks.

Something special about RootOf?...

Carl Love 28045
December 19 2023
0 0

@acer It seems quite odd to me that indets is "smart enough" to avoid returning bound variables from RootOf, yet it doesn't do it for Int, int, Sum, sum, or any other standard command with a bound variable that I can find. The bound variables of ints and sums are often automatically generated by dsolve and other commands. One often sees _a, _k1, etc.

Do you have any idea why indets gives special treatment to RootOf like this?

I've long thought that symbolic computation needs a formal way to declare a variable as bound.  

Confusing syntax...

Carl Love 28045
December 19 2023
0 0

@TKChang99 The syntax Surface(...) certainly makes it seem as if Surface is a separate command (with its own help page) rather than simply an option to SurfaceInt, so it's no surprise that there was that confusion. The standard syntax for an option would be Surface= [...], and I can't see any good reason why the integration commands in VectorCalculus couldn't use this more-standard syntax.

Streamlined version...

Carl Love 28045
December 19 2023
0 0

@RukevweOyinloye Here is a more-streamlined version of code that does exactly the same thing. While writing this code, I noticed that num_groups is irrelevant for this presumably toy example. Either I'm missing something, or its relevance won't become apparent until the example is more complicated.

> 

restart
:
> 

num_profiles:= 4:  num_websites:= 3:
X:= Matrix((num_profiles, num_websites), symbol= x);
objs:= seq(ArrayTools:-AddAlongDimension(X,2)):
'objs' = <objs>;
constraints:=
    seq(ArrayTools:-AddAlongDimension(X,1)) =~ 1,
    z >=~ objs
:
'constraints' = <constraints>;
sol:= Optimization:-Minimize(
    z, {constraints}, integervariables= {z}, binaryvariables= {seq}(X)
);
optimal_assignment:= eval(X, sol[2]);
for ij in op(2, optimal_assignment) do
    printf("Profile %d assigned to Website %d.\n", lhs(ij))
od;
printf("Objective Value (Minimized Maximum Website Overlap): %d.\n", sol[1]);

Matrix(4, 3, {(1, 1) = x[1, 1], (1, 2) = x[1, 2], (1, 3) = x[1, 3], (2, 1) = x[2, 1], (2, 2) = x[2, 2], (2, 3) = x[2, 3], (3, 1) = x[3, 1], (3, 2) = x[3, 2], (3, 3) = x[3, 3], (4, 1) = x[4, 1], (4, 2) = x[4, 2], (4, 3) = x[4, 3]})

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(7, {(1) = x[1, 1]+x[2, 1]+x[3, 1]+x[4, 1] = 1, (2) = x[1, 2]+x[2, 2]+x[3, 2]+x[4, 2] = 1, (3) = x[1, 3]+x[2, 3]+x[3, 3]+x[4, 3] = 1, (4) = x[1, 1]+x[1, 2]+x[1, 3] <= z, (5) = x[2, 1]+x[2, 2]+x[2, 3] <= z, (6) = x[3, 1]+x[3, 2]+x[3, 3] <= z, (7) = x[4, 1]+x[4, 2]+x[4, 3] <= z}))

sol := [1, [z = 1, x[1, 1] = 0, x[1, 2] = 0, x[1, 3] = 0, x[2, 1] = 0, 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] = 0, x[4, 3] = 0]]

Matrix(%id = 36893490538334837084)

Profile 2 assigned to Website 2.
Profile 3 assigned to Website 3.
Profile 4 assigned to Website 1.
Objective Value (Minimized Maximum Website Overlap): 1.

NULL

Download firstworkablecode.mw

X is array of decision variables...

Carl Love 28045
December 19 2023
0 0

@mmcdara X is the array of binary decision variables such that X[i,j] = 1 iff profile i should be assigned to website j. It shouldn't have a numeric datatype.

First 26 27 28 29 30 31 32 Last Page 28 of 709