16

Option 1: Submit as is to a solver which can globally optimize MIQPs having non-convex objective, and which might reformulate to a linearized MILP model under the hood. Such solvers include CPLEX, Gurobi 9.x, and BARON, among others. Option 2: Step 1 Linearize the products of binary variables, per How to linearize the product of two binary variables? . <...


14

Recognize that each route can be viewed as being a node on a graph. Edges connect nodes if the routes the nodes represent intersect. This is the canonical graph coloring problem for which there are a number of exact and approximate algorithms. Specifically, you're trying to find a constructive algorithm for determining the chromatic number. For 10 routes ...


13

Maybe I am missing something but it looks like there is no need for a library: \begin{align} \sum_i \sum_j \sum_k x_{ji} y_{kj} cost(i,k)&=\sum_i \sum_j x_{ji} \sum_k y_{kj} cost(i,k) \end{align} Now since $\sum_k y_{kj}=1$, exactly one row is 1, the others zero. We pick the best one: $$ =\sum_i \sum_j x_{ji} \max_k cost(i,k)$$ Since $\sum_j x_{ji}=1$ we ...


11

The backbone of modern MIP solvers is the so-called branch-and-bound algorithm. Nowadays, MIP solvers employ a variety of algorithmic tools, such as: presolve cutting planes heuristics branching strategies You can have a look at this paper by R. Bixby for an overview of such techniques, and their historical context. It is a few years old, but not a ...


10

Let $w_o$ denote the weight of object $o$, and let $c_b$ denote the capacity of bin $b$. You can interpret this as a job shop scheduling problem. The correspondence is that each object is a job, with duration $w_o$, each bin is a machine that is available for only $c_b$ time units, and $z$ is the makespan. It is also a special case of the bottleneck ...


9

