Carl Love

Carl Love

26386 Reputation

25 Badges

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

MaplePrimes Activity


These are replies submitted by Carl Love

@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

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

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

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

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.

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

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

@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

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

@RukevweOyinloye One thing that you certainly must do is remove the minimize from the objective function. The Optimization[Minimize] already specifies that you want to minimize.

You probably have other problems also, which'll be easier to diagnose when you upload a worksheet.

@nm That _Z is the bound variable of RootOf​​​​​, and every RootOf has a _Z, so you'd might as well just filter out all occurences of RootOf. That _Z is very different from the free variables returned by discontsolve, etc., that you're otherwise looking for.

@Carl Love Some commands may also return unknown functions, such as _F(x, y). For example, pdsolve might do this. These can be filtered by type typefunc(suffixed('_')) as the 2nd indets argument. To filter both symbols and functions, make the type 

{thistype, typefunc}(suffixed('_'))

To filter indexed names as well, make it

{thistype, typefunc, typeindex}(suffixed('_'))

@Thomas Dean You can use until testeq(...)=FAIL instead of the overly complicated 
until evalb(testeq(...)=FAIL).

@Thomas Dean Sorry, you were right; there is a difference. I think that the presence of a difference in how while and until handle FAIL should be considered a bug in the implementation of until.

@Thomas Dean There is no difference in how ifwhile, and until interpret FAIL! They all interpret it the same as false.

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