如何启用线性松弛输出

Question

我有一个相当复杂的 MILP，但主要问题是连续变量的数量，而不是二进制文件的数量。我只是“硬编码”了线性松弛来理解它的输出，它大约需要。 10-15 分钟即可解决（这并不奇怪）。如果我运行带有输出的 MILP，我看不到前 10 分钟发生任何事情，因为这 10 分钟需要构造第一个整数可行解。因此，在 B&B 输出中“手动”解决线性松弛（类似 Iteration: 1 Dual objective = 52322816.412592）时，能够启用我所看到的相同输出会有所帮助。

这可能吗？我在 google 上搜索了一下，但我只找到了用于控制解决方案算法的解决方案，或者用于使用回调推导线性松弛的解决方案，而我对中间步骤的“简单”输出感兴趣。

Answer 1

在 java 中，您可以依赖 IloConversion 对象，它允许您在本地更改一个或多个变量的类型。

查看示例 AdMIPex6.java

/* --------------------------------------------------------------------------
 * File: AdMIPex6.java
 * Version 20.1.0  
 * --------------------------------------------------------------------------
 * Licensed Materials - Property of IBM
 * 5725-A06 5725-A29 5724-Y48 5724-Y49 5724-Y54 5724-Y55 5655-Y21
 * Copyright IBM Corporation 2001, 2021. All Rights Reserved.
 *
 * US Government Users Restricted Rights - Use, duplication or
 * disclosure restricted by GSA ADP Schedule Contract with
 * IBM Corp.
 * --------------------------------------------------------------------------
 *
 * AdMIPex6.java -- Solving a model by passing in a solution for the root node
 *                  and using that in a solve callback
 *
 * To run this example, command line arguments are required:
 *     java AdMIPex6  filename
 * where 
 *     filename  Name of the file, with .mps, .lp, or .sav
 *               extension, and a possible additional .gz 
 *               extension.
 * Example:
 *     java AdMIPex6  mexample.mps.gz
 */

import ilog.concert.*;
import ilog.cplex.*;


public class AdMIPex6 {
   static class Solve extends IloCplex.SolveCallback {
      boolean     _done = false;
      IloNumVar[] _vars;
      double[]    _x;
      Solve(IloNumVar[] vars, double[] x) { _vars = vars; _x = x; }
    
      public void main() throws IloException {
         if ( !_done ) {
            setStart(_x, _vars, null, null);
            _done = true;
         }
      }
   }

   public static void main(String[] args) {
      try (IloCplex cplex = new IloCplex()) {
         cplex.importModel(args[0]);
         IloLPMatrix lp = (IloLPMatrix)cplex.LPMatrixIterator().next();
       
         IloConversion relax = cplex.conversion(lp.getNumVars(),
                                                IloNumVarType.Float);
         cplex.add(relax);

         cplex.solve();
         System.out.println("Relaxed solution status = " + cplex.getStatus());
         System.out.println("Relaxed solution value  = " + cplex.getObjValue());

         double[] vals = cplex.getValues(lp.getNumVars());
         cplex.use(new Solve(lp.getNumVars(), vals));

         cplex.delete(relax);

         cplex.setParam(IloCplex.Param.MIP.Strategy.Search,
                        IloCplex.MIPSearch.Traditional);
         if ( cplex.solve() ) {
            System.out.println("Solution status = " + cplex.getStatus());
            System.out.println("Solution value  = " + cplex.getObjValue());
         }
      }
      catch (IloException e) {
         System.err.println("Concert exception caught: " + e);
      }
   }
}

如果你使用 OPL 那么你可以看看 Relax integrity constraints and dual value

int nbKids=300;
float costBus40=500;
float costBus30=400;
 
dvar int+ nbBus40;
dvar int+ nbBus30;
 
minimize
 costBus40*nbBus40  +nbBus30*costBus30;
 
subject to
{
 ctKids:40*nbBus40+nbBus30*30>=nbKids;
}
main {
  var status = 0;
  thisOplModel.generate();
  if (cplex.solve()) {
    writeln("Integer Model");   
    writeln("OBJECTIVE: ",cplex.getObjValue());   
    
  }
  // relax integrity constraint
  thisOplModel.convertAllIntVars();
 
  if (cplex.solve()) {
    writeln("Relaxed Model");   
    writeln("OBJECTIVE: ",cplex.getObjValue());  
    
    writeln("dual of the kids constraint = ",thisOplModel.ctKids.dual);
  }
   
 
}

Answer 2

听起来您要求在 B&B 求解的线性松弛部分进行更详细的记录。查看 CPLEX 参数设置，例如 IloCplex.Param.MIP.Display（尝试将其设置为 5）以及 IloCplex.Param.Simplex.Display（尝试设置为 1 或 2）。

如何启用线性松弛输出

How to enable linear relaxation outputs

java

cplex

output