Besides the traditional linearization suggested by @MarkL.Stone and @Richard, you might consider using the constraints to obtain a compact linearization. Explicitly, multiply both sides of your second constraint by $x_{j,i}$: $$\sum_k x_{j,i} y_{k,j} = x_{j,i}$$ Now replace $x_{j,i} y_{kj}$ with $z_{i,j,k}$ and impose an additional constraint to enforce $y_{...


9

This is a minimum cost flow problem in the bipartite graph $G=(V,A)$ with $V=N_U \cup N_B$. Add a source node and link it to each vertex $v\in N_U$. On each of these arcs, constrain the flow to be in the range $[a_{min},a_{max}]$. Note that if $a_{min} > |N_B|$ the problem is infeasible. Likewise with a sink node, that you link to each vertex $v \in N_B$, ...


9

I'd like to share a MIP solver developer's perspective on how our process works and what that means for the user. A MIP solver is a massive toolbox of algorithmic tools and tricks. Because MIP is generally NP-Hard, when we design a solver we set up a basic framework (for MIP typically branch-and-bound, some parallel functionality, and a bunch of acceleration ...


9

You can add an extra binary that equals $1$ if and only if the first constraint is satisfied: \begin{align} x_1+x_2+x_3 &\ge \delta\\ x_1+x_2+x_3 &\le 3\delta\\ x_4+x_5+x_6 &\ge 1 - \delta\\ x_4+x_5+x_6 &\le 3(1 - \delta)\\ \delta &\in \{0,1\} \end{align} If $\delta=1$, the first two constraints become: $$ 1 \le x_1+x_2+x_3 \le 3 $$ And ...


8

Be sure that your code reaches the getSolutions line. As of now, you are not sure that it does. Your Python code is creating more than 3000000 functions! There is a good chance that is what is causing your memory issues. Don't use exec, and create a single timezone function instead with S and TA as additional parameters. You can use a lambda to pass it to ...


8

Introduce a binary variable $x_{d,s}$ and change the right hand side to $1+2x_{d,s}$.


8

When I use CBC from time to time, it returns the best solution it has found even if it runs into the time limit. I guess, in your case, it has not even found a feasible solution. I call it this way: cbc file.lp sec 600 solve printi csv solu mysolution.csv On difficult binary problems, I had some success enabling zero-half cuts or adding more cuts then by ...


8

You can omit $v$, $w$, and $z$ and instead directly link $u$ and $x$ as follows: \begin{align} -(1 - u_{ikj}) \le x_{ij} + x_{kj} - 1 &\le 1 - u_{ikj} \tag1 \\ -u_{ikj} \le x_{ij} - x_{kj} &\le u_{ikj} \tag2 \end{align} Constraint $(1)$ enforces $u_{ikj} = 1 \implies x_{ij} + x_{kj} = 1$ (equivalently, $x_{ij} \ne x_{kj}$). Constraint $(2)$ enforces $...


8

Pretty much all of them. Any solver worth using will support timeouts and what you describe is basically running a solver with a timeout. Solvers that are supposed to compute more than one solution (e.g. MILP, convex & global MINLP, global NLP, stochastic MILP & MINLP) will return the best one by timeout - the rest will typically return garbage if a ...


8

There are many resources available to learn constraint modelling. When learning about constraint modelling I can recommend the following books: Principles of Constraint Programming by Krzysztof Apt is probably the most used constraint programming book that will teach you all the aspects of constraint programming. The book that would most fit your ...


8

When I started learning CP (coming from IP), one of the first things I discovered is that model elements are less standardized in CP than in IP. An IP model typically contains a polynomial objective function and equality/inequality constraints involving polynomial functions (where you are hoping the polynomials are linear or at worst quadratic). Beyond that (...


8

Aggressive cut generation will slow the processing of the root node (and other nodes, if cuts are generated beyond the root), so it's more likely to slow finding a feasible solution than to speed it up. Setting MIP_Strategy_Subalgorithm to 1 tells CPLEX to use primal simplex on node subproblems. To emphasize finding feasible solutions, you want to set ...


8

How about $$\omega_1 + \cdots + \omega_n \le n-1 $$ This way, at most all variables but one of them can take value $1$ simultaneously. In the context of knapsack problems, if each variable models the selection of a given item and that the sum of the weights of the items exceed the knapsack capacity, these inequalities are called cover inequalities.


8

@Kuifje's formulation is correct. Here's a somewhat automatic derivation via conjunctive normal form: $$ \lnot \bigwedge_{i=1}^n \omega_i \\ \bigvee_{i=1}^n \lnot \omega_i \\ \sum_{i=1}^n (1 - \omega_i) \ge 1 \\ \sum_{i=1}^n \omega_i \le n-1 \\ $$


7

The McCormick envelope is one possible approach. Another, if the domain of $y$ is not too large, is to use a type 1 Special Ordered Set. Assume that $y\in\lbrace 1,\dots,N\rbrace$. Replace $y$ with$$\sum_{j=1}^N j\cdot z_j$$where the $z_j$ are binary variables, and replace the equation $xy=q$ with$$x=\sum_{j=1}^N\frac{q}{j}z_j.$$Add the constraint$$\sum_{j=1}...


7

Introduce binary variable $y_0$ and linear constraints: \begin{align} y_0 + y_1 + y_2 &= 1\\ 1y_0 + 2y_1 + 3y_2 &= x \end{align} Equivalently, eliminating $y_0$: \begin{align} y_1 + y_2 &\le 1\\ 1 + y_1 + 2y_2 &= x \end{align}


7

As mtanneau said the core algorithm in MIP solvers is branch-and-bound (actually branch-and-cut) and a lot of machinery around it. But to a certain degree, solvers try to identify problem structures and might employ more problem specific algorithms if they detect a certain structure or adjust their overall solving strategy. Single constraint knapsack ...


7

These are called contiguity constraints. See this paper for models and references.


7

Solving: why is this solution optimal? As Richard explained, the objective in OR is not "fuzzy" like in ML: we assume an objective that can be evaluated by the computer. Once the problem is specified, there is not much to explain: you can prove optimality or infeasibility directly. Many solution methods attempt to prove optimality, and it is ...


7

Mention of intlinprog, without further specification, generally means the intlinprog of the MATLAB Optimization Toolbox. However, Gurobi also has a function called intlinprog, which mimics the interface of the MATLAB Optimization Toolbox intlinprog, but which calls the Gurobi solver. Similarly with Mosek. CPLEX has cplexintlinprog, which mimics the ...


6

Interestingly enough, one of the best source-open (!= open source) solvers is often overlooked: SCIP (download here); there is a Python interface (PySCIPOpt), too. The parameter you need is limits/time. edit: right, SCIP comes with a license and is not entirely free. AFAIK, the price tag is small when you use it commercially, the revenues are used mainly ...


6

Introduce a binary variable $y_j$ to indicate whether $x_j(t)>0$ for some $t$, and impose linear constraints: $$\sum_{t=1}^T x_j(t) = n_j y_j$$


6

In my opinion your best bet is to define an auxiliary variable $z_{ijk}$ such that: \begin{equation} z_{ijk} \geq x_{ji} + y_{kj} -1 \\ z_{ijk} \leq x_{ji} \\ z_{ijk} \leq y_{kj} \end{equation} Now this may become a really huge problem depending on the dimensions of $i$, $j$ and $k$. However, you gain the linearity of the problem which is worth a lot in my ...


6

Answers to the linked question mention both big-M constraints and semicontinuous variables. To speed up the big-M approach, you might consider introducing the constraints dynamically only as they are violated ("row generation" or "cut generation"). Explicitly: Omit all big-M constraints and the associated binary variables. Solve the ...


6

TL;DR: Some optimization problems are tough, and it requires a lot of work to get them solved. First, let me answer your questions: Yes, this is NP-hard, but that does not say anything about whether or not it is easy to solve. Most MIPs are NP-hard, yet they are solved extremely frequently. My favorite treatment of this comes courtesy of Paul Rubin (see ...


Only top voted, non community-wiki answers of a minimum length are eligible