skip to Main Content

I have a python constraint problem like this:
You need to make a schedule for the presentation of papers for a conference. A total of 10 papers from several fields are to be presented at the conference: Artificial Intelligence (AI), Machine Learning (ML) and Natural Language Processing (NLP). Your task is to make a schedule for a conference by dates, taking into account the following constraints:
A maximum of 4 papers can be presented in each term.
If the number of papers from a given area is less than or equal to the maximum number of papers that can be presented in a given term, then those papers should be distributed in the same term. And i have this code:

from constraint import *

def domain_length(domain):
    return len(domain) < 4

if __name__ == '__main__':
    num_terms = int(input())

    papers = dict()

    paper_info = input()
    while paper_info != 'end':
        title, topic = paper_info.split(' ')
        papers[title] = topic
        paper_info = input()

    # Define variables
    variables = list(papers.keys())
    domain = [f'T{i + 1}' for i in range(num_terms)]

    problem = Problem(BacktrackingSolver())

    # Add variables to problem
    problem.addVariables(variables, domain)

    # Add constraints
    for area in ['AI', 'ML', 'NLP']:
        area_papers = [title for title, topic in papers.items() if topic == area]
        area_num_papers = len(area_papers)

        if area_num_papers <= 4:
            # If there are fewer papers than the number of terms, assign them to different terms
            problem.addConstraint(AllEqualConstraint(), area_papers)
        else:
            # Otherwise, assign papers to non-overlapping sets of terms
            papers_sets = [area_papers[i:i + 4] for i in range(0, area_num_papers, 4)]
            for papers_set in papers_sets:
                # Add constraints to ensure each set is assigned to a different term
                problem.addConstraint(AllDifferentConstraint(), papers_set)

                # Add constraints to ensure no more than 4 papers are assigned to each term
                for term in domain:
                    problem.addConstraint(lambda *papers, t=term: sum(1 for p in papers if p == t) <= 4, papers_set)

    # Add constraint for maximum of 4 papers per term
    for term in domain:
        problem.addConstraint(lambda *papers, t=term: sum(1 for p in papers if p == t) <= 4, variables)

    result = problem.getSolution()

    # Print solution
    for paper, term in result.items():
        print(f"{paper} ({papers[paper]}): {term}")

The code works properly when there are not more than 4 papers from topic. Now the problem is that the code doesn’t find a solution when there are more than 4 papers from a specific topic. For example, if there are 6 AI papers, it prints no solution, where it should. The line that handles these cases:

papers_sets = [area_papers[i:i + 4] for i in range(0, area_num_papers, 4)]

Separates the papers correctly like in the sample output, but then i think there is a problem with the constraint:

for papers_set in papers_sets:
                # Add constraints to ensure each set is assigned to a different term
                problem.addConstraint(AllDifferentConstraint(), papers_set)

because it doesn’t find any solution. What could be the problem?
Here is a sample input and output:

Input:
3
Paper1 AI
Paper2 AI
Paper3 AI
Paper4 AI
Paper5 NLP
Paper6 AI
Paper7 NLP
Paper8 NLP
Paper9 NLP
Paper10 NLP
end
Output:
Paper1 (AI): T3
Paper2 (AI): T3
Paper3 (AI): T3
Paper4 (AI): T2
Paper5 (NLP): T2
Paper6 (AI): T2
Paper7 (NLP): T2
Paper8 (NLP): T1
Paper9 (NLP): T1
Paper10 (NLP): T3

Please signup or login to give your own answer.
Back To Top
Search