Почему Cplex предлагает решение со слабыми ограничениями? - PullRequest
Новая
       28

Почему Cplex предлагает решение со слабыми ограничениями?

0 голосов
/ 05 апреля 2019

Я разработал модель линейного математического программирования в Visual Studio (C ++) и решил проблему с помощью Cplex (12.7.1). Однако я заметил странное поведение Cplex. Для некоторых проблемных ситуаций Cplex предоставляет выполнимое (неоптимальное решение), которое можно легко улучшить, устраняя слабые места при определенных ограничениях. Упрощенный пример математической модели выглядит следующим образом:

Свернуть A

Подлежит

cX - dY <= A </p>

dY - cX <= A </p>

X, Y бинарный, непрерывный, c, d параметры

Учитывая значения X и Y в предоставленном возможном (неоптимальном) решении, ослабление обоих ограничений. Непрерывная переменная A может быть легко уменьшена с учетом значений переменных решения X и Y (то есть путем устранения ослабления хотя бы одного из двух ограничений). Я понимаю, что Cplex предоставляет решение, которое выполнимо, учитывая ограничения проблемы. Однако при ветвлении и решении симплекса в ветке для создания выполнимого решения, почему вычисление этого симплекса приводит к этим двум необязательным ограничениям? Что я могу сделать, чтобы Cplex всегда предоставлял хотя бы решение, в котором одно из этих двух ограничений является обязательным?

  • Я попытался включить решение без провисания, чтобы проверить, распознается ли Cplex как возможное решение как допустимое решение (т. Е. Чтобы проверить, не содержит ли математическая модель, запрограммированная в C ++, ошибки);
  • Я пытался увеличить допуски Cplex (IloCplex :: Param :: MIP :: Tolerances :: MIPGap);
  • Я попытался переключить динамический поиск Cplex (IloCplex :: Param :: MIP :: Strategy :: Search).

Ни одна из этих попыток не решила проблему. 

int nozones = 2;
int notrucks = 100;
int notimeslots = 24;
IloEnv env; 
IloModel model(env);
IloExpr objective(env);
IloExpr constraint(env);

NumVar3Matrix X(env, notimeslots);
for (i = 0; i < notimeslots; i++)
{
    X[i] = NumVarMatrix(env, notrucks);
    for (l = 0; l < notrucks; l++)
    {
        X[i][l] = IloNumVarArray(env, nozones);
        for (k = 0; k < nozones; k++)
        {
            X[i][l][k] = IloNumVar(env, 0, 1, ILOINT);
        }
    }
}

NumVar3Matrix A(env, nozones);
for (k = 0; k < nozones; k++)
{
    A[k] = NumVarMatrix(env, notimeslots);
    for (int i0 = 0; i0 < notimeslots; i0++)
    {
        A[k][i0] = IloNumVarArray(env, notimeslots);
        for (int i1 = 0; i1 < notimeslots; i1++)
        {
            A[k][i0][i1] = IloNumVar(env, 0, 9999, ILOFLOAT); 
        }
    }
}

//objective function
for (int k0 = 0; k0 < nozones; k0++)
{
    for (int i0 = 0; i0 < notimeslots; i0++)
    {
        for (int i1 = 0; i1 < notimeslots; i1++)
        {
            if (i0 > i1)
            {
                double denominator = (PP.mean[k0] * (double)(notimeslots*notimeslots)); //parameter
                objective += A[k0][i0][i1] / denominator;
            }
        }
    }
}

model.add(IloMinimize(env, objective)); 

//Constraints
for (int k0 = 0; k0 < nozones; k0++)
{
    for (int i0 = 0; i0 < notimeslots; i0++)
    {
        for (int i1 = 0; i1 < notimeslots; i1++)
        {
            if (i0 > i1)
            {
                for (int l0 = 0; l0 < notrucks; l0++)
                {
                    constraint += c[k0][l0] * X[i0][l0][k0];
                    constraint -= d[k0][l0] * X[i1][l0][k0];    
                }

                constraint -= A[k0][i0][i1];
                model.add(constraint <= 0);
                constraint.clear();

                for (int l0 = 0; l0 < notrucks; l0++)
                {
                    constraint -= c[k0][l0] * X[i0][l0][k0];
                    constraint += d[k0][l0] * X[i1][l0][k0];                
                }
                constraint -= A[k0][i0][i1];
                model.add(constraint <= 0);
                constraint.clear();
            }
        }
    }
}

