+ Reply to Thread
Results 1 to 6 of 6

Simple example but Excel Solver can't find feasible solution

  1. #1
    Registered User
    Join Date
    05-23-2023
    Location
    Seoul
    MS-Off Ver
    2016
    Posts
    4

    Simple example but Excel Solver can't find feasible solution

    I want to make a travel plan using Excel Solver to decide which city to visit in order and how long to stay.
    I'm going to leave from city A and come back to city A.

    Below table shows the airfare for moving from one city to another, and the cost of accommodation per day for staying in each city.
    aa.PNG

    Target(Blue cell): To minimize Total expense (N17)
    Cells to change(Green cells): Staying days in a city ($D$17:$F$19)

    For example, 9 in F17 cell means moving from A to C and staying in C for 9 days.
    'From count'(Column H) checks the number of departures from each city
    =COUNTIF(D18:G18,">0")

    'To count'(Row 22) checks number of times you arrive in each city
    =COUNTIF(D18:D21,">0")

    'necessary?'(Column K) checks if you have ever arrived in the city (because if you have arrived, you also have to leave)
    =HLOOKUP(C19,$D$17:$G$22,6,FALSE)

    Constraints include following
    -- We're not moving to the same city
    > D18 = 0
    > E19 = 0
    > F20 = 0
    > G21 = 0
    -- Number of staying should be an integer
    > D18:G21 = integer
    -- travel starts from city A
    > H18 = 1
    -- come back to city A
    > D22 = 1
    -- We're not going to stop by a city more than once
    > H19:H21 <= 1
    > E22:G22 <= 1
    -- if you have arrived in a city, you also have to leave
    > H19:H21 >= K19:K21
    -- Total staying days (except to come back to A and stay) should be 10
    > D26 = sum(E18:G21) = 10
    -- Total visiting cities (except A) should be 2
    > D27 = sum(E22:G22) = 2
    -- Number of days to return to A and stay at A is randomly specified as 1
    > D19:D21 <= 1

    I think the number shown on the screen would be the best travel plan. If I enter this number and run solver, I find a solution, but if I clear all the numbers and run it, I don't find a solution.

    I'd like to use this logic in five city examples, but Excel can't find a feasible solution even in this toy example.

    What's the reason and how can I make it work?

    I have attached the related Excel file.

    *I heard that solver does not recognize countif function, so I tried to use iferror instead of countif, but I also couldn't find a solution.(This is implemented in a separate sheet of the attached file.)

    sample_problem.xlsx
    Last edited by dms_gg; 05-24-2023 at 01:46 AM.

  2. #2
    Registered User
    Join Date
    12-30-2021
    Location
    Toronto
    MS-Off Ver
    365
    Posts
    51

    Re: Simple example but Excel Solver can't find feasible solution

    I am not sure solver can deal with countif or iferror functions. First of all, once we know which cities should be visited, the problem is trivial.
    For example, if you are sure that cities A and B should be visited and the total stay is 10 days, then it is clear that you will stay 9 days in city C and 1 day
    in city B. In general, if you know which m cities to visit and the total days of stay, the problem is trivial. Now Suppose that you need visit m cities and
    come back to city A. This problem is the Traveling Salesman Problem, which is NP-hard. You need to incorporate the subtour elimination constraints. If your problem
    size is small, you can solve it optimally. Here is my thought on using either EXCEL or Python: Suppose that you have n cities in the pool and need to visit
    m (m<=n) cities. For each possible m cities (there are n!/m!(n-m)! cases), solve the Traveling Salesman Problem. Then find the minimal total cost which includes
    the stay plan. The grand minimal total cost will be the solution to your original problem.

  3. #3
    Forum Expert
    Join Date
    01-25-2011
    Location
    Belgium, Alveringem
    MS-Off Ver
    Excel 2003, 2007, 365
    Posts
    1,418

    Re: Simple example but Excel Solver can't find feasible solution

    like this, with binary values instead of integer
    Attached Files Attached Files
    Remember, saying thanks only takes a second or two. Click the little star * below, to give some Rep if you think an answer deserves it.

  4. #4
    Registered User
    Join Date
    05-23-2023
    Location
    Seoul
    MS-Off Ver
    2016
    Posts
    4

    Re: Simple example but Excel Solver can't find feasible solution

    That's an amazing idea.
    You solved my problem very clearly.
    Thanks a lot.
    Have a nice day

  5. #5
    Registered User
    Join Date
    05-23-2023
    Location
    Seoul
    MS-Off Ver
    2016
    Posts
    4

    Re: Simple example but Excel Solver can't find feasible solution

    I heard about TSP for the first time and it's very similar to my problem.
    The way to solve the TSP seems to be easily searched, so I think I can approach my problem a little differently and solve it.
    Thank you very much.

  6. #6
    Registered User
    Join Date
    12-30-2021
    Location
    Toronto
    MS-Off Ver
    365
    Posts
    51

    Re: Simple example but Excel Solver can't find feasible solution

    I believe that solving TSPs is the only way to solve your problem correctly in general. In order to test your EXCEL model, suppose that you need to visit cities B, C, and D. You may make city B is very close to city A, but far away from cities C and D. Check if your solution is A-B-A and C-D-C.

+ Reply to Thread

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Similar Threads

  1. [SOLVED] Simple example but Excel Solver can't find feasible solution
    By dms_gg in forum Excel Formulas & Functions
    Replies: 1
    Last Post: 05-25-2023, 01:07 AM
  2. Overriding Solver "Could not find feasible solution" in VBA?
    By orchemistral in forum Excel General
    Replies: 5
    Last Post: 06-24-2019, 03:59 PM
  3. Problem with Solver: "Can't find a feasible solution"
    By whoamiquestionmark in forum Excel General
    Replies: 7
    Last Post: 10-23-2017, 12:58 PM
  4. Replies: 11
    Last Post: 10-30-2013, 02:11 PM
  5. Replies: 2
    Last Post: 09-04-2013, 08:36 PM
  6. [SOLVED] Solver macro... bypass no feasible solution popup
    By Cicada in forum Excel Programming / VBA / Macros
    Replies: 1
    Last Post: 04-25-2012, 05:28 PM
  7. [SOLVED] Why is excel solver saying that there is not a feasible solution?
    By jt13 in forum Excel Programming / VBA / Macros
    Replies: 1
    Last Post: 01-17-2006, 01:30 PM

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts

Search Engine Friendly URLs by vBSEO 3.6.0 RC 1