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
6
votes
1answer
178 views

Does the weighted sum approach find all pareto-optimal solutions in MILP

I use the weighted sum approach for a multiobjective optimization problem that is formulated as a MILP. This means that the objective function is linear. I read quite often that the weighted sum ...
1
vote
1answer
76 views

A discrete location problem

I have a discrete optimization problem in which there are some predetermined nodes in the set A. a vehicle must visit them as the traveling salesman problem. there are some other nodes in the set B ...
2
votes
0answers
77 views

Indicator function for integer variable with inequality constraint

I have $n$ integer variables $\vec{x}$ with the following integer programming problem. $$ COST = \sum^{n-1}_{i = 0} a_i x_i + \sum^{n-1}_{j=0} b_j I(x_j > 0) $$ Here, $a_i, b_j \in \mathbb{R}_+$ ...
3
votes
1answer
177 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}...
3
votes
1answer
88 views

Portfolio optimization with indicator function constraint in CVXPY

I have the following portfolio optimization problem that I want to solve using CVXPY: \begin{align}\min_w&\quad w^\top\Pi\\\text{s.t.}&\quad\sum_{i=1}^nw_i=1\\&\quad w^\top\Sigma w\le\...
2
votes
0answers
96 views

Condition for an integer program and its linear relaxation to have the same value

Let $A$ be a $(0,1)$-matrix where no row or column is a zero vector, and consider the following optimization programs \begin{align}(1):\min&\quad y\cdot1\\\text{s.t.}&\quad yA\ge w\\&\quad ...
1
vote
1answer
100 views

Issues modeling portfolio optimization with rebalancing in gurobipy

I want to solve the following portfolio optimization problem by means of the Python API of Gurobi: \begin{align}\max_w&\quad w^\top\Pi\\\text{s.t.}&\quad w^\top\Sigma w=\sigma^{\rm target}\\&...
0
votes
0answers
37 views

Interger programming using gray encoding

Could anyone suggest me a tool or library which takes an integer programming problem written in DOCPLEX or CVXPY as input and outputs the equivalent problem using Gray binary encoding? I am happy to ...
1
vote
2answers
131 views

Formulate a problem as Mixed Linear Programming problem

I need to formulate the following problem as a Mixed Integer Linear Programming problem A farmer needs to establish a 17-year business plan where he will decide when to sell or buy a new truck. The ...
2
votes
2answers
211 views

Does it make sense to use a MILP solver for a scheduling problem but without the obligation to schedule all the tasks?

