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
vote
2answers
71 views

How to say to Gurobi solver with Python API to start from a given solution?

I have a binary linear program, where all my variables are binary. So, I have implemented the problem on python with Gurobi solver. I have implemented also a heuristic to find a near-optimal solution. ...
15
votes
1answer
206 views

Has the expressibility of 'non-integrality testing' as extension to MILP been studied before?

It turns out that extending MILP with any of the constraints $y=\lfloor x\rfloor$, $y=\lceil x\rceil$, $0 < x$, or $x\notin \mathbb{Z}$ is 'equally hard'. (see my answer here, and below) ...
3
votes
1answer
155 views

If variable falls below a certain value, include difference to set value in objective

I think its easiest to describe my goal first and continue with my implementation and the resulting problems! My goal: Using Pyomo as interface and Gurobi as solver, if a variable $x_{i,t}$ falls ...
7
votes
0answers
89 views

Network design problem with rounded capacity constraints

I have a network design problem with complicating capacity constraints which I'm trying to model through a Mixed Integer Programming formulation. The problem is defined on a directed, incomplete graph ...
3
votes
1answer
351 views

Why does the getTime() function from cplex concert returns wrong value?

I am running a MILP formulation (implemented in C++) with the Cplex Concert Technology 12.10, and I am trying to get the total elapsed time. So till the moment, I have tried three approaches: Be ...
1
vote
1answer
47 views

Capacitated Facility Location problem with a dynamic set up cost

I am trying to solve a Capacitated Facility Location Problem (CFLP) with a dynamic setup cost in R. The problem statement is this: I have the transport cost The ...
4
votes
1answer
251 views

Is it possible to identify all possible Irreducible Infeasible Sets (IIS) for an infeasible Integer Linear Programming problem? (ILP)?

For an Integer Linear Programming problem (ILP), an irreducible infeasible set (IIS) is an infeasible subset of constraints, variable bounds, and integer restrictions that becomes feasible if any ...
1
vote
1answer
47 views

Rule of thumb for introducing known constraints in Mixed Integer problem when they grow the formula

When encoding a problem into a Mixed Integer formula one faces a trade-off between embedding domain knowledge which might require new helper variables to express the constraints thereby growing the ...
-4
votes
0answers
29 views

How can I 2 terms in the objective function with sigma over each term in pywraplp library in OR tools

I am having 2 terms in my objective function based on the below objective function. Please guide me on how can I formalize it in OR tools? I tried the below way but it only considers the second term ...
-2
votes
0answers
49 views

Inventory positioning Model in GAMS

I have plotted a problem in GAMS expecting to get the route and inventory level I should put in DC but it's not shown the result. ...
2
votes
1answer
117 views

How to linearize the product of two integer variables?

Given two integer variables $L_x \leq x \leq U_x$ and $L_y \leq y \leq U_y$, how can we linearize the product $x \cdot y$?
3
votes
0answers
57 views

Is there any open source solver for MILP that can output the top N best results instead of the global best?

I am working on an MILP problem, and the project needs to output the top N best results rather than the global best. I am looking for an open source solver which has a callback function. Can anyone ...
2
votes
1answer
72 views

Linearize product of $x\cdot y \text{ with } x,y \in \{-1,0,1\}$ for MILP

I have a problem where I have many products between variables drawn out of $\{-1,0,1\}$. Could you suggest a linearization in terms of variables in $\{-1,0,1\}$ or $B_1 - B_2$ where $B_i \in \{0,1\}$ ...
6
votes
1answer
582 views

Linear Programming: Integer and non-integer decision variables

I am looking for an answer to a question I can't quite get behind. I am given the following mathematical optimization problem: \begin{align}\min&\quad\sum_{t\in T}s_t\cdot z_t+h_t\cdot i_t+p_t\...
3
votes
1answer
55 views

Docplex : model is infeasible

I have implemented a model in cplex and even if I give it an initial feasible solution of a heuristic programmed elsewhere, it gives me the error "the model is infeasible". Please if someone ...
1
vote
1answer
47 views

KPIs in Docplex?

I want to add a KPI to calculate the percentage of occupancy of vehicles: the total travel time of occupied arcs (where the capacity of a vehicle is non-zero) over the total travel time. How can I ...
3
votes
1answer
53 views

