Skip to main content

Questions tagged [linear-programming]

For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.

Filter by
Sorted by
Tagged with
0 votes
0 answers
33 views

Combine two constraints into one

I have these two constraints, where the indices are $i$ person, $j$ shift and $t$, the day. $x_{ijt}$ is the shift assignment, $m_{ijt}$ the motivation of the person in a shift (only takes values $m_{...
nflgreaternba's user avatar
2 votes
1 answer
184 views

Set a limit on value change of a binary variable

I am working on an Energy Management problem. The objective is to minimize the electricity bill for the customer. I have a time-series data with 15 min. intervals spanning the course of 1 year. The ...
Kushagr Goyal's user avatar
2 votes
0 answers
39 views

Using BigM and auxiliary variable to linearise model leads to incorrect results

I am working on a Pyomo optimization model that aims to select the cheapest fuel for production at different facilities over several time periods. The model should select Mode1 for Tech1 when Fuel1 is ...
Jamie Bull's user avatar
-1 votes
0 answers
47 views

Master problem modification leads to dual value calculation problems

I have the following problem. I have set up a Column Generation model and implemented it in Gurobi. It is a bit hardcoded, but it works so far. There I have the two dual vectors $\pi_{ts}$ and $\mu_i$....
nflgreaternba's user avatar
3 votes
1 answer
93 views

Restrict the number of non-zero variables to any constant in MILP

I am designing an MILP in which given a set $[n]$ of $n$ agents, we create for each $i \in [n]$ a real variable $x_i$. The variables $x_i$ are between 0 and 1 ($0 \leq x_i < 1$). I would like to ...
Samuel Bismuth's user avatar
0 votes
1 answer
41 views

How to compare models?

I have the following problem. I have a staff scheduling model that explicitly considers employee motivation in the modeling (this is modeled by additional constraints that sum up the number of ...
nflgreaternba's user avatar
0 votes
0 answers
37 views

Linear sum assignment, but with ranked assignments?

Let's say I have 5 tasks that I have to assign to 5 agents, with a cost matrix: ...
Dan's user avatar
  • 1
-1 votes
0 answers
49 views

proof of NP-hardness

I have a scheduling problem and was wondering how to prove that the problem at hand is $NP$- hard? The model minimizes overstaffing and comes with normal scheduling constraints (demand, working hours ...
Karl Seidl's user avatar
1 vote
1 answer
90 views

Conditional binary programming

I am currently trying to model the relationship that if the binary variables $b_{it}=0$ and $c_{it}=1$, and for the integer non-negative variable $b^{n}_{i(t-1)}=0$, then the new binary variable $a_{...
mingabua's user avatar
0 votes
0 answers
33 views

Scheduling categories of jobs with completion time requirements

Consider a discrete time slotted, system with two categories of jobs $J_1$ and $J_2$, where each job from the category $J_1$ has completion time requirement of $C_1$ and the jobs from category $J_2$ ...
ephemeral's user avatar
  • 917
1 vote
1 answer
78 views

Schedule monotony constraints

Suppose I have a model for creating a nurse's duty roster. The model has the indices $i$ for the person, $t$ for the day and $s$ for the shift. I have the binary variable $x_{its}$ which indicates ...
manofthousandnames's user avatar
1 vote
0 answers
95 views

Knapsack problem - reducing the number of decision variables

I am trying to solve something similar to a knapsack problem: $$\max \sum v_{n}P_{n}$$ subject to some basic weight constraints. However, what makes this problem difficult to solve is that $P_{n}$ is ...
BenBernke's user avatar
  • 185
1 vote
1 answer
66 views

Help modeling linear constraints

I have the following variables and indices. I have $y_{ijk} \in [0;1]$ which indicates how performant a machine $i$ is on day $j$ in the interval $k$. The binary variable $z_{ijk}$ indicates whether a ...
mingabua's user avatar
0 votes
1 answer
80 views

Single Machine Job Scheduling With Release Dates and No Idling Constraint

I'm trying to model a linear job scheduling optimisation problem. There is a single machine and N jobs $J_1, J_2, ..., J_N$. Each job consists of one step with processing time $p_1, p_2, ..., p_N$. ...
Ralph Melish's user avatar
1 vote
0 answers
55 views

Does getting the second optimal solution in a general MILP require solving a MILP again?

This general question popped into my mind if finding all optimal solutions takes not much more time than finding just one optimal solution in a MILP why not gettting all of them in Gurobi?
Red shoes's user avatar
  • 153
2 votes
1 answer
110 views

How to model the constraints of min and max in cvxpy

I have a continuous variable $x_{ij}\in[0,1]$ and I need to write the following constraint: $$M_i-m_i+1\leq C_i$$ where $M_i=\max\{j: x_{ij}>0\}$ and $m_i=\min\{j: x_{ij}>0\}$
zdm's user avatar
  • 403
2 votes
2 answers
121 views

Deriving linear constraints from logical notation

I have the following two logical implications. $x_{it}$ and $y_{it}$ are binary, $N$ is an integer number. $i$ and $k$ are indexes. $$\sum_{k=1}^{t}x_{ik}\ge N~\implies y_{it}=1$$ $$\sum_{k=1}^{t}x_{...
manofthousandnames's user avatar
4 votes
2 answers
296 views

Linear condition between two continuous variables

There are two real variables $x$ and $y$. The conditions are such that: if $y\le 0$, then $x=0$ if $y>0$, then $x=y$ How to write linear equations or inequalities to satisfy both the conditions?
Lorentz's user avatar
  • 41
0 votes
1 answer
104 views

How to model this constraint in a better way?

I have a resource allocation problem. There are $M$ users and $N$ resources (machines). One user can be assigned to multiple resources/machines. But maximum $B$ machines can be activated at a time for ...
KGM's user avatar
  • 2,297
1 vote
0 answers
41 views

Primal-dual simplex method for general LP

I've learned the primal-dual method for standard LP, but for a general LP written as \begin{align} \min_{x\in \mathbb{R}^n} ~~~ &c^\top x \\ s.t. ~~& l^{s}\leq Ax \leq u^{s},\\ ...
andy's user avatar
  • 77
0 votes
0 answers
57 views

What's the dual of an LP in its general form?

For an LP written as \begin{align} \min_{x\in \mathbb{R}^n} ~~~ &c^\top x \\ s.t. ~~& l^{s}\leq Ax \leq u^{s},\\ &l^{x}\leq x \leq u^{x} \end{align} how can we get its dual ...
andy's user avatar
  • 77
3 votes
1 answer
191 views

Reformulate constraints

I have the following constraints and am wondering whether I can formulate the whole thing more narrowly and with fewer constraints. $x_{itk}$ is binary and $u_{it}, v_{itk}\in [0,1]$. $M$ is a Big-M ...
manofthousandnames's user avatar
0 votes
0 answers
40 views

Linearizing a continuous function

is there a way to linearize this and plug it in a mathematical model ? Suppose I have a continuous variable, if used once, it triggers a secondary effect that reduces the targeted upper bound by a ...
applethal's user avatar
3 votes
1 answer
66 views

What approximation is guarantees when solving an LP with floating-point numbers?

Given a linear program $$\begin{align} \text{maximize} \quad & c^{T}x \\ \text{s.t.} \quad & A x \leq b \end{align} $$ I can solve it exactly in polynomial time, using e.g. interior-point ...
Erel Segal-Halevi's user avatar
1 vote
1 answer
78 views

How to track the first timestep at which a binary variable becomes 1 in an IP? [duplicate]

I have an MIP where I have a binary variable $y_t$ which is set to 1 or 0 and is indexed by time t. It can be set to 1 at multiple timestamps but it is never continuously 1 for more than single ...
Demitri's user avatar
  • 11
1 vote
1 answer
45 views

Converting a function composing of multipe pieces into a linear equation

I have a variable (alpha) which depends on some other binary variables, denoted as X_i. So, for some combination of other variables, alpha may take a value (Beta_j). I added some auxillary variables (...
Sam's user avatar
  • 97
1 vote
1 answer
82 views

How to model $\max\limits_{x\in X} \min\limits_{y\in Y} \max\limits_{z\in Z} f(z)$ as single MILP

I have the following optimization problem: \begin{align*} \max\limits_{x\in X} &\min\limits_{y\in Y} \max\limits_{z\in Z} & f(z) \\ &\text{such that} & (x, y, z)\in P \end{align*} ...
graphtheory123's user avatar
2 votes
1 answer
84 views

Why this ILP and LP are equivalent?

Let's consider a competition with $n$ questions. Each question has a price $p_i$ and a score $v_i$. To advance to the next round of the competition, we need to accumulate a minimum score of $D$. We ...
occasional's user avatar
1 vote
1 answer
83 views

A tool for finding integer solutions to linear systems

I have a system of linear equations $A x = 0$, where $A$ is an integer matrix, and I want to find a non-zero solution, if it exists. In that case, a rational solution exists. Multiplying by the common ...
Erel Segal-Halevi's user avatar
0 votes
0 answers
46 views

Solving convex separable programming problem using interior point method?

In my engineering application, all decision variables are non-negative and everything is convex separable. In addition to that, the only function that I am trying to approximate with grid point are $f(...
Tuong Nguyen Minh's user avatar
1 vote
1 answer
80 views

Economic interpretation of shadow/dual variables in LP

I have recently read a text which deals with the dual variables attached to constraints. In an economic sense, one can interpret them as shadow variables indicating market clearing for resource ...
Marlon Brando's user avatar
4 votes
3 answers
322 views

How to maximize the number of variables with value at least 0?

Given a matrix $A$ and a vector $b$, I would like to find a vector $x$ satisfying the set of linear constraints $A x \leq b$, and subject to that, contains as many variables as possible with ...
Erel Segal-Halevi's user avatar
1 vote
1 answer
64 views

Linearizing a quadratic constraint

I am working on a quadratic conic optimization problem, but I have discovered that it would be preferable if the quadratic constraint is linearly approximated. In other words, I need some way to make ...
Mikkel Honningsvåg Sandhaug's user avatar
1 vote
1 answer
62 views

How to write a constraint to find the index of the min value in a set?

Consider this example with set A={100,50,150}. Min value in this set is 50. How to find out that the index of 50 is 2 in this set? I need 2 as the answer to put it in another constraint
Shayan Helali's user avatar
1 vote
1 answer
66 views

Connections between Bounds in MIPs

we are currently learning about MIP/MILP minimization at university and have become familiar with the branch-and-bound algorithm. Unfortunately, the relationship between upper bound, lower bound and ...
Vv J's user avatar
  • 19
0 votes
2 answers
72 views

How to write a If then else constraint with continuous variables

I have a problem under investigation which requires if, elseif and else conditions to implement as a constraint in a mixed integer program. Any leads will be appreciated. Thanks a lot. Let $x_t$, $y_t$...
Srinivasan B's user avatar
1 vote
0 answers
36 views

How to convert unit-capacity network flow into transportation problems?

I am working on a problem that can be modeled as a minimum-cost network flow problem where the capacity of edges is 1. I found Exercise 3.8, Chapter 5 of Parallel and Distributed Computation: ...
Recursion's user avatar
1 vote
1 answer
55 views

Cplex no solution but no conflict

I am solving a problem using benders decomposition. The master problem is solved by cplex.The subproblems are logic and can be solved without using cplex solver. The scale for subproblem is large. ...
XXia's user avatar
  • 49
0 votes
1 answer
76 views

Scheduling optimization problem - Where to begin?

Class Scheduling Optimization for a Trade School We are exploring ways to model, simulate, and optimize class scheduling for a trade school, focusing on addressing the complex dynamics of managing ...
Evan's user avatar
  • 1
0 votes
0 answers
55 views

How to initialize a parameter (belonging to the first stage model) in a two stage model, taking its value from second stage model?

I am working on a two stage approach in order to reduce the complexity of a scheduling model which is an NP-hard problem. I have to implement a while loop in order to repeat solving the models in case ...
Baghban's user avatar
  • 131
1 vote
1 answer
62 views

Fast Algorithms for Min-cost Multicommodity Flow Problem with Most Arcs Having 0 cost

I have a min-cost multicommodity flow problem with the following characteristics: Flows can be fractional (integer flows not required) Set of commodity types is $K$, set of demand nodes is $\\{ d_k : ...
graphtheory123's user avatar
1 vote
1 answer
108 views

Dual to Primal conversion

I recently tried to solve a primal minimization problem using its maximization dual. In the optimal simplex tableau of the dual, there was a slack variable and only one dual variable in the basis. So, ...
Shanya Tiwari's user avatar
2 votes
1 answer
154 views

How to pass the values of a variable of the first model to a parameter of the second model?

I am working on a scheduling problem which is NP-hard problem. Therefore, I decided to implement two-stage strategy to speed up the solution process. I need to pass the values of a variable from the ...
Baghban's user avatar
  • 131
0 votes
2 answers
121 views

Converting a piecewise function to linear equations

I am trying to build a MILP model. In this model, I have a dependent variable (alpha) that its value depends on the value of some other variables (or different combination of some other variables). In ...
Sam's user avatar
  • 97
1 vote
0 answers
97 views

Converting a Linear Program with TU Constraint Matrix to a Nonlinear Convex Model: Solver Performance?

I'm currently working on a large Mixed Integer Program (MIP) where the constraint matrix is Totally Unimodular (TU), allowing me to model it as a Linear Program (LP) for efficiency, as total ...
graphtheory123's user avatar
-1 votes
1 answer
66 views

How to linearize a product of an integer and a binary variable

i have this constraint right here, which is not linear. How would i linearize such a product. $number_t$ is a positive integer and $new_t$ and $reset_t$ are binary. $$number_t = (number_{t-1}+new_t)\...
Uni ewr's user avatar
  • 61
1 vote
0 answers
80 views

Coding Operation research algorithms

Can you suggest good books to refer regarding coding operation research algorithms like transportation algorithm, assignment algorithm etc What are the best practices for coding those algorithms
Tharindu Kariyawasam's user avatar
1 vote
1 answer
67 views

Weighted sum in the objective function

I am working on my actual model. The objective function aims to maximize the preferences related to each criterion pc to select the best contract that fits with the project characteristics( c1= size, ...
Basma Ben Mahmoud's user avatar
2 votes
0 answers
87 views

Re-formulating an LP where a subset of constraints can be loosened?

I have an LP of the structure below (omitting some constraints that are not directly applicable for this question). $$\text{min } c'x$$ $$Ax + By \geq d$$ for a given $A \in R^{m \times a}_{>0}, B \...
Mason's user avatar
  • 515
0 votes
1 answer
147 views

PuLP is ignoring constraints, and setting everything to 0 for minimization problem

I have a multi-objective optimization problem I am trying to solve with competing objectives. I am trying to model a network of industrial businesses which can share wastewater rather than sending it ...
Caleb O's user avatar
  • 13

1
2 3 4 5
17