New answers tagged

6

It is not true in general, but you can make it work with $$\max\sum_{i=1}^{n}\log(1-a_{i})x_{i}$$ Since $\log$ is monotonic, your objective is equivalent to $$\max\log\left(\prod_{i=1}^{n}(1-a_{i}x_{i})\right)$$ which becomes $$\max\sum_{i=1}^{n}\log(1-a_{i}x_{i})$$ and finally, since $x_i$ is binary and $\log(1) = 0$ $$\max\sum_{i=1}^{n}\log(1-a_{i})x_{i}$$ ...


6

No it's not true in general. Consider $n=4$ with $a=(0.3,0.7,0.5,0.5)$ under the constraint $(x_1 \wedge x_2) \text{xor}(x_3\wedge x_4)$ which can be expressed in terms of MILP by introducing helper binary variables. For the linear term, $(1,1,0,0)$ and $(0,0,1,1)$ are equally good optima while for the product term they obviously differ in quality, meaning ...


10

This is called the budgeted maximum coverage problem.


4

Via conjunctive normal form: $$ A_i \implies \bigwedge_j \lnot B_j \\ \lnot A_i \lor \bigwedge_j \lnot B_j \\ \bigwedge_j (\lnot A_i \lor \lnot B_j) \\ \bigwedge_j (1-A_i +1- B_j\ge 1) \\ \bigwedge_j (A_i +B_j\le 1) \\ $$ The other implication $$B_j \implies \bigwedge_i \lnot A_i$$ yields the same linear constraints. From your comment, you also want to ...


1

I would add an auxiliary variable $z\in\{0,1\}$: $$ z \geq a_i \ \ \forall a_i \in A $$ Then you can write: $$ b_j \leq 1-z \ \ \forall b_j \in B $$ If $z=0$, then the constraint is redundant. However, if $z=1$, then all elements of $B$ have to be 0. Update: @RobPratt correctly pointed out that the above formulation allows for $a_i = b_j = 0$, which ...


2

The problem is feasible only if the sum of the rows equals the sum of the columns. That's true for your Reference table, but not for the other tables. I'm not clear about what your objective function is intended to do relative to the Reference table. But your formula =((SUM(B19:F31))^2)^(1/2) makes no sense. Perhaps you intend to sum the squared differences ...


4

If you can't find (or can't afford) a solver that will handle a problem with that many nonzero matrix coefficients, and if your problem has a structure that fits one of the following methods, you might try either Dantzig-Wolfe or Benders decomposition.


9

This is a semicontinuous variable, and you can enforce it by introducing a binary variable $y$ and imposing linear constraints $$cy\le x \le My.$$ If $y=0$, then $x=0$. If $y=1$, then $x\in[c,M]$.


5

the library needs to find the gurobi shared library before you can create the solver. You can set GUROBI_HOME to help. you can have callbacks, but only in c++. Look for or-tools/linear_solver/linear_solver.h. Search for callbacks.


6

Disclaimer: One might want to look for a reformulation or a special structure to apply mathematical tools to find optimal in the feasible set. I am assuming you're already past the possibility that your problem case could be reformulated as a MILP/LP/QP etc. So, with the problem on hand, we're dealing a case where we cannot have a reformulation. Whatever I ...


6

It looks like you want to model $x \; \Longrightarrow \; y $, or in conjunctive normal form : \begin{align*} \lnot x \vee y \\ 1-x + y \ge 1 \\ x \le y \end{align*} If $y$ takes value $1$ when a given parameter $p$ is larger than a given variable $z$, then you need to add $p > z \; \Longrightarrow y=1$, or its contraposition $y=0 \; \Longrightarrow \; p \...


2

Assuming you are comparing Benders results to CPLEX solutions, why not use the CPLEX formula for the Benders results? Best integer would be your $LB$ and best bound would be the current objective value of the master problem.


3

Once you solve a docplex model, it creates an internal SolveDetails object that contains the best bound you're looking for. You can access it in two ways: Assuming you've defined your docplex model as model (an instance of the class docplex.mp.model.Model) print(model.get_solve_details().best_bound) Assuming you've stored your model's solution in sol (an ...


9

Here's another single-solve solution. Replace each original variable $x_n$ with a sum of two variables, $x_n=y_n + z_n$, where $y_n$ is integer-valued and $z_n\in [0,1]$. Now define $\lbrace z_1,\dots, z_n\rbrace$ to be a type 1 special ordered set (SOS1). Assuming the solver supports SOS1 constraints, you'll end up with a solution in which at least $n-1$ of ...


8

An alternative approach that requires only one solve and no modification of the model is to modify branch and bound to prune by integrality when at most one integer variable takes a fractional value (rather than the usual requirement that all integer variables are integer-valued). You would also need to disable any presolve/cut routines that assume ...


8

We at Mosek has started porting Mosek to the Apple M1 CPU so the upcoming version 10 will support it. Here is an initial thought. Normally optimization software links to a BLAS/LAPACK library such as Intel MKL that does dense matrix multiplication and other important operations. That the BLAS/LAPACK library is of high quality is very important for the ...


5

Your last example, is certainly not that interesting. Let $f_1(x)$ and $f_2(x)$ abe the objective functions. From multi-objective optimization theory it is well known that if we use strictly positive weights for the objectives and solve the corresponding weighted sum scalarization, any optimal solution is efficient. In this case, we choose weight vector $\...


9

Gurobi is solving the global optimisation problem. This involves (i) locating the global solution, and (ii) proving that it is the global solution. Step (i) is typically the easiest by far. By providing the solution you are helping the solver fathom more nodes from the beginning, but that's about it. It still needs to prove global optimality, which is the ...


3

ILOG Cplex 20.1 installation comes with a directory with examples. To use the conflict refiner, you want to consult the manual which includes a list of files that contain examples on how to use the conflict refiner. Of particular interest are the following files: ./examples/src/java/ConflictEx1.java ./examples/src/cpp/iloconflictex1.cpp ./examples/src/python/...


3

As the docplex documentation says: Given an infeasible model, the conflict refiner can identify conflicting constraints and bounds within it. So, consider you have an infeasible model (I'll call my instance model). This is one way to use the conflict refiner. import docplex.mp.conflict_refiner as cr import docplex.mp.model as cpx model = cpx.Model(name='...


1

@Mostafa, j is the number of jobs while r is the number of machines, this means $NumofJobs = Tasktime.shape[1]$ and $NumofMachines = Tasktime.shape[0]$, and also, s must be $s = m.addVars(NumofMachines,NumofJobs)$, otherwise the optimality cannot be achieved. Do this modification and run the example by using the data in Table 1 found in your reference paper(...


Top 50 recent answers are included