How to build a contiguous path?

In my (simplified) problem I have a grid. Given an origin cell, I'd like to find a minimum-length path on this grid that connects to one or more target cells. My idea is to use a series of binary ...
1
vote
1answer
49 views

Convex Optimization with Variable Dependency / no unmet demand carry forward

I'm running into an issue with a Linear Optimization Problem. The ultimate goal is to come back with an optimal production quantity (prod_qty) across several items ...
-5
votes
0answers
70 views

why in coding constraints you don't get the right answer?

From "A new unrelated parallel machine scheduling problem with tool changes to minimize the total energy consumption" Zhang et al. 2020 paper. A scheduling problem that schedules $n$ jobs on ...
1
vote
0answers
74 views

How to figure out integer variables in the relaxation set?

Suppose, there is mixed-integer programming as follows: $(1)$ $$\begin{aligned} \min&\quad c^{\top} x\\ \text{s.t.}& \quad A x \geq b \\ &\quad B x \geq d \\ &\quad x \geq 0 \\ &...
3
votes
1answer
288 views

Implement if-else without then part using int variables {0,1}

I have 6 binary variables $a_i$ for $i$ from 0 to 5. I would like to model the next if-else statement using only MILP constraints   if $(a_0+a_1+a_2)\mod 2=1$ then $(a_3+a_4+a_5) \mod 2 = 0$ I tried <...
5
votes
2answers
221 views

Combinatorial Feasibility Cuts for Benders Decomposition

Are there any advantages of adding constraints in Bender's master problem that ensure the feasibility of the subproblems? This would not add any feasibility cuts. Or is it beneficial to have a master ...
4
votes
1answer
83 views

The difference between subtour-elimination constraints in the symmetric and asymmetric TSP

We know that there are lots of formulations for traveling salesman problem. Some of them are based on the directed graph (asymmetric) and others are based on the undirected graph (symmetric). Also, ...
4
votes
1answer
177 views

How do constraints become redundant in a Big-M conjunction?

The following Big-M conjunction appears on page 14:3 of The Path&Cycle Formulation for the Hotspot Problem in Air Traffic Management: \begin{align*} \text{(i)} \quad t_{(g, \; s)} - t_{(f, \; s+...
4
votes
0answers
61 views

Modeling question on continuous variable that dependens on binary variables

Given a model with a binary variable $b_s$ that describes whether taking an item $s$ from a set $S$ or not. Consider that some other constraint in the model depends upon whether all items of the set ...
3
votes
1answer
84 views

Multi period inventory / reordering MILP in PULP

I'm trying to optimize reorder quantities for $n$ products over $m$ periods in PuLP. The total reorder quantity should fill a container. I've never worked with multiple periods before, and I can't get ...
4
votes
2answers
98 views

Deriving order/rank variable from another decision variable

There is a decision variable $x_i$ which denotes the time when a person is allowed to do his work. The objective function is $\min (x_i - a_i)$ where $a_i$ is the time when the person arrives at the ...
4
votes
1answer
119 views

Constrain Mixed-Integer problem such that a graph is fully connected

I have a problem (see my questions about Architectural layouts which poses an interesting abstract question) where there exists an implicit (symmetric) graph whose values in the adjacency matrix are ...
2
votes
0answers
53 views

Designing Multi Floor Architectural Layouts

Architectural layouts define the position and shape of rooms in 3D space, where windows and water pipes are and as well as how humans travel between rooms (among other things). There is a lot of ...
3
votes
0answers
49 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
220 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 ...
3
votes
2answers
119 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 ...
6
votes
1answer
250 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}\\ ...
8
votes
1answer
168 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 ...
2
votes
1answer
87 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
113 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
296 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
127 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
160 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,...
5
votes
1answer
515 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 ...
4
votes
1answer
259 views

Issue in solving a large scale MIQP problem

I am solving a large scale MIQP optimisation problem at each step of a model predictive control problem. The problem description is as below. \begin{align} \min_{u} \quad (x_{k}&-x_\text{ref})^{T}...
2
votes
0answers
74 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
95 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
60 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 ...
13
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 ...
2
votes
1answer
67 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
323 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 ...
2
votes
0answers
89 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 ...
6
votes
1answer
245 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 ...
4
votes
1answer
122 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....

1
2 3 4 5
11