Questions tagged [mixed-integer-programming]

For questions about mathematical optimization problems involving both continuous and binary or general integer variables.

Filter by
Sorted by
Tagged with
-1
votes
0answers
7 views

Setting up a community Server for OR-enthusiasts [migrated]

It is more a suggestion than a question. I am thinking it would be a great idea to set up a OR-Discord-Server for people who are studying or working with the methods for operations research. I myself ...
5
votes
1answer
110 views

Dual of a model to obtain reduced costs

I have the following model which I am going to solve with column generation. Basically it is a VRP problem with pick-up and delivery in which couriers are assigned to a set of shifts based on their ...
3
votes
0answers
66 views

Extract/Inject Solutions (orig problem-space) during Search in MILP -> CoinOR Cbc

Task / Goal I'm considering adding some customized problem-specific local-search component on top of a general-purpose MILP solver (= improvement heuristic). The basic idea is the following: All new ...
9
votes
1answer
1k views

Is Apple's M1 suitable for Operations Research?

I am curious about the performance of Apple's M1 chip solving optimizations models, MIP, LP, and in solutions approach as benders or columns generations. I read that is a spectacular cpu to perform ...
5
votes
1answer
234 views

Why does one objective function prove feasibility faster than another?

I recently ran a MIP model with cplex specifying it should stop solving when integer feasibility was proven (mipsolutions=1). ...
2
votes
0answers
87 views

Harvest planning problem

I need to model the following problem: For a planning horizon of $P$ equal periods, one has $N$ harvesting locations and $K$ contractors who can harvest at those locations ($K < N$). Each ...
5
votes
2answers
119 views

In a MIP, how to force a decision variable to be zero unless the sum of specific other decision variables is equal to a certain number?

In an MIP, how can I formulate a constraint such that a decision variable is only greater (or equal to) zero if (and only if) the sum of different decision variables is equal to something. I'm working ...
5
votes
1answer
80 views

What are (some of) the best resources for shift scheduling/rostering?

Shift scheduling/rostering is obviously very widely researched, with tons of papers around it. I found the review papers by Van den Bergh et al. [1] and Ernst et al. [2], but am looking for something ...
2
votes
0answers
119 views

Why is exact TDTSP solving much harder to do than TSP solving?

I was thinking about exact methods for solving the Time Dependent TSP (TDTSP). Clearly, it is at least as complex as TSP because it extends TSP, but why is it for exact approaches that difficult to ...
1
vote
1answer
78 views

Resource Optimization For Cargo Handling

I have to work on some real world data and come up with an optimization technique to handle cargo. To make thing simpler let's assume that there are 2 types of resources Manpower (150 ton / 8 hour) ...
7
votes
3answers
185 views

How to formulate the constraint If $x = k$, then $y = c$?

Given are two integer variables $L_x \leq x \leq U_x$ and $L_y \leq y \leq U_y$. I'd like to formulate the constraint $$ \text{If} \;\; x = k, \;\; \text{ then } \;\; y = c, $$ where $k$ and $c$ are ...
4
votes
1answer
112 views

Alternate formulation for modeling inventory constraints

I'm working on a inventory optimization problem where inventory used at a time-period is computed based on price-bucket that is selected for an item. Problem contains multiple items (around 10K), 15-...
4
votes
1answer
89 views

Lot-sizing problem variant

