Find out if a model is feasible or not

[Ben]

Hello,

I am programming a little sudoku solver&generator.

There are two situations when it can occur that I have an infeasible problem:
1. the user enters a wrong/unsolvable sudoku
2. during the generation process, when the field is filled with some random numbers at the beginning, it might cause an infeasibility, so that a correction is needed

I want to achieve, that AIMMS does not terminate the program, but in the 1. case gives a message to the user, and in the 2. case goes back/starts again with generating a new field.
I tried to work with a code like this for the generation. It shall check whether given random numbers can be filled to a sudoku, if not then it shall start again with some random numbers/alternatively go back and delete some numbers in the field

Valid_Solution_Found := 0;
while(not Valid_Solution_Found) do
        ! process a new selection of random numbers here, or a correction !
        Solve My_Sudoku_Program;
        if (My_Sudoku_Program.ProgramStatus = 'Optimal') then
            Valid_Solution_Found := 1;
            ! go on with the code here !
        else
            empty My_Solution(r,c,k);
            empty Some_Random_Numbers_On_A_Sudoku_Field(r,c);
        endif;
endwhile;

But this dos not work at all, I only get a message which constraints could not be satisfied and the execution of the program is terminated.

I am just a beginner with AIMMS, so I am not sure whether there is an easy way to do what I want. But I did not find a proper way how to easily check the feasibility of a given problem.

I hope someone can help me with that.

[Marcel Hunting]

Hi,

If the AIMMS generator detects that the problem is infeasible then AIMMS will, by default, generate an error message and halt the execution. You can try to disable some of the feasibility checks performed by the generator and see whether the run then continues if an instance is infeasible. To do so you have to switch off the following options: 'Row Range Violation Left Hand Side' and 'Warning Infeasible Row Col'.

Best regards,

Marcel Hunting

AIMMS Optimization Specialist

[Ben]

Hi,

thanks for your answer. But since I am an AIMMS beginner, I do not know where to find this option.

My error message ist this one:
The range of the left hand side of the "=" constraint C_Each_Value_Once_Per_Row(1,1) is [0, 7], and the right hand side of that constraint is -1; this constraint is infeasible.  See also option row_range_violation_left_hand_side.

I tried sth similar in the beer transport project from the beginner's tutorial. I set the supply of one plant to 0. Then I just get this message:
Warning: After six iterations CPLEX 12.6.3 concluded that LeastCostTransportationPlan is infeasible.
But the program is still running, it still performs calculation after the solving process.

The difference in my opinion is, that I have to work with the variable in my sudoku project. I have to set the .nonvar suffix to 1 for a specific number of values.

In addition to the upper two situations, I have a thirs one, more comlicated.
My algorithm works like this:
I have a filled field, which fulfills the rules of a sudoku. Then I want to delete one number (let's say the 6 in the 1st row and 1st column). But I want to check whether the resulting puzzle still has a unique solution. Therefore I want to check whether I can put any other number (1,2,3,4,5,7,8,9) in the empty field (1st row, 1st column) and still get a solution. If no, the puzzle is still unique and the process will go one with the next field. If there is a solution, the puzzle is not unique anymore and program has to go one step back, filling the field again with the original number.

Conclusion: I need a way to check my model, whether it is feasible, and I need a clear way to differ feasible and infeasible.
If I would disable these options, what would be the result? Would all infeasible models still be infeasible and all feasible ones still feasible?

Or is there any other way to check/try whether a problem is feasible or not?

Best regards,

Ben

[Marcel Hunting]

Hi,

These two options can be found in the Option Tree which can be opened by using Setting - Project Options from the menu bar. Inside the Option Tree you can search for both options in the search bar at the bottom.

Switching off these options does not change the feasibility/infeasibility of a model; it just changes which part in AIMMS will detect these kind of infeasibilities, namely the AIMMS generator or the solver (CPLEX). If it is the AIMMS generator then AIMMS will throw an error and halt the execution; if it is CPLEX then there is no error and the execution continues. Apparently you want the latter behavior.

Best regards,

Marcel