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
3
votes
0answers
40 views

Polynomial Time Solution For a Mixed-Integer Linear Programming Specific Case

Consider the following mixed-integer linear programming (MILP): \begin{equation*} \begin{array}{ll@{}ll} \text{maximize} & 1 & \\ \text{subject to}& x_{i} \geq 0, &i=1 ,\dots, m\\ ...
7
votes
2answers
219 views

Product of weighted binary variables equivalent to sum of weighted binary variables?

I'm working on an optimization problem with a non-linear objective function of the form $$\max\prod_{i=1}^{n}(1-a_{i}x_{i}).$$ The objective function represents the combined probability of success for ...
7
votes
1answer
156 views

Name for this ILP problem type

I am considering automating testing of down-stream testing of packages that depend on other packages. There are test sets $T_1,\ ..., T_n$ which can be tested or not tested, which each have a time ...
3
votes
2answers
110 views

Assistance in formulating binary constraint(s)

I would like to seek some advice on modeling the following logical condition: Given two groups of binary decision variables $A_{i}, i=1...n,$ and $B_{j}, j=1...m$. $A_{i}=1- B_{j}, \forall i, \forall ...
2
votes
1answer
69 views

Excel Solver: Solving matrix values to match row/column sum according to reference

I've been trying to program Excel Solver to fill the values of a matrix so that the sum of rows and columns match preestablished values. See image: Excel Problem I understand this problem has infinite ...
5
votes
1answer
292 views

If continuous variable < constant then same variable = 0

When I come across with a situation needs an if-then constraints I visit Larry's post. I am a bit confused with the titled constraint this time because I am not trying to set $y$ based on $x$ but ...
2
votes
1answer
101 views

Using OR-Tools with .NET and GUROBI

We want to model our MILP problem with Google OR-Tools in .NET, and solve it using GUROBI (solver may change in the next 1-2 years). However, we couldn't find the correct syntax to call GUROBI. https:/...
5
votes
1answer
98 views

Practical open source LP solvers for large linear programming problem with $10^7$ parameters

I have an LP problem of the form $\min\ c^Tx$ subject to $Ax\leq b$ where $x$ consists of 30 million parameters and $A$ is a very very sparse matrix of size 30M by 30M (with only 3 ones per row). I ...
5
votes
1answer
509 views

Boolean constraining another boolean

like the title suggest, I am trying to constraint a boolean with another boolean, if that makes sense. x and y are both booleans, where y=1 when ...
2
votes
0answers
61 views

Problem with Piecewise constraint in Gurobi

I am facing a problem in my model with piecewise constraints that is making my one of the decision variables equal to zero for every value. My objective function is: \begin{equation} \min \sum_{t=...
3
votes
1answer
75 views

How to compare the optimality gaps between a commercial solver and Benders

Suppose I have a mixed-integer-linear programming model where the objective is maximization. I solve my model in two different ways. First, I call CPLEX (a commercial solver), and then implement ...
2
votes
0answers
57 views

Mathematical model complexity Vs Time Complexity of the model

As far as I know, when we talk about the term of complexity, it referred to the time complexity of the model in which how long does it take to solve a specific mathematical program by a specific ...
2
votes
1answer
53 views

How to return the last upper bound docplex?

I try to solve a model in docplex(python) the model was stopped after a specific time limit. I want when the model stop return the best upper bound was found.
8
votes
2answers
311 views

Mixed-Integer Linear Programming With Free Variables

In the classic Mixed-Integer Linear Programming (MILP), the variables are fixed to be either integer or real. I am interested in the following MILP variant, where only one thing different from the ...
5
votes
1answer
152 views

What methods are used to solve multi-objective optimization problem with non-linear objective functions and integer decision variables?

Case 1: NLP When either the objective function or at least one of the constraints or both are non-linear it is a NLP. We use generalized reduced gradient or Quadratic Programming to solve NLP. However,...
2
votes
0answers
82 views

About combinatorial Benders Cuts

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
1answer
118 views

Bi-Objective MILP with two conflicting (and linear dependent) objectives

I have a bi-objective MILP (Mixed Integer Linear Programming) problem, where I call the two objective functions as Obj1 and Obj2....
6
votes
1answer
243 views

Gurobi searches all nodes despite variable initialization

We are trying to solve a large-scale MIQCQP (18K decision variables) problem via Gurobipy (v9.0.3). Gurobi is able to solve this problem in ~13 mins despite whether or not we initialize the decision ...
-3
votes
2answers
58 views

How to check infeasibility with conflict refiner (docplex mixed integer programming )?

Please, if someone can give me an example of the application of conflict refiner, I have already read the documentation but I did not understand how to use it well.
6
votes
1answer
243 views

Dual of a model to obtain reduced costs

I have the following model which I am going to solve with column generation. \begin{align} \max & \sum_{b \in B} \sum_{s \in S} \sum_{r \in \Omega_s}\beta_{bs}p_r y_{br}\label{objective-set1}\\ ...
3
votes
0answers
75 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 ...
12
votes
2answers
2k 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
240 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). ...
3
votes
0answers
97 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
128 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
83 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
121 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
81 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
207 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
124 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
91 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 ...
4
votes
1answer
309 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
72 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
419 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
139 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
74 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
87 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
250 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
123 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
188 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
125 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
76 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
201 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
145 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
192 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
72 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
80 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
415 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 ...

1
2 3 4 5
10