I have a the following optimization problem: I have mandates,(e,g. to deliver 100 tonnes of products) that I need to schedule its delivery during the month (day 2: deliver 40 Tonnes, day 15: deliver ...
3
votes
1answer
257 views

Gurobi: how to add a constraint to make there be only one non-integer value

line1 line2 line3 line4 A 2.3 0 3.1 0 B 0 4 2.2 0 C 1.1 0 0 4.6 Let's say after optimization with certain constraints, my model will generate an optimal production allocation table similar to ...
2
votes
1answer
67 views

Suggestions how to get access to MINTO MILP solver?

I came across the MINTO MILP solver today. A solver i wasn't aware of or at least had not paid attention too. While development seem to have stopped two decades ago however i still wouldn't mind ...
3
votes
2answers
408 views

How to linearize a constraint with a maximum of a linear function

I want to linearize the following statement into a MILP: $\forall x\in \mathbb{R}^{m}$ satisfying $Cx \le d$, $\exists i\in \{1,\cdots,m\}$ such that $a_i^Tx \ge b_i$, where $a_i$ and $b_i$ are given ...
3
votes
1answer
137 views

Bin Packing with CP Solver

[ [0,5], [0,4], [1,6], [2,4], [3,6], [3,2], [4,5], [5,5], [6,4], [7,3], [8,2], [8,3], [9,5], [10,3]] ...
2
votes
0answers
72 views

What if anything do linear relaxations of "nearby" MILP nodes tell us about other MILP nodes

Assume we are given MILP where $y \in (\mathbb{R}^+)^n$, $x_1, x_2 \in \{0, 1\}$ are the integer variables. It is obvious that this problem when solved via branch and bound has a 2 deep b&b-tree. ...
4
votes
1answer
83 views

Maximizing sum of step functions under single linear constraint

I am trying to efficiently solve the following optimization problem: \begin{align}\max_{b \in \mathbb{R}_+^D}&\quad\sum_{n=1}^{N}\operatorname H(b^T w^{(n)} - c^{(n)}) \\\text{s.t.}&\quad\sum_{...
19
votes
3answers
2k views

Using Neural Networks For Solving Optimization Problems

Recently, I came across the below paper and found it very interesting. Solving Mixed Integer Programs Using Neural Networks; https://arxiv.org/abs/2012.13349 The idea is to use (train with neural ...
5
votes
3answers
249 views

Infeasibility False Positive

Is it possible/likely for a mixed integer linear solver (CBC in my case) to incorrectly state that a problem is infeasible when in fact it is actually feasible? Are there properties of the model that ...
5
votes
1answer
118 views

Do you know of any formula to calculate the difficulty score of Sudoku?

I am looking for a formula to measure the difficulty level of a Sudoku solution.
3
votes
1answer
183 views

The optimum is achieved only by forced "solution polishing"

I have the behavior of CPLEX during a MIP search, when it finds the optimal solution in a reasonable time during a forced "solution polishing" phase only. Otherwise, if you do not switch the ...
7
votes
1answer
117 views

Bilinear programming vs Mixed integer linear programming performance comparison

I know that both bilinear programming and mixed integer linear programming are NP-hard. But is there a preference to have when choosing an approach to solve a problem that can be represented in both, ...
0
votes
0answers
75 views

Products distribution planning model

I have a problem of planning the distribution of products for a month. I have different unique products. A Mandate is provided for each product, and the Mandated quantity for each product is to be ...
6
votes
2answers
200 views

Heuristic solution to the graph partitioning problem

I am working on a graph partitioning problem. A static column generation based solution was proposed in How to partition a graph with optimal number of groups? But I need some MILP solver to solve ...
2
votes
1answer
117 views

Benders Decomposition cuts for MILP problem with further separable subproblems

I am solving an OR scheduling problem where I assign the patient to (day,OR) tuple in Master Problem. Once the assignment is made, a subproblem can be solved for each (day,OR) tuple independently ...
4
votes
2answers
187 views

Multi-product distribution modeling : too many constraints

I have received many helps to model the problem, thank's for that ! I just edited the post to make clear what my actuel problem is. The following model is giving me amazing results with few products (...
6
votes
2answers
71 views

If $t\le0$ then $P=1$, if $t > 0$ then $P =0$ or $P=1$

I am trying to model $t \leq 0.0 \implies P = 1.0$ else $P=1$ or $P=0$ where $0 \leq t \leq H$ is a bounded nonnegative real, and $P$ is binary. I can use the expression $t + \epsilon P \ge \epsilon$ ...
2
votes
1answer
79 views

Is there any solver intended specifically for integer and binary variables alone on the optimization model other than solvers for MIP, MILP?

Any solvers which can be integrated in python where we can quickly solve if we have integer and binary variables alone in our model other than normal solvers for MIP, MILP?
5
votes
4answers
405 views

Solving Capacitated VRP with multiple various sized vehicles

I am looking to form a Capacitated VRP problem like this: I have 40,000 dropping locations with Demands of each point available I have 5-6 types of vehicles available with different capacities and ...
3
votes
0answers
89 views

In binary linear programming, what's the relationship between the dual solution and the lagrangian multipliers?

In my optimization problem the objective function and all the constraints are linear. The decision variables are binary. [so, it's BLP] Some of the hard constraints are very time-consuming to be ...
4
votes
2answers
116 views

When solving many MILPs how to assign CPU cores to solver instances?

Let's say I have an 16 core machine and many roughly equally hard MILP problems and enough RAM. The latency of solving doesn't matter. With how many cores should I start solvers on to maximize ...
4
votes
2answers
104 views

How to linearize specific range constraints?

I would like to know about the linearization of the $(If, Then)$ constraints as follows: $$\begin{array}{l} \text { If: } \\ 15 \leqslant x \leqslant 25 \\ \text { then: } \quad y=\color{blue}{a} x+\...
1
vote
1answer
79 views

Formulate a constraint set to identify the number of overlapping operations

Let assume we have operation $r \in R$, machine $n \in N$ and day $t \in T$. $S_{r}$ is the service duration of operation $r$. Note that $S_{r}$ can be defined based on time slot (e.g., $S_{1}$ can be ...
3
votes
0answers
56 views

Resource scheduling problem with synchronization constraints: Weak LP relaxation

I have a resource assignment/scheduling problem which involves assigning jobs to $m$ workers. There are 2 sets of different jobs, $J^1$ and $J^2$, and a set of periods $T$. Let $d_{jt}$ be the number ...
0
votes
0answers
49 views

Lower bound very bad. How to improve?

I have the following MILP: \begin{alignat}{2} \nonumber \mbox{minimize } \quad & \phi = \sum_{i=1}^{m-1} \sum_{f=1}^{F} \sum_{\underset{\bar{f} \neq f}{\bar{f}=1}}^F \sum_{h \in H} \left( D_{f \...
3
votes
3answers
196 views

Does a pre-calculated lower bound of an MILP problem help?

I have an MILP model, say $$ \begin{array}{rl} \mbox{minimize} &f_1(x) + f_2(x)\\ \mbox{subject to} &x\in X \end{array} $$ which is hard to solve. And I find it simple to solve the two ...
3
votes
2answers
67 views

CPLEX MILP Report all solutions found

I am running a MIP using DOCPLEX that generates several feasible integer solutions during the Branch and Bound search. The node log updates every now and then based on the parameter setting. However, ...
1
vote
0answers
36 views

Constraint formation help

I am implementing a quay crane optimization model. The objective is to minimize the loading time. Inputs to the model are $I=$ number of nodes $K =$ number of cranes $z_k =$ crane speed in meter/...
4
votes
1answer
268 views

What is the best practice regarding "automatic integer variables"?

There are sometimes variables that automatically take integer values in feasible solutions, like MTZ-formulation of TSP. They could be declared continuous or integer, and I find the solver performs ...
0
votes
0answers
93 views

Check VRP instance is feasibility

Beforehand, this is a very long thread, in case you want to know in advance, to see if this thread's interests match with yours, this thread concerns fast ways of determining whether a VRP instance is ...
4
votes
1answer
111 views

How do I formulate constraints that check if a parameter is between certain values, using binary variables?

I have $3$ parameters $a_1,a_2,a_3$ and a variable $d$ and $3$ binary variables $b_1,b_2,b_3$ and a "result" variable $s$. How do I model constraints so that: If $d$ is between $0$ and $a_1$...
3
votes
1answer
178 views

Scheduling minimization Integer Programming problem formulation

I am working with integer optimization. I have a problem with $t$ tasks and every task $i$ needs $w_i$ weeks to be completed and $p_{il}$ workers on a specific week $l$. There is a total time in weeks ...
5
votes
1answer
91 views

Breadth First Search vs. Best First Search

What is the main difference between Breadth First Search and Best First Search? What is meant by saying Breadth First Search requires previous knowledge?
1
vote
0answers
60 views

Multiple conditions in indicator constraint of Gurobi

I'm working on a vehicle routing problem, in which a vehicle need to pick up amounts of things in some nodes. I'm trying to solve it by Gurobi optimizer. Except for meeting the time windows of each ...
6
votes
1answer
100 views

Upper and lower bounds of a variable equal

I'm working on a MILP (Mixed-Integer Linear Programming) problem with the Java API of Cplex. In order to easily exclude some variables from my problem I thought about setting both their lower and ...
2
votes
1answer
106 views

Problem with vehicle routing problem in Gurobi Python

I have a vehicle routing problem solved by linear programming, but I'm confused about the constraints (see the model in figure 1). In the model, $u$ and $x$ are decision variables, and we set node $0$ ...
0
votes
1answer
137 views

1
2 3 4 5
10