I know that MILP solvers are bad with scheduling problems. However, if we are allowed to keep unscheduled some tasks (i.e a solution with 0 scheduled tasks is a feasible solution but we add the ...
2
votes
2answers
338 views

How can I identify the reason that makes a MILP model hard for solvers such as CPLEX?

I'm solving a MILP model whose native lower bound (via linear relaxation) is very poor. We could provide a lower bound by providing a given value (derived based on the problem itself). I know that ...
6
votes
4answers
744 views

Can this be formulated as one inequality

I have two binary variables $x_1$ and $x_2$ and a non-negative continuous variable $y$. In addition, I have the following two parameters $u>q>0$. I would like to formulate the following ...
2
votes
1answer
60 views

distance specific constraint

I have some points with determined coordinates $(a_i,b_i)$. A vehicle can move between these points based on rectangular distance. In more detail, we consider that the path between points is an ...
0
votes
2answers
253 views

How to model y = floor(x)?

I went through the answers to this question: Modeling floor function exactly, but I still do not get how to model y = floor(x). Is that question answered and I just ...
1
vote
2answers
91 views

How this problem can be defined as MultiObjective optimisation

I need to optimize the end-to-end latency of a multi-component application. Assuming that the application has 10 components, component 1-5 is hosted by device 1, and device 2 is hosting the other 5 ...
1
vote
0answers
76 views

Benders Decomposition Problem

$$r_{m_h,s}(n)=\frac B{m_hb_\ell s}\log_2(1+\gamma_{m_h,s}(n))$$ How to deal with multiple subproblems in Benders decomposition when the original objective function is in product form of an integer ...
3
votes
3answers
108 views

How to write distance specific constraint?

Suppose there are a few plants (p) and few customers (c). The supply (Sp), distance (Dpc), cost (COSTpc) and demand (DEMANDc) between them is given. I have a constraint that 90% of total demand of all ...
3
votes
3answers
227 views

How to linearize the Min function while letting the binary variable to be fixed for x1==x2 as well?

As discussed here, the min function, i.e $X = \min\{x_1,x_2\}$, can be linearized as follows: \begin{align} X & \le x_1 \\ X & \le x_2 \\ X & \ge x_1 - ...
2
votes
1answer
118 views

Is my formulation correct and how to formulate this IF-THEN constraint?

I have system with $N_U$ users and $N_T$ transmitters. Multiple transmitters can transmit to a single users and one transmitter can transmit to many users, i.e., two sets of transmitters serving two ...
4
votes
1answer
98 views

Formulating these logical constraint in an ILP

I have these two constraints : $z \leq My$ $t \leq M'y $ where $z$ and $t$ are two integer variables $ z, t\geq 0$, $y$ is a binary variable, and $M$, $M'$ are two big numbers. So basically these ...
2
votes
1answer
106 views

How can I have minimum amount of resources wasted in this resource allocation problem?

I have a demand, $d$ I also have supply from 1000 sources. The supplies from those $N$ (for example, $N=1000$) sources are given by $s_1,s_2,s_3,\cdots,s_N$. So,the total supply is : $s_1+s_2+\cdots+...
6
votes
2answers
399 views

Branch and Price Algorithm

Can branch and price be a good solution approach for a routing problem with min-max objective function? For example, minimizing the max length of any vehicle route in a VRP. In the literature, I haven'...
3
votes
1answer
182 views

Semi continuous constraints in CPLEX Python

I have a semi-continuous optimization problem reformulated as a MIQP optimization problem. My objective has a quadratic form $x^{T}Qx$ and my $x_{i}$ are such as $x_{i} \in [m,M] \cup \{0\}$. ...
1
vote
1answer
394 views

Mixed integer quadratic programming (MIQP) in CVXPY

There's something I don't understand about CVXPY's example on its MIQP use. It says that the algorithm returns a solution $x \in \mathbb{Z}^n$ but I thought in general the point of MIQP algorithms was ...
7
votes
1answer
162 views

Strong MIP formulations for a large-scale mixed-integer nonlinear feasibility problem

I'm trying to construct a strong MIP formulation for the following integer nonlinear feasibility problem. Informally: We have a $m \times n$ decision matrix of binary variables Each row of the matrix ...
12
votes
2answers
509 views

How to handle an IP sub-problem with an objective function in Benders Decomposition

I have a question on Benders Decomposition (BD). Suppose I have an MILP model which can be decomposed into a master problem (MP) including integer and continuous variables and a subproblem (SP) ...
3
votes
2answers
229 views

How to formulate this problem?

I have a matrix in the size of $S \in \mathbb{R}^{M\times N}$ with only binary values $0..1$. I want to select $m<M$ rows from $S$ and sum the $m$ rows to get a new vector $v$. I wish $v$ to be ...
4
votes
1answer
179 views

Column Generation algorithm

I want to solve a VRP with a column generation algorithm. The objective of the problem is makespan minimization. but there is a point in calculating the arrival time of the vehicle in each node. the ...
3
votes
1answer
43 views

How can I change decision variable type in Concert Technologies (with Java)

I have a MILP model with continuous variables ($y_{ij}$) and binaries ($x_{ij}$). I am using Java and cplex 12.8 for implementation. Is there a way by which - using the Java-cplex API - I would be ...
3
votes
1answer
126 views

Logical constraint in ILP

I want to write the following constraint: Let $z$ be an integer variable such that $0\le z\le M$, and $t$ be a binary variable where $M$ denotes big-M. The logical constraint is as follows: if $z \...
3
votes
1answer
153 views

How to express this logical constraint for an ILP?

I am trying to write an ILP for a problem but I have this logical constraint and I'm stuck. In my model I have: two binary variables: $x$ and $y$ One Integer variable: $z$ The logical constraint I am ...
3
votes
1answer
119 views

A Question on A tutorial on column generation and branch-and-price for vehicle routing problems by Dominique Feillet

I am reading A tutorial on column generation and branch-and-price for vehicle routing problems by Dominique Feillet to learn the column generation approach, but I have a problem. in section 3.3 ...
5
votes
1answer
213 views

Column Generation algorithm for vehicle routing problem

I want to solve a VRP with a column generation algorithm. The objective of the problem is makespan minimization. In more detail, I want to minimize the arrival time of the last vehicle in the depot. I ...
4
votes
1answer
217 views

Best way to solve an allocation problem

I have the following problem: I have products with different attributes (price, weight, category) and I have a list of clients. Every client has an "affinity value" with every product, the ...
-2
votes
1answer
173 views

Optimized Production Planning & Scheduling

I want to create an optimized schedule and production to meet demand of four different buyers. I am starting with Pulp but not able to account for continuous production variable and discrete dispatch ...
5
votes
0answers
82 views

Are there any good models for min-max vehicle routing problem?

I am trying to model a min-max VRP problem with multiple delivery vehicles and I have come up with a model using branch and cut but I do not think it is strong enough as it takes lot of time to ...
3
votes
1answer
178 views

Mixed integer programming vs Constraint programming

I see that certain studies are comparing MIP and constraint programming (CP) performances. And generally, they claim that CP outperforms MIP. But I believe that it is not completely true. Because ...
2
votes
1answer
110 views

Scenario based approach to value-at-risk optimization using mixed-integer programming

For a discrete set of scenarios, minimising value at risk can be formulated as a mixed integer linear programming problem. If each scenario has equal probability then this can be written as \begin{...
4
votes
1answer
158 views

Column generation when intractable variables appear in the objective function

Is it possible to implement a column generation for a problem that the variables in the "complicating" constraint appear in the objective function? Suppose the MIP is: \begin{align} z = \...
2
votes
0answers
67 views

Finding Optimal Route using different Paths

I have a list of paths e.g. path 1 takes you from point A to B. A person needs to complete 5 of such paths. $$Route1 = path1 + ...
2
votes
1answer
111 views

Is a convex or MILP (without big-M) formulation possible for this problem

Assume we are given a directed acyclic graph (DAG) $G(V, A)$, where $|V| = n, |A| = m$, and the graph contains a source node $\mathbf{s}$ (i.e. every node in $V \backslash \mathbf{s}$ is connected by ...
8
votes
2answers
122 views

(Iterative?) Solutions to a certain quadratic program with non-convex constraints

Let $y\in\mathbb{R}^m$, $\tau\in\mathbb{R}$ and $X\in\mathbb{R}^{m\times n}$, with $\tau>0$ I would like to efficiently solve the following problem: Problem 1 Choose $\alpha,z\in\mathbb{R}^m,\beta\...
1
vote
1answer
70 views

How to get detail about 'OptimizationStatus.ERROR' in MIP module in Python?

I am using MIP (Mixed Integer Programming) module in Python to solve one of my optimization problems. for some of the scenarios, model returns "ERROR" (OptimizationStatus.ERROR) status after ...
2
votes
0answers
152 views

Operation hours optimization for circular schedule

Here is my problem. A store has X = 15 electical devices with the ability to work non-stop, fully charged, up to 8 hours. Their battery charge lasts 2 hours and the operating hours of the store differ ...
3
votes
1answer
124 views

Linearizing power term in objective function

I would like to linearize $x^2$ term in my objective function. I understand this can be solved using quadratic programming solver; however, for my use case linearization is necessary to convert it to ...
4
votes
2answers
198 views

Output of binary variable greater than one

I am working on a shipping demurrage problem that uses a binary variable to denote the date a specific vessel can be loaded (I have been kindly helped by Wesley on OR before with this). I am confident ...
3
votes
2answers
138 views

Limit number of switches in employee scheduling problem

Here is a scheduling problem I need to solve. Given the demand for 2 positions in 1 week with 3 shifts per position, I need to allocate the employees accordingly with some extra operational ...
3
votes
1answer
100 views

Pyomo: Help setting up my model

I have been working with a model for the past couple of weeks, but I am not sure what am I doing wrong as every time Pyomo returns that is infeasible or ...
2
votes
1answer
124 views

Linearize sum of product in objective function

Notation: I have an optimisation problem with objective function: \begin{align}\max&\quad\sum_n Q_n\\\text{s.t.}&\quad Q_n=x_{ij}^{nk}(y_i^{nk}-c_n), \forall n \in N, k \in K, (i,j) \in P.\end{...
2
votes
1answer
133 views

Representing Date Variables in Pulp

I am working on an optimisation problem that involves minimising shipping demurrage. I am struggling to model how to represent the difference, (x-y) between dates where the ship is ready to be loaded ...

1 2 3
4
5
9