How to optimize a problem using only linear constraints

Viewed 63

I am new to AMPL. Currently I am trying to optimize a networking problem. I can only use CPLEX solver. Others like ILOG CP are forbidden.
Input:

  • Demands - set of demands that have to be fulfilled (basically QoS rules) which consist of multiple paths between a given pair of servers. Every path must be assigned some guaranteed bandwidth which is >= 0
  • demand_maxPath - number of paths for a demand d
  • hd - bandwidth requested for a demand d

Goal
The goal is to assign bandwidths to every path with regards to some cost function. Here is an example. d denotes demand id, x(d,1) is a first path that belongs to demand d and so on, hd denotes bandwidth requested for a demand d.

Constraints

There are a couple of constraints:

  1. sum of bandwidths of all paths for a demand d must equal hd
  2. x(d,p) must be equal to hd, where p is a variable

Constraint 2 enforces that all other paths from a demand d, except for path (x,dp) must be equal to 0.
Approach

My approach: I declared a variable:

var demandPath_signalCount { d in Demands, 1..demand_maxPath[d]}, >= 0;

which holds values for each of the paths. The following constraint reflects contraint 1:

subject to demand_satisfaction_constraint { d in Demands }:
  sum { dp in 1..demand_maxPath[d] } demandPath_signalCount[d,dp] = h[d];

However, I can't think of a way to write constraint 2. For example:

subject to path_value_satisfaction_constraint { d in Demands }:
  max { dp in 1..demand_maxPath[d] } demandPath_signalCount[d,dp] = h[d];

doesn't work since max() function is nonlinear.
Other idea was to declare another variable:

var demand_chosenPath { d in demands }, >= 0;

and to use it like so:

subject to path_value_satisfaction_constraint { d in Demands }:
  demandPath_signalCount[d,demand_chosenPath[d]] = h[d];

It obviously doesn't work either since variables cannot be used as indices.
Yet another way that I tried was to constraint the values that demandPath_signalCount may be equal to like so:

set possible_values {d in Demands } = 0..demand_volume[d] by demand_volume[d];

and

subject to possible_values_satisfaction_constraint { d in Demands, dp in 1..demand_maxPath[d] }:
  demandPath_signalCount[d,dp] in possible_values[d];

But then again, the error is: continuous variable in tuple

How to formulate the second constraint?

0 Answers
Related