Пожалуйста, найдите журнал ниже: 

CPXPARAM_TimeLimit                               10
CPXPARAM_Threads                                 3
CPXPARAM_MIP_Tolerances_MIPGap                   9.9999999999999995e-08
CPXPARAM_MIP_Strategy_CallbackReducedLP          0
Tried aggregator 2 times.
MIP Presolve eliminated 412 rows and 384 columns.
MIP Presolve modified 537 coefficients.
Aggregator did 21 substitutions.
Reduced MIP has 595 rows, 475 columns, and 10901 nonzeros.
Reduced MIP has 203 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.09 sec. (8.97 ticks)
Found incumbent of value 1254245.248934 after 0.11 sec. (10.55 ticks)
Probing time = 0.00 sec. (0.39 ticks)
Tried aggregator 1 time.
Reduced MIP has 595 rows, 475 columns, and 10901 nonzeros.
Reduced MIP has 203 binaries, 272 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.03 sec. (4.47 ticks)
Probing time = 0.00 sec. (0.55 ticks)
Clique table members: 51.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 3 threads.
Root relaxation solution time = 0.05 sec. (15.41 ticks)

    Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

*     0+    0                      1254245.2489    13879.8564            98.89%
*     0+    0                      1225612.3997    13879.8564            98.87%
*     0+    0                      1217588.5782    13879.8564            98.86%
*     0+    0                      1209564.7566    13879.8564            98.85%
*     0+    0                      1201540.9350    13879.8564            98.84%
*     0+    0                      1193517.1135    13879.8564            98.84%
*     0+    0                      1185493.2919    13879.8564            98.83%
*     0+    0                      1177589.9029    13879.8564            98.82%
      0     0   334862.8273   139  1177589.9029   334862.8273      387   71.56%
*     0+    0                       920044.8009   334862.8273            63.60%
      0     0   335605.5047   162   920044.8009     Cuts: 248      516   63.52%
*     0+    0                       732802.2256   335605.5047            54.20%
*     0+    0                       669710.6005   335605.5047            49.89%
      0     0   336504.5144   153   669710.6005     Cuts: 248      617   49.75%
      0     0   338357.1160   172   669710.6005     Cuts: 248      705   49.48%
      0     0   338950.0580   178   669710.6005     Cuts: 248      796   49.39%
      0     0   339315.6848   189   669710.6005     Cuts: 248      900   49.33%
      0     0   339447.9616   193   669710.6005     Cuts: 248      977   49.31%
      0     0   339663.6342   203   669710.6005     Cuts: 228     1091   49.28%
      0     0   339870.9021   205   669710.6005     Cuts: 210     1154   49.25%
*     0+    0                       531348.6042   339870.9021            36.04%
      0     0   340009.1008   207   531348.6042     Cuts: 241     1225   35.87%
      0     0   340855.1873   202   531348.6042     Cuts: 231     1318   35.85%
      0     0   341229.8328   202   531348.6042     Cuts: 248     1424   35.78%
      0     0   341409.5769   200   531348.6042     Cuts: 248     1502   35.75%
      0     0   341615.2848   286   531348.6042     Cuts: 248     1568   35.71%
      0     0   341704.8400   300   531348.6042     Cuts: 225     1626   35.69%
      0     0   341805.5681   222   531348.6042     Cuts: 191     1687   35.67%
*     0+    0                       489513.3319   341805.5681            30.17%
      0     0   341834.6048   218   489513.3319     Cuts: 169     1739   30.17%
      0     0   341900.1390   228   489513.3319     Cuts: 205     1788   30.16%
      0     0   341945.8278   211   489513.3319     Cuts: 197     1855   30.15%
