Questions tagged [mixed-integer-programming]

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

37 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
12
votes
0answers
220 views

Tools to implement branch-and-price algorithms

As far as I know, implementing a branch-and-price algorithm is a task far from trivial. However, there are tools such as SCIP or the BCP framework of COIN-OR that help implement such algorithms. I ...
12
votes
0answers
106 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) ...
10
votes
0answers
154 views

Solving large-scale stochastic mixed integer program

What are some methods or algorithms for solving a large-scale stochastic mixed-integer optimization problem that runs on an hourly dataset for a year? Do we employ some kind of decomposition? (the ...
9
votes
0answers
88 views

For subset selection regression as a mixed integer program, how tightly should the bounding box be set?

When solving best subset regression as a mixed integer program, how do you decide how tightly to bound the range of values of the $X$ values? When the box is tight, the solver finds a solution ...
8
votes
0answers
66 views

Modelling a simple ordering problem to have balanced delivery days

Assuming that I should buy 50 items from 25 different vendors with pre-known delivery duration between 2-7 day for each, which day of a week should I place each order so that the delivery days be even ...
8
votes
0answers
85 views

Automatic detection of SOS variables and constraints

We've been working on a new feature for Octeract Engine, namely to automatically extract SOS structure from a model and then exploit it. While the literature is quite rich on what to do with SOS once ...
6
votes
0answers
76 views

Building the Scheurman's Model II constraints for a multi period linear program

Scheurman's paper discusses Model I and model II Formulation to solve harvesting and scheduling problems. It is a specific implementation to solve multi period linear programs. Both models are also ...
6
votes
0answers
75 views

Benefits of removing slack variables during presolve

I was reading Tobias Achterberg's thesis, and on page 138 he mentions the following presolving technique for linear equations (I'm slightly paraphrasing Example 10.2): Consider the equation $4x_1+...
6
votes
0answers
66 views

Data Formulation for Mixed-Integer-Programming Models

Until now, I have used the Gurobi, CPLEX and OR-Tools (GCO) interface to formulate mixed-integer-programming models. Recently, I have discovered MiniZinc and want to utilize it to formulate big ...
6
votes
0answers
248 views

Cplex is stuck after root node relaxation solution

I am solving an MIP through Benders decomposition (coded both generic and legacy callback versions), by employing Java with Cplex 12.9. For some of the instances, Cplex is stuck for two hours (time ...
5
votes
0answers
41 views

What are useful plots/statistics/metrics when analyzing the solution sensitivity in multi-objective optimization?

Consider an optimization problem with $n>3$ objectives. For handling this there exists often two approaches: a) some weighting of the objectives, b) fix an order of objectives and then optimize ...
5
votes
0answers
73 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 ...
5
votes
0answers
213 views

What is the difference between root relaxation and LP relaxation

(I apologize. I saw this question but, I do not know these may be the same or not.) I am trying to solve a MIP problem and have an issue about that. The problem's LP relaxation has the objective ...
5
votes
0answers
58 views

Complexity of determining whether a LP or MIP is infeasible

What is the best complexity for the worst case scenario and the algorithm associated with it to determine if a linear programming (LP) is infeasible ? Further, what if we consider a mixed integer ...
5
votes
0answers
87 views

Solver for Go Programming Laguage

Has anyone used MIP solvers (open source or commercial) with Go language https://golang.org/? I am looking for a solver for simple linear MIPs for network flows and set cover types of problems.
4
votes
0answers
60 views

“Rank 1” type constraint $X=vw^\top$: MILP representation? Convex relaxation? Other tractable approach?

Suppose $X\in\mathbb{R}^{m\times n}$, $v\in\mathbb{R}^m$, $w\in\mathbb{R}^n$ are variables from an optimization problem, which also includes the constraints: $$0\le v\le a$$ $$0\le w\le 1$$ $$w_1+\...
4
votes
0answers
66 views

Adding redundant inequality to a model

The following relationship is part of my optimization model ($W_k$ denotes a binary variable) $$W_{1} \le \cdots \le W_{k-1} \le W_{k} \le W_{k+1} \le \cdots \le W_{k^{\max}}$$ My question is, do ...
4
votes
0answers
63 views

Continue on “Is there a known MILP to schedule routes after routes are made”

I have made some progress on my previous question (Is there a known MILP to schedule routes after routes are made). I have derived the sets of the problem, which are: 1) Itineraries of vehicle: $i \in ...
4
votes
0answers
505 views

cvxpy: Code that works for default solver doesn't work for cp.GLPK_MI

The following code works: ...
4
votes
0answers
162 views

Publishing paper that uses LP solver to solve equation

I was reading this paper by Cerna et al. (2018)1. In the paper there are only CPLEX-solvable equations given by the authors and the results. How valuable is this paper, and what is its quality? Can ...
3
votes
0answers
65 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
0answers
92 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 ...
3
votes
0answers
73 views

Linearization of the shifted copy of a function

Suppose in a model I have the expression $y_{1}(x) = 10 + 5 x^2$ where $x \in [0,20]$ is a continuous variable. In order to be able to use an MILP solver, I piecewise linearise $z_{1} = x^2$, by ...
3
votes
0answers
47 views

Linearisation using SOS2

I am trying to linearise the following expresssion. $C(k) = B(k) e^{-d(k)}, B(k) \ge 0 , d(k) \ge 0 $ I am trying to do this by using SOS2 sets. I set $X(k) = e^{-d(k)}$ and I get $C(k) = B(k) X(...
3
votes
0answers
49 views

What are the efficient ways to model this scheduling problem and ways to improve running time

There are $N - \{1 \ldots N\}$ jobs, each with processing time $p_j$, to be scheduled on $M - \{1 \ldots M\}$ machines over span of $D - \{1 \ldots D\}$ days and while working $T - \{1 \ldots E \ldots ...
3
votes
0answers
60 views

Integer variable optimization - decreasing execution time

I have a variable declared as follows in AMPL: ...
3
votes
0answers
46 views

Discrete optimization in transport economics

I was working on a problem in transport economics where the optimal number of trips in a given duration of time is to be found out. The profit is a function of the price vector $p$ and time cost $c$ ...
2
votes
0answers
34 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 ...
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
0answers
143 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 ...
1
vote
0answers
53 views

Modeling the multiplication of two binary decision variables in undirected graph in python

In an undirected graph, I'm trying to model a constraint that forcing the optimizer to set an edge $(u,v)$ between two nodes to only exist (= $1$) if the two nodes have been selected to be $1$. The ...
1
vote
0answers
17 views

Implement geometric constraint using DOCplex

currently I'm working on a wind farm layout optimization problem. I found an appropriate model in literature (Fischetti et al.) and now I'm trying to reproduce it using the Python API of cplex with ...
1
vote
0answers
66 views

Ways to improve lower bounds while solving MIPs

What are the ways to improve lower bounds while solving a minimization problem (MILP)?
1
vote
0answers
64 views

Converting Nonlinear Program into an LP

I have a problem with a nonlinear objective function which is \begin{align}\min&\quad Z_j\cdot(N_j)^{0.5}\end{align} where $j$ is the index. I want to know how can I turn it into a linear ...
0
votes
0answers
73 views

Linearization of constraints with square root

I am trying to solve an optimization programming model involving a non-linear constraint with a square root. It follows (in a simplified form): $X_i\ge\sqrt{A_i/B_i}$ where $X_i,A_i,B_i$ are positive ...
0
votes
0answers
60 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 ...
-1
votes
2answers
144 views

How to model y = floor(x)

I went through 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 do not see it?