*     0+    0                       489468.1697   341945.8278            30.14%
      0     2   341945.8278   202   489468.1697   341945.8278     1855   30.14%
Elapsed time = 5.53 sec. (446.68 ticks, tree = 0.01 MB, solutions = 14)
*   199+  154                       484741.1904   341968.3817            29.45%
    263   222   342462.1403   198   484741.1904   341968.3817    12287   29.45%
*   550+  420                       461678.3486   341993.1725            25.92%
    555   403   411858.3790   117   461678.3486   341993.1725    21480   25.92%
*   566+  319                       439985.4277   341993.1725            22.27%
    660   321   350009.7742   289   439985.4277   341993.1725    16141   22.27%
*   670+  427                       438464.9662   342020.7550            22.00%

Flow cuts applied:  15
Mixed integer rounding cuts applied:  65
Zero-half cuts applied:  6
Gomory fractional cuts applied:  15

Root node processing (before b&c):
  Real time             =    5.53 sec. (446.21 ticks)
Parallel b&c, 3 threads:
  Real time             =    4.50 sec. (1093.39 ticks)
  Sync time (average)   =    0.59 sec.
  Wait time (average)   =    0.04 sec.
                         ------------
Total (root+branch&cut) =   10.03 sec. (1539.61 ticks)

Ожидаемый результат состоит в том, что во всех возможных решениях, которые предоставляет Cplex, для всех пар ограничений, которые хотя бы на одном из них являются обязательными (без провисания).

Ответы [ 2 ]

2 голосов
/ 10 апреля 2019

Я предполагаю, что CPLEX прервана из-за превышения вашего лимита времени, поэтому решение не оказалось оптимальным. Это правильно?

Это не ошибка. CPLEX не дает таких гарантий для запуска, завершенного пользователем. CPLEX останавливается как можно скорее, когда найдено решение, удовлетворяющее запросам / настройкам пользователя.

Чтобы получить поведение, которое вы ищете, в C API вы можете использовать:

https://www.ibm.com/support/knowledgecenter/en/SSSA5P_12.9.0/ilog.odms.cplex.help/CPLEX/UsrMan/topics/discr_optim/mip/para/51_soln_fixed.html

для решения исправленной проблемы. Поскольку полученная проблема - чистый LP, теперь вы можете позвонить:

  • CPXlpopt (), который решает этот фиксированный LP
  • запрос двойных и т. Д. Из LP решить.

И, как уже упоминалось в ссылке, вы можете использовать solveFixed () для API более высокого уровня.

Даниэль также ответил на ваш кросс-пост здесь:

https://developer.ibm.com/answers/questions/499882/why-does-cplex-provide-feasible-solutions-with-con/

https://developer.ibm.com/answers/questions/499879/why-does-cplex-provide-slack-on-constraints-when-p/

Пожалуйста, ответьте на форуме разработчиков IBM, если что-то не понятно, спасибо.

0 голосов
/ 06 апреля 2019

Я думаю, что знаю ответ на этот вопрос.

Эвристика Cplex иногда находит целочисленные решения, не являющиеся LP оптимальными.Вот пример этого поведения.Это действительно может генерировать несогласованные решения.Многие конструкции моделирования MIP (абсолютные значения, минимальные / максимальные формулировки и т. Д.) Предполагают, что все целочисленные решения являются оптимальными для LP.Предпочтительно, чтобы Cplex очистил эти решения.

Обходное решение, которое я использую для этой проблемы, заключается в следующем.После остановки Cplex с решением MIP всегда фиксирует все дискретные переменные и разрешается как LP.Это очистит целочисленные решения, не являющиеся оптимальными для LP.Одно возможное исключение: если проблема окажется глобально оптимальной, тогда это может и не понадобиться (я стал несколько параноиком по этому поводу, поэтому я всегда добавляю финальный LP).Я не видел такого поведения (пока) с другими